Why Hash Tables Collide: Swiss Tables, Robin Hood Hashing, and CPU Cache Lines

Modern CPUs execute arithmetic in a few nanoseconds, while a random access to main memory can take dozens of nanoseconds. The memory hierarchy that mediates this gap is:

• L1 cache – typically a 64‑byte line, hit latency ~4–5 cycles.
• L2 cache – larger line, hit latency ~12–14 cycles.
• L3 cache – shared among cores, hit latency ~40–60 cycles.
• DRAM (main memory) – latency ~150–250+ cycles.

When a program follows a pointer, the CPU must load the 64‑byte cache line that contains the referenced object. If the line is not already present in any cache level, the request travels to DRAM, incurring the full latency above.

Why a linked‑list bucket hurts performance

In a traditional separate‑chaining hash table each bucket holds an 8‑byte pointer to a heap‑allocated node. Nodes are allocated independently (e.g., via malloc), so successive nodes are scattered across virtual address space. Traversing a three‑element chain looks like:

Node* cur = bucket_ptr;
while (cur) {
    // use cur->key, cur->value
    cur = cur->next;
}

Each dereference triggers a cache‑line fetch:

• First node may be in L1 or L2 – cheap.
• Second node is likely in a different line, often missing L1/L2/L3 and forcing a DRAM fetch.
• Third node repeats the miss.

Three misses can stall the core for >300 cycles, during which the CPU does no useful work. The cost grows linearly with chain length, making lookups unpredictable and far slower than the few cycles needed for hash computation.

Practical impact

Consider a hash table with a load factor of 0.75 and an average chain length of 4. A lookup that traverses the entire chain will experience roughly four DRAM accesses, each costing ~50 ns. The total latency can exceed 200 ns, whereas an open‑addressing table that stores keys contiguously typically finds the entry within a single cache line, completing in < 10 ns.

Because the CPU spends most of its time waiting for memory, modern libraries (e.g., Rust’s hashbrown, Google’s Abseil flat_hash_map) replace linked lists with open addressing or SIMD‑accelerated probing, eliminating pointer indirection and maximizing cache locality.

Open addressing replaces pointer‑based chaining with a single contiguous array that holds every key‑value pair. Because the array resides in a linear memory region, a probe of adjacent slots typically hits the same 64‑byte cache line, reducing the latency of each memory access from dozens of cycles (DRAM) to a few cycles (L1 cache).

Two classic probing strategies are common:

• Linear probing examines slots i+1, i+2, … in order.
• Quadratic probing examines slots i+1², i+2², …, spreading the search pattern more widely.

Both strategies suffer from primary clustering. In linear probing, a collision creates a run of occupied slots; any new key that hashes near the run collides again and lengthens the cluster. The evidence notes that lookup time “degrades rapidly once load factor exceeds 60 %,” because the probe sequence must scan longer runs of contiguous entries.

Deletion introduces the tombstone dilemma. Removing an entry by marking its slot empty breaks the probe chain: a later lookup for a key that resides after the deleted slot would stop prematurely and incorrectly report “not found.” To preserve correctness, implementations use a special DELETED marker (a tombstone). Tombstones remain in the array and must be examined on every subsequent probe, turning otherwise fast misses into linear scans over dead slots until the table is rebuilt.

Practical example in a C‑like pseudo‑code:

bool find(key) {
    idx = hash(key) % capacity;
    while (control[idx] != EMPTY) {
        if (control[idx] != DELETED && table[idx].key == key) return true;
        idx = (idx + step) % capacity; // step = 1 for linear, i*i for quadratic
    }
    return false;
}

Mitigations include:

• Keeping the load factor below the clustering threshold (e.g., ≤ 0.6).
• Periodically rehashing to eliminate tombstones.
• Adopting advanced schemes such as Robin‑Hood hashing or Swiss Tables, which store a 1‑byte control byte per slot and use SIMD to probe 16 buckets at once, dramatically reducing the impact of both clustering and tombstones.

When designing enterprise‑grade hash maps, engineers should weigh the simplicity of linear/quadratic probing against the predictable performance penalties of primary clustering and tombstone accumulation, and consider modern open‑addressing variants that preserve cache locality while providing bounded probe lengths.

