# Swiss Table flat_hash_map Internal Structure: How Abseil Achieves O(1) Lookups

> Explore the Swiss Table flat_hash_map internal structure. Learn how Abseil achieves O(1) lookups using H1 H2 hash components and SIMD group probing.

- Repository: [Abseil/abseil-cpp](https://github.com/abseil/abseil-cpp)
- Tags: internals
- Published: 2026-07-11

---

**`absl::flat_hash_map` implements a Swiss table using a flat array of control bytes paired with key-value slots, achieving amortized O(1) lookups by splitting hash values into H1 (index) and H2 (filter) components and probing in SIMD-friendly groups.**

The `absl::flat_hash_map` container in the Abseil C++ library is a high-performance hash map that uses the *Swiss table* design to store elements in a contiguous memory block. Unlike node-based containers, this **Swiss table flat_hash_map** separates metadata (control bytes) from stored values to maximize cache locality. According to the Abseil source code, the implementation achieves constant-time operations through a layered architecture spanning three primary headers: [`absl/container/flat_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/flat_hash_map.h), [`absl/container/internal/raw_hash_map.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/raw_hash_map.h), and [`absl/container/internal/raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/absl/container/internal/raw_hash_set.h).

## Flat Memory Layout and Control Bytes

The Swiss table stores data in two parallel arrays: a **control byte array** followed by an **array of slots** holding the actual key-value pairs.

A control byte indicates whether a slot is empty, deleted (tombstone), or occupied. For occupied slots, the lower 7 bits store **H2**, a 7-bit hash fragment derived from the full hash value. This design is defined in [`raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/raw_hash_set.h)【7†L85-L89】.

To enable branchless probing without bounds checking, the control array includes a **sentinel** value (`kSentinel`) and a **clone region** that replicates the first `kWidth-1` control bytes at the end of the array. As implemented in [`raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/raw_hash_set.h)【6†L70-L78】, this padding ensures that probe sequences can cross the array boundary safely without wrapping logic.

## Two-Part Hash Decomposition

When a key is hashed via `absl::Hash`, the result is split into two parts to optimize lookups:

- **H1**: The low bits serve as the starting index into the slot array. The definition in [`raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/raw_hash_set.h)【7†L82-L84】 shows that `H1(hash)` effectively equals the hash value masked to the table size.
- **H2**: The upper 7 bits are stored in the control byte to filter candidates. This fragment is stored via the logic in [`raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/raw_hash_set.h)【7†L85-L89】.

During lookup, the probe sequence begins at the H1 index and walks through groups. Only slots with matching H2 values require a full key comparison, reducing expensive `operator==` calls to approximately one per lookup on average.

## Group-Wise Quadratic Probing

Probing operates on **groups**—contiguous chunks of control bytes sized to `Group::kWidth` (typically 16 bytes on x86 to leverage SIMD instructions).

The algorithm proceeds as follows:
1. Compute the group index from H1.
2. Scan the group's control bytes for a match with the target H2 value.
3. If H2 matches, perform a full key comparison.
4. If no match is found, advance to the next group using quadratic probing.

Because the load factor is capped at **7/8** (see `CapacityToGrowth` in [`raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/raw_hash_set.h)【7†L31-L38】), each group contains on average two empty slots. This guarantees that the probe sequence terminates quickly, with an expected false positive rate for H2 matches of ≤ 1/8【6†L33-L36】.

## Small Object Optimization (SOO)

For tables containing zero or one elements, the container avoids heap allocation entirely. The `SooCapacity()` function in [`raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/raw_hash_set.h)【6†L78-L80】 determines when to store the single slot inline within the `HeapOrSoo` union inside the container object. This optimization eliminates pointer indirection for small maps.

## Growth and Rehashing Mechanics

When the element count reaches `capacity * 7/8`, the table resizes to the next valid capacity. The `NextCapacity` function in [`raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/raw_hash_set.h)【7†L19-L23】 computes the new size as `2^n - 1`, maintaining power-of-two alignment minus one for efficient masking.

The memory layout for the new allocation is calculated by `RawHashSetLayout`【7†L38-L45】, which arranges control bytes and slots to satisfy alignment requirements while minimizing padding. Rehashing is amortized O(N) and preserves the O(1) guarantee for individual operations.

## Step-by-Step O(1) Lookup Analysis

The constant-time guarantee emerges from the following pipeline:

- **Hash computation**: Computing `absl::Hash(x)` and splitting into H1/H2 is constant time.
- **Group scanning**: Each group fits in a single cache line, requiring minimal memory accesses.
- **H2 filtering**: The 7-bit filter eliminates approximately 99.2% of slots from full comparison (false positive rate ≈ 1/128).
- **Key comparison**: Expected constant comparisons (≈ 1) due to low collision probability.
- **Termination**: The 7/8 load factor ensures the probe chain length is bounded by a small constant.

Consequently, `find()`, `insert()`, and `erase()` operations execute in amortized O(1) time with low constant factors.

## Code Example

```cpp
#include "absl/container/flat_hash_map.h"
#include <string>
#include <iostream>

int main() {
  // Initialize with Swiss table implementation
  absl::flat_hash_map<std::string, int> m = {
    {"one", 1}, {"two", 2}, {"three", 3}
  };

  // O(1) lookup using H1/H2 decomposition
  if (auto it = m.find("two"); it != m.end()) {
    std::cout << "Found: " << it->second << "\n";
  }

  // Heterogeneous lookup avoids string construction
  std::string_view sv = "three";
  if (auto it = m.find(sv); it != m.end()) {
    std::cout << "Found via string_view: " << it->second << "\n";
  }

  // Internally calls raw_hash_map::insert_or_assign_impl
  m.insert_or_assign("four", 4);
}

```

All public operations delegate to the generic `raw_hash_set` logic, inheriting the Swiss table performance characteristics.

## Summary

- **`absl::flat_hash_map`** delegates to `raw_hash_map` and `raw_hash_set` for the core Swiss table implementation.
- **Control bytes** store 7-bit H2 hash fragments separately from slots, improving cache locality and enabling SIMD filtering.
- **H1/H2 decomposition** splits the hash into an index (H1) and a filter (H2), minimizing full key comparisons.
- **Group-wise probing** processes 16-byte chunks of control bytes to check multiple slots simultaneously.
- **7/8 load factor** ensures probe sequences terminate quickly, guaranteeing amortized O(1) operations.
- **Small Object Optimization** stores single elements inline, avoiding heap allocation for tiny maps.

## Frequently Asked Questions

### What is the difference between H1 and H2 in Swiss table hashing?

H1 consists of the low bits of the hash value and determines the starting index for the probe sequence. H2 consists of the high 7 bits and is stored in the control byte to filter candidate slots before performing expensive key comparisons. This separation is defined in [`raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/raw_hash_set.h)【7†L82-L89】.

### Why does flat_hash_map use a 7/8 load factor instead of 1.0?

A maximum load factor of 7/8 ensures that each group of control bytes contains at least one empty slot on average, guaranteeing that probe sequences terminate after checking a constant number of groups. The `CapacityToGrowth` function in [`raw_hash_set.h`](https://github.com/abseil/abseil-cpp/blob/main/raw_hash_set.h)【7†L31-L38】 enforces this limit to maintain O(1) lookup performance.

### How does the control byte array improve cache performance?

The control byte array is much smaller than the slot array (1 byte vs. sizeof(key)+sizeof(value)), allowing 16 or more control bytes to fit in a single cache line. This enables the probing algorithm to check multiple slots using SIMD comparisons before touching the actual key-value data, drastically reducing cache misses during lookups.

### What happens when flat_hash_map needs to grow?

When the element count reaches the growth threshold (capacity × 7/8), the `NextCapacity` function calculates the new size as the next power of two minus one. The `RawHashSetLayout` class computes the memory layout for the new allocation, and all elements are rehashed into the new table. This rehashing occurs infrequently enough that individual insertions remain amortized O(1).