Robin Hood hashing is an open‑addressing scheme that equalizes the probe sequence length (PSL) of all entries. Each slot stores the distance between the key’s original hash index and its current position. When a new key is inserted, its PSL starts at 0 and increments with each probe. If it encounters an existing entry whose PSL is smaller, the newcomer “steals” the slot, evicting the richer entry, which then continues probing with its original PSL. This exchange continues until every element finds a home where its PSL is not greater than the occupant’s PSL.

Tracking PSL has two immediate effects on the table’s behavior:

• Flattened probe distribution: By constantly swapping richer keys with poorer ones, the algorithm prevents long chains from forming. The result is a near‑uniform distribution of probe lengths, which yields predictable latency even at high load factors.
• Early‑termination of failed lookups: During a search, the current search PSL is compared to the PSL stored in each examined slot. If the slot’s PSL is lower than the search PSL, the key cannot exist further in the probe sequence, allowing the algorithm to stop without scanning the remainder of the cluster.

Consider a table with slots 0‑4 holding keys A, B, C, D and an empty slot 5. Their original hashes are 0, 0, 0, 1 respectively, giving PSLs of 0, 1, 2, 2. Inserting a new key X that also hashes to 0 proceeds as follows:

slot 0: A (PSL 0) – X.PSL 0 ≤ A.PSL → continue
slot 1: B (PSL 1) – X.PSL 1 ≤ B.PSL → continue
slot 2: C (PSL 2) – X.PSL 2 ≤ C.PSL → continue
slot 3: D (PSL 1) – X.PSL 3 > D.PSL → X steals slot 3,
          D is re‑inserted with PSL 2 and eventually lands at slot 5.

During a lookup for a non‑existent key Y, the algorithm increments a search PSL with each probe. If it reaches a slot where stored PSL < search PSL, it can safely abort, knowing Y would have been encountered earlier. This property eliminates unnecessary memory accesses, which is critical on modern CPUs where a cache miss can cost dozens of cycles.

Robin Hood hashing therefore improves cache locality (all entries reside in a contiguous array) and reduces variance in lookup times, making it a preferred choice for high‑performance hash maps such as Rust’s hashbrown and many in‑memory database engines.

Swiss Tables implement an open‑addressing hash map that stores all key‑value pairs in a single contiguous buffer, eliminating the pointer indirections of traditional separate‑chaining tables. The design hinges on three tightly coupled components: a SIMD‑driven control‑byte array, a split hash (H1/H2), and a probing scheme that maximizes cache line utilization.

Control‑byte metadata

• Each slot has a 1‑byte entry in a separate array that is 16‑byte aligned.
• Bit patterns encode slot state:
  • 0xFF – EMPTY
  • 0x80 – DELETED (tombstone)
  • 0b0xxxxxxx – FULL, where the low 7 bits store the H2 fingerprint.
• The high bit instantly distinguishes occupied slots from empty or deleted ones, allowing the CPU to skip key comparisons when a miss occurs.

Split hash: H1 and H2

When a 64‑bit hash of a key is computed, Swiss Tables divide it into two parts. H1 consists of the top 57 bits and determines the initial bucket index (H1 % num_buckets). H2 is the low 7 bits and is stored in the control byte as a fingerprint. Because H2 has only 128 possible values, the probability of a false positive match on an occupied slot is roughly 1⁄128, meaning the map rarely touches the actual key memory on a miss.

SIMD vector probing

Lookup proceeds by loading 16 consecutive control bytes into a 128‑bit SIMD register (__m128i on SSE2). The target H2 fingerprint is broadcast across another register, and a single _mm_cmpeq_epi8 instruction produces a 16‑bit mask indicating which slots share the same fingerprint. The mask is examined with _mm_movemask_epi8 and trailing‑zero count to locate candidate slots, after which a full key equality test is performed only on those few candidates.

Probing strategy

• Groups of 16 slots are examined atomically; if none match and an EMPTY byte appears, the search terminates.
• When a group contains no EMPTY byte, the algorithm jumps to the next group using a triangular stride (group size × increasing step), which prevents secondary clustering while guaranteeing coverage of the entire table.

By combining a compact 1‑byte control array, a 7‑bit fingerprint, and SIMD‑accelerated batch comparisons, Swiss Tables achieve near‑zero key touches on misses and predictable low‑latency lookups, making them the de‑facto “modern king” of high‑performance hash maps in both Abseil and Rust.

Swiss Tables achieve high‑throughput lookups by separating metadata from the actual key/value storage and by exploiting the 128‑bit SIMD registers available in SSE2. Each bucket has a one‑byte control value: the most‑significant bit marks the slot as empty (0xFF) or deleted (0x80), while the lower seven bits store a fingerprint (H2) derived from the key’s 64‑bit hash. Because the fingerprint is only 7 bits, a false‑positive match occurs in roughly 1 in 128 cases, allowing the algorithm to avoid touching the full key unless the fingerprint matches.

During a probe the algorithm loads a contiguous group of 16 control bytes into an __m128i vector register. The target fingerprint is broadcast into another vector, and a single _mm_cmpeq_epi8 instruction produces a 16‑byte mask indicating which slots share the same H2 value. The mask is then collapsed to a 16‑bit integer with _mm_movemask_epi8, enabling the CPU to iterate only over the matching positions using a trailing‑zero count.

• Step 1 – Broadcast fingerprint: __m128i target = _mm_set1_epi8(h2_hash);
• Step 2 – Load control group: __m128i ctrl = _mm_loadu_si128((__m128i*)(ctrl_array + group_index));
• Step 3 – Parallel compare: __m128i matches = _mm_cmpeq_epi8(ctrl, target);
• Step 4 – Create bitmask: uint16_t mask = _mm_movemask_epi8(matches);
• Step 5 – Verify candidates: iterate over set bits, load the corresponding key, and perform a full equality test.

If the mask is zero, the group contains no matching fingerprints; the algorithm then advances to the next group using a triangular stride (e.g., 16, 48, 96 …) to avoid secondary clustering while guaranteeing coverage of the entire table.

Because the SIMD comparison touches only the 16‑byte metadata, a miss typically incurs a single cache‑line load and no memory accesses to the key/value array. This “zero key touches on misses” property dramatically reduces latency compared with traditional linear probing, where each slot requires a full key comparison and potentially several cache misses.

In practice, integrating this pattern into an existing hash table requires:

1. Aligning the control byte array to 16 bytes.
2. Ensuring the bucket count is a power of two so that bucket_mask = num_buckets‑1 can be used for wrap‑around.
3. Providing a fast 64‑bit hash function that yields both the bucket index (top 57 bits) and the 7‑bit fingerprint (bottom 7 bits).

Python’s built‑in mapping type was a major source of memory pressure in earlier releases because each entry stored a full PyObject* for the key, a pointer to the value, and a separate hash‑table slot containing a pointer to that entry. Starting with Python 3.6, the implementation was rewritten as a “compact dict” that separates the dense storage of keys/values from the sparse control array that drives probing. This design mirrors the open‑addressing strategies described for modern hash tables (e.g., Robin Hood hashing and Swiss Tables) and therefore inherits their cache‑locality benefits.

The compact dict consists of three logical components:

• Entry array: a contiguous block where each slot holds a (key, value) pair. Because the array is dense, sequential slots reside in the same 64‑byte cache line, allowing the CPU to fetch multiple pairs with a single memory access.
• Control byte array: a parallel byte‑wide metadata buffer (similar to the 1‑byte control bytes used by Swiss Tables). Each byte encodes whether the slot is empty, deleted, or occupied and stores a short fingerprint of the key’s hash, enabling fast SIMD‑style scans without touching the actual key objects on a miss.
• Insertion order list: the entry array is also ordered by insertion, which the interpreter exposes as the guaranteed iteration order of dict objects.

When a new key is inserted, the hash is split into two parts: the high bits select a bucket index in the control array, and the low bits become the fingerprint stored in the control byte. Probing proceeds by examining groups of control bytes (typically 16 at a time) and swapping entries only when the probe‑sequence length of the incoming key exceeds that of the resident key – the Robin Hood rule that flattens probe distribution.

Example:

d = {"alpha": 1, "beta": 2, "gamma": 3}
for k, v in d.items():
    print(k, v)

In this snippet the interpreter walks the dense entry array; each iteration touches only the cache line that already holds the next (key, value) pair, avoiding random heap dereferences. The compact layout reduces per‑entry overhead from roughly three pointers to a single combined slot plus one byte of metadata, which translates into a noticeable memory saving for large dictionaries while preserving the O(1) average‑case lookup performance expected from modern hash tables.