Hash Dispersion, Tombstone Deletion, Robin Hood Hashing & Cuckoo Eviction Networks

The Hash Table is the workhorse data structure of modern computing, underpinning language runtimes, in-memory databases, symbol tables, and key-value caches. By mapping a vast universe of arbitrary keys to a compact array of integer indices via hash functions, hash tables achieve average-case O(1) search, insertion, and deletion. However, the theoretical simplicity of hash tables conceals profound mathematical and microarchitectural challenges: collision clustering, tombstone accumulation, cache-line thrashing, and worst-case algorithmic degradation. Mastering advanced collision resolution—from probe sequence length equalization in Robin Hood hashing to dual-table cuckoo eviction networks and modern SIMD-accelerated SwissTables—is essential for high-performance systems engineering.

1. Mathematical Formalism of Hash Tables & Hash Dispersion#

A Hash Table implements the associative dictionary abstract data type, mapping keys from a large universe U to integer indices in a finite array table T[0 ... m - 1].

The Mapping Function#

The mapping is mediated by a mathematical Hash Function:

h: U → { 0, 1, 2, ..., m - 1 }.

The Pigeonhole Principle & Inevitability of Collisions:

In practical systems, the universe of possible keys U (e.g., all valid 64-bit integers, arbitrary UTF-8 strings, or serialized objects) is vastly larger than the table capacity m (|U| >> m).

By the Pigeonhole Principle, there must exist distinct keys k1 ≠ k2 such that:

h(k1) = h(k2).

Such an occurrence is defined as a Hash Collision. Designing a hash table requires two complementary engineering pillars:

1. Designing a high-dispersion hash function that scatters keys uniformly across { 0 ... m - 1 }.
2. Implementing an efficient collision resolution strategy when two keys map to the same slot.

The Simple Uniform Hashing Assumption (SUHA)#

Theoretical analysis of hash tables relies on the Simple Uniform Hashing Assumption:

Any given key k is equally likely to hash to any of the m slots in the table, completely independent of which slots other keys have hashed to:

P(h(k) = i) = 1 / m for all i in { 0 ... m - 1 }.

The Load Factor (α) represents the average occupancy density of the table:

α = n / m,

where n is the number of stored keys and m is the table capacity.

The Birthday Paradox in Hash Tables#

A common misconception is that collisions only become frequent when the load factor approaches 1.0 (when the table is nearly full).

The Birthday Paradox proves this intuition catastrophically wrong:

In a table with m slots, the expected number of random insertions before encountering the very first collision is:

E[Insertions until 1st Collision] ≈ √( (π · m) / 2 ).

For a hash table of capacity m = 1,000,000 slots:

E ≈ √( (3.14159 · 1,000,000) / 2 ) ≈ √1,570,796 ≈ 1,253 insertions!

After inserting just 1,253 keys into a million-slot table (a load factor of only α = 0.00125), the probability of at least one collision exceeds 50%! Collisions occur almost immediately, making robust collision handling mandatory.

Universal Hashing Families#

To defend against adversarial inputs that cause deliberate worst-case clustering, Carter and Wegman (1979) introduced Universal Hashing.

A finite collection of hash functions H mapping U to { 0 ... m - 1 } is 2-Universal if for any pair of distinct keys x ≠ y:

P_{h ~ H}( h(x) = h(y) ) <= 1 / m.

A classic universal hash family for integer keys uses a large prime p > |U|:

h_{a,b}(k) = ( (a · k + b) mod p ) mod m,

where a in { 1, 2, ..., p - 1 } and b in { 0, 1, ..., p - 1 } are chosen randomly at table initialization.

Because the attacker does not know which function was chosen from H, they cannot construct a deterministic collision sequence, guaranteeing average-case O(1) performance.

Cryptographic vs. Non-Cryptographic Hashes & HashDoS Attacks#

In high-throughput systems, cryptographic hashes (SHA-256, BLAKE3) are too slow, requiring 10 to 50 CPU cycles per byte. Non-cryptographic algorithms (MurmurHash3, xxHash, CityHash) achieve 10+ Gigabytes per second by utilizing fast bit shifts, rotations, and 64-bit integer multiplications.

The HashDoS Vulnerability:

In 2011, security researchers demonstrated that many web frameworks (Node.js, Python, PHP, Ruby) used vulnerable non-cryptographic hash functions with predictable seeds to parse HTTP POST parameters. Attackers generated millions of string keys that hashed to the exact same bucket, degrading hash lookups from O(1) to O(N). A tiny 2 Megabyte HTTP request forced servers to freeze at 100% CPU utilization for hours!

To prevent HashDoS, modern language runtimes (Rust, Python 3.4+) adopted SipHash-1-3 / SipHash-2-4, a pseudorandom keyed hash function that resists collision flooding while maintaining high performance.

2. Separate Chaining vs. Open Addressing Memory Topologies#

The two classic collision resolution paradigms diverge fundamentally in their memory layouts and cache interactions.

Separate Chaining#

In Separate Chaining, each slot T[i] in the primary table stores a pointer to an external auxiliary data structure (typically a singly linked list, or a small Red-Black tree for large buckets). When a collision occurs, the new key is prepended to the linked list.

Table T:
[ 0 ] ---> [ "apple", val ] -> NIL
[ 1 ] ---> NIL
[ 2 ] ---> [ "dog", val ] -> [ "cat", val ] -> [ "fox", val ] -> NIL
[ 3 ] ---> NIL

• Advantages:

- Simple implementation.

- Gracefully tolerates high load factors: the table continues functioning even when α > 1.0 (more elements than slots).

• Architectural Disadvantages:

- Cache Inefficiency: Linked list nodes are scattered across the heap. Traversing a bucket requires pointer chasing, incurring an L1/L2 cache miss on every node.

- Memory Overhead: On a 64-bit system, every node incurs 8 bytes of pointer overhead (next) plus heap allocator chunk padding. Storing 8-byte integers incurs 200% to 300% memory overhead.

Open Addressing#

In Open Addressing, all key-value pairs reside directly within the contiguous memory array T[0 ... m - 1]. There are zero heap pointers.

When a collision occurs at initial slot h(k), the algorithm systematically probes alternative slots according to an algorithmic sequence:

h(k, 0), h(k, 1), h(k, 2), ..., h(k, m - 1).

The load factor cannot exceed 1.0 (α <= 1.0). When α reaches a threshold (typically 0.70 to 0.85), the table must resize and rehash all keys.

Probing Strategies & Clustering Dynamics#

1. Linear Probing:

h(k, i) = (h(k) + i) mod m.

The algorithm steps sequentially through adjacent slots: h(k), h(k) + 1, h(k) + 2, ...

- Hardware Advantage: Extreme spatial locality! Sequential slots reside on the same 64-byte L1 cache line. A single DRAM fetch loads multiple probe candidates.

- Theoretical Disaster - Primary Clustering:

Occupied slots tend to coalesce into long contiguous blocks called clusters.

Once a cluster forms, any key that hashes to ANY slot within the cluster must walk to the very end of the cluster, extending it further. The probability of a cluster growing is proportional to its size, creating a runaway snowball effect!

Under linear probing, the expected number of probes for an unsuccessful search scales as:

E[Probes] ≈ (1/2) · [ 1 + 1 / (1 - α)^2 ].

At α = 0.90, an unsuccessful search requires an average of ~50 probes!

1. Quadratic Probing:

h(k, i) = (h(k) + c1 · i + c2 · i^2) mod m.

The step size increases quadratically: +1, +4, +9, +16, ...

- Advantage: Eliminates primary clustering because adjacent slots do not form solid walls.

- Weakness - Secondary Clustering:

All keys that share the exact same initial hash h(k) trace the exact same probe trajectory through the table.

1. Double Hashing:

h(k, i) = (h1(k) + i · h2(k)) mod m.

Uses a secondary hash function h2(k) as the step size (where h2(k) must be relatively prime to m).

- Advantage: Two keys with the same initial hash h1(k) will have different step sizes h2(k), scattering probes across entirely different permutations and eliminating secondary clustering.

- Disadvantage: Loses cache line spatial locality because steps jump to arbitrary memory locations.

3. The Tombstone Deletion Dilemma & High-Load Degradation#

In open addressing, deleting a key is surprisingly treacherous.

The Search Termination Invariant#

In open addressing, a search for key k proceeds through its probe sequence until:

1. Key k is found (Search Hit).
2. An empty slot (None) is encountered (Search Miss).

Why does hitting an empty slot prove the key does not exist? Because if key k had been inserted previously, it would have claimed that empty slot! Therefore, finding an empty slot is the mathematical proof that the key is absent.

Why Naive Deletion Destroys the Table#

Suppose keys A, B, and C all hash to slot 3:

• Key A is inserted at slot 3.
• Key B collides at slot 3, probes to slot 4, and is placed at slot 4.
• Key C collides at slots 3 and 4, probes to slot 5, and is placed at slot 5.

Now, delete Key B by simply setting slot 4 to None:

Table: [ Slot 3: A ][ Slot 4: None ][ Slot 5: C ]

Next, search for Key C:

• Probes slot 3: finds A (not C).
• Probes slot 4: encounters None!
• The algorithm terminates and reports: "Key C NOT FOUND"!

Setting slot 4 to None severed the probe chain, creating an orphaned entry. Key C exists in the table at slot 5, but is permanently invisible to searches!

The Tombstone Solution & Its Hidden Cost#

To preserve the search invariant, deletions in open addressing do not clear the slot. Instead, they mark the slot with a special sentinel called a Tombstone (or DELETED):

• Searches treat a Tombstone as OCCUPIED: the search continues past the tombstone down the probe sequence.
• Insertions treat a Tombstone as FREE: a new key may claim and overwrite the tombstone slot.

The Tombstone Accumulation Crisis:

In systems with heavy insert-and-delete churn (e.g., session caches):

• Over time, almost every slot in the table becomes populated with tombstones.
• While the number of active elements n may remain small (low real load factor α), searches for absent keys must traverse dozens or hundreds of tombstones before hitting a true None slot.
• Lookup latency collapses from O(1) to O(N).

Remediation: The table must periodically trigger an expensive Rehash / Compaction pass to purge tombstones, or implement Robin Hood backward-shift deletion.

4. Robin Hood Hashing: Equalizing Probe Sequence Lengths (PSL)#

Introduced by Pedro Celis, Per-Åke Larson, and J. Ian Munro in 1985, Robin Hood Hashing is an open-addressing technique that solves the variance and cluster degradation of linear probing:

"Take from the rich and give to the poor."

Probe Sequence Length (PSL)#

For any key k residing at slot index j in a table of capacity m:

Its Probe Sequence Length (PSL) is the physical distance between its current slot j and its ideal home hash slot h(k):

PSL(k) = (j - h(k) + m) mod m.

• A key with PSL = 0 is "Rich": it occupies its ideal, preferred home slot.
• A key with PSL = 5 is "Poor": it was displaced 5 slots down the table due to collisions.

The Robin Hood Invariant & Insertion Algorithm#

When inserting key k with value v:

1. Initialize incoming_key = k, incoming_val = v, and incoming_psl = 0.
2. Compute initial slot idx = h(k) mod m.
3. Loop through probe slots:

- Case A (Slot is Empty): Place incoming_key and incoming_psl in the slot. Insertion terminates!

- Case B (Slot contains Matching Key): Update the existing value. Insertion terminates!

- Case C (Slot contains Another Key with resident_psl):

Compare the two probe sequence lengths:

- If incoming_psl <= resident_psl: The incoming key is "richer" (or equal). It yields precedence. Increment incoming_psl += 1, advance idx = (idx + 1) mod m, and continue probing.

- If incoming_psl > resident_psl: THE ROBIN HOOD STEAL!

The incoming key has traveled farther from home than the resident key. The incoming key is "poorer"!

We evict the resident key:

Swap (incoming_key, incoming_psl) with the resident slot data.

The evicted resident now becomes the new incoming key! We continue probing with this newly evicted key (incrementing its PSL) until it finds a home.

+----------------------------------------------------------------------------------------------------+
|                                    ROBIN HOOD EVICTION MECHANISM                                   |
+----------------------------------------------------------------------------------------------------+
  Incoming Key: 'Delta' (PSL = 3, "Poor") arrives at Slot 5.
  Resident Key: 'Beta'  (PSL = 1, "Rich") currently occupies Slot 5.

  Condition: incoming_psl (3) > resident_psl (1) ==> TRUE!

  Action: SWAP!
  1. Slot 5 is assigned to 'Delta' with PSL = 3.
  2. 'Beta' is evicted and becomes the incoming key with PSL = 1 + 1 = 2.
  3. Probing continues down Slot 6 to find a home for 'Beta'.
+----------------------------------------------------------------------------------------------------+

Why Robin Hood Hashing is Revolutionary#

1. Variance Equalization:

Standard linear probing produces highly skewed probe distributions: 90% of keys have PSL = 0, while unlucky keys suffer PSL = 40.

Robin Hood hashing violently flattens the distribution: all keys are clustered tightly around the mean PSL (e.g., PSL in { 1, 2, 3 }).

1. Early Exit on Search Misses:

In standard linear probing, an unsuccessful search MUST probe until it hits an empty slot (None).

In Robin Hood hashing, when searching for key k with current search probe distance curr_psl:

If the slot contains a resident key with resident_psl < curr_psl:

THE SEARCH CAN TERMINATE IMMEDIATELY AS A MISS!

Why? Because if key k existed in the table, Robin Hood's insertion rule would have swapped key k into that slot when its PSL exceeded the resident's PSL! The presence of a richer resident is mathematical proof that key k is absent!

1. Backward-Shift Deletion (Zero Tombstones!):

When a key at slot j is deleted, Robin Hood hashing does not insert a tombstone. Instead, it inspects slot j + 1. If the key at j + 1 has PSL > 0, it shifts that key backward into slot j and decrements its PSL. This shift continues down the cluster until an empty slot or a key with PSL = 0 is reached, leaving the table 100% clean of tombstones!

5. Cuckoo Hashing: Guaranteed Worst-Case O(1) Lookups#

While Robin Hood hashing minimizes search variance, lookup operations can still require multiple probes under high load.

Introduced by Rasmus Pagh and Flemming Friche Rodler in 2001, Cuckoo Hashing achieves the ultimate theoretical objective of dictionary design:

Strictly Worst-Case O(1) Lookup Time.

The Dual-Table Architecture#

In standard Cuckoo Hashing:

• The data structure maintains two separate tables T1 and T2, each of size m.
• Two independent, uncorrelated hash functions are used: h1 for T1, and h2 for T2.

The Fundamental Cuckoo Invariant:

For ANY key k stored in the data structure, k is GUARANTEED to reside in either:

Slot T1[h1(k)] OR Slot T2[h2(k)].

Key k can NEVER reside in any other slot in the entire system!

The Worst-Case O(1) Search & Delete#

Because a key can only exist in two predetermined locations, looking up a key requires evaluating h1(k) and h2(k) and checking exactly two memory addresses:

def lookup(key):
    if T1[h1(key)] == key:
        return T1[h1(key)].value
    if T2[h2(key)] == key:
        return T2[h2(key)].value
    return None  # Guaranteed O(1) Worst-Case! Exactly 2 memory accesses!

Deletions are equally trivial: check both locations and clear the matching slot. Zero tombstones, zero shifting, zero rebalancing!

The Cuckoo Bird Eviction Network#

The magic and complexity of Cuckoo Hashing resides in its Insertion Algorithm, inspired by the cuckoo bird (which lays its eggs in another bird's nest, pushing the existing eggs out):

1. To insert key k:

Attempt to place k into its primary slot T1[h1(k)].

1. If T1[h1(k)] is empty: place k and terminate.
2. If T1[h1(k)] is occupied by an existing key x:

- Evict key x from T1[h1(k)].

- Place key k into T1[h1(k)].

- Key x must now be relocated to its ALTERNATIVE location in Table 2: slot T2[h2(x)].

1. If T2[h2(x)] is empty: place x and terminate.
2. If T2[h2(x)] is occupied by key y:

- Evict key y from T2[h2(x)].

- Place key x into T2[h2(x)].

- Now key y must be relocated to its alternative location in Table 1: T1[h1(y)].

1. Continue this eviction cascade iteratively.

+----------------------------------------------------------------------------------------------------+
|                                    CUCKOO EVICTION CASCADE                                         |
+----------------------------------------------------------------------------------------------------+
  Insert Key K ---> Claims T1[h1(K)]
                         |
                         v (Kicks out Key X)
                    Key X moves to T2[h2(X)]
                         |
                         v (Kicks out Key Y)
                    Key Y moves to T1[h1(Y)]
                         |
                         v (Finds Empty Slot!) ---> Cascade Terminates Successfully!
+----------------------------------------------------------------------------------------------------+

Eviction Cycles & Rehashing#

What happens if the eviction cascade enters an infinite loop (a cycle in the Cuckoo Bipartite Graph)?

If an eviction loop is detected (e.g., cascade length exceeds MAX_STEPS ≈ 2 · log(N)):

The table is full or in a deadlocked cycle.

The data structure triggers an emergency Rehash:

1. Select two brand-new random hash functions h1 and h2 from a universal family.
2. If load factor α > 0.50, double table capacity m.
3. Re-insert all existing keys into the fresh tables.

Pagh and Rodler proved that as long as the load factor α < 0.50, the probability of an insertion triggering a rehash is O(1 / n), and the amortized insertion time is strictly O(1) Amortized.

6. Production Systems, Google SwissTable & SIMD Hash Probing#

In modern software systems, Google's SwissTable (absl::flat_hash_map, adopted by the Rust standard library as hashbrown and CPython 3.6+ as its dictionary layout) represents the cutting edge of industrial hash table engineering.

The Problem with Traditional Open Addressing#

Traditional open addressing inspects one slot at a time. Each probe requires reading the key, comparing hashes, and potentially reading a 32-byte or 64-byte key payload from memory, causing cache misses.

The SwissTable Architectural Breakthrough#

SwissTable decouples metadata from key-value payloads:

1. Control Byte Array: A dense, separate array of 1-byte control markers corresponding to each slot in the table.

Each 8-bit control byte stores:

- 0b11111111 (0xFF): Empty slot

- 0b11111110 (0xFE): Deleted slot (Tombstone)

- 0b0xxxxxxx: Occupied slot! The 7 lowest bits store the H2 Hash Fingerprint (the upper 7 bits of the key's 64-bit hash code).

1. Key-Value Slots Array: Stores the actual keys and values.

Control Bytes (16 bytes = 128 bits):
[ 0xFF ][ 0x5A ][ 0xFF ][ 0x12 ][ 0xFF ][ 0xFF ][ 0x5A ][ 0xFF ] ... (16 slots in 1 vector!)
                |
                v  (Single SIMD Instruction: _mm_cmpeq_epi8)
Matches 0x5A:  [ 0 ][ 1 ][ 0 ][ 0 ][ 0 ][ 0 ][ 1 ][ 0 ] ... (Instant bitmask!)

16-Way SIMD Parallel Probing#

When looking up key k:

1. Compute 64-bit hash: hash = H(k).
2. Extract H1 (lower 57 bits): determines the 16-slot group index.
3. Extract H2 (upper 7 bits): a 7-bit fingerprint (e.g., 0x5A).
4. SwissTable loads 16 consecutive control bytes into a 128-bit SSE2/NEON register in a single instruction.
5. It executes a single SIMD vector equality instruction (_mm_cmpeq_epi8 on x86, or vceqq_u8 on ARM), comparing all 16 slots against fingerprint 0x5A simultaneously in 1 clock cycle!
6. It extracts a 16-bit bitmask via _mm_movemask_epi8.

Result:

In exactly 2 CPU clock cycles, SwissTable filters out 15 mismatched or empty slots in parallel! The CPU only reads the full key payload from the main array for the rare slots that match the 7-bit fingerprint, eliminating over 99% of memory bus overhead and cache misses.

7. Common Pitfalls & Misconceptions in Hash Table Engineering#

Engineers frequently encounter performance bugs and vulnerabilities when deploying hash tables.

Pitfall 1: Unmixed Hash Codes with Power-of-Two Tables#

To avoid expensive integer division (hash % capacity), tables with power-of-two capacities (m = 2^k) compute indices using bitwise masking:

index = hash & (capacity - 1).

If a key's hash function has poor entropy in its lowest bits (e.g., memory pointers aligned to 8 or 16 bytes, where the lowest 3 or 4 bits are ALWAYS 0000):

All keys will map exclusively to indices that are multiples of 8 or 16! Over 85% of table slots sit completely empty while the remaining slots suffer catastrophic collision chaining.

Solution: Always pass raw keys through a bit avalanche mixer (e.g., the Murmur3 64-bit finalizer) to scramble upper and lower bits thoroughly.

Pitfall 2: Mutating Keys After Insertion#

A widespread bug in object-oriented languages (Java, Python, C#):

An object is inserted into a HashSet or HashMap. Later, a developer modifies a field in that object that participates in its equals() or hashCode() method.

Consequence:

The object's hash code has changed, but it remains sitting in the slot computed from its OLD hash code!

When the program searches for the object using map.contains(obj), the lookup evaluates the NEW hash code, looks in the wrong bucket, and reports that the object does not exist. The mutated object becomes a Memory Leak Zombie: it can never be found, updated, or removed!

Pitfall 3: Ignoring High Load Factor Thresholds#

In linear probing, allowing the load factor α to climb past 0.80 causes average search times to skyrocket exponentially. Always tune resize thresholds to trigger reallocations at α ≈ 0.70 to 0.75.

8. Comprehensive Checkpoint Practice Problems & Complete Step-by-Step Solutions#

Mastery of hash dispersion, Robin Hood swaps, and cuckoo networks requires solving rigorous mechanical trace problems.

Problem 1 (Linear Probing, Quadratic Probing & Double Hashing Collision Trace):

A hash table of capacity m = 11 uses zero-indexed slots (indices 0 through 10).

The primary hash function is:

h1(k) = k mod 11.

The secondary hash function (for double hashing) is:

h2(k) = 1 + (k mod 7).

Trace the insertion of the following sequence of integer keys into an initially empty table under three separate collision strategies:

Keys = [ 10, 22, 31, 4, 15, 28 ]

1. Strategy A: Linear Probing where h(k, i) = (h1(k) + i) mod 11.
2. Strategy B: Quadratic Probing where h(k, i) = (h1(k) + i^2) mod 11.
3. Strategy C: Double Hashing where h(k, i) = (h1(k) + i · h2(k)) mod 11.

For each strategy, show the step-by-step probe sequence for each key, the number of collisions encountered, and the final 11-slot table layout.

Solution:

Strategy A: Linear Probing Trace (h(k, i) = (k mod 11 + i) mod 11)

• Key 10: h1(10) = 10 mod 11 = 10. Slot 10 is empty. Placed at Slot 10. (0 collisions)
• Key 22: h1(22) = 22 mod 11 = 0. Slot 0 is empty. Placed at Slot 0. (0 collisions)
• Key 31: h1(31) = 31 mod 11 = 9. Slot 9 is empty. Placed at Slot 9. (0 collisions)
• Key 4: h1(4) = 4 mod 11 = 4. Slot 4 is empty. Placed at Slot 4. (0 collisions)
• Key 15: h1(15) = 15 mod 11 = 4.

- Probe 0 (i=0): Slot 4 is occupied by [4]. Collision 1!

- Probe 1 (i=1): Slot (4 + 1) mod 11 = 5 is empty. Placed at Slot 5. (1 collision)

• Key 28: h1(28) = 28 mod 11 = 6.

- Probe 0 (i=0): Slot 6 is empty. Placed at Slot 6. (0 collisions)

Final Linear Probing Table:

[ 22, None, None, None, 4, 15, 28, None, None, 31, 10 ]

Total collisions = 1 collision.

Strategy B: Quadratic Probing Trace (h(k, i) = (k mod 11 + i^2) mod 11)

• Keys 10, 22, 31, 4: Placed at slots 10, 0, 9, 4 respectively (0 collisions).
• Key 15: h1(15) = 4.

- Probe 0 (i=0): Slot 4 occupied by [4]. Collision 1!

- Probe 1 (i=1): Slot (4 + 1^2) mod 11 = 5 is empty. Placed at Slot 5. (1 collision)

• Key 28: h1(28) = 6. Slot 6 empty. Placed at Slot 6. (0 collisions)

Final Quadratic Probing Table:

[ 22, None, None, None, 4, 15, 28, None, None, 31, 10 ]

(Note: Identical here because i=1 was sufficient).

Strategy C: Double Hashing Trace (h(k, i) = (h1(k) + i · h2(k)) mod 11)

• Keys 10, 22, 31, 4: Placed at slots 10, 0, 9, 4 respectively (0 collisions).
• Key 15:

h1(15) = 15 mod 11 = 4.

h2(15) = 1 + (15 mod 7) = 1 + 1 = 2 (step size = 2).

- Probe 0 (i=0): Slot 4 occupied by [4]. Collision 1!

- Probe 1 (i=1): Slot (4 + 1 · 2) mod 11 = 6 is empty.

Placed at Slot 6! (1 collision).

• Key 28:

h1(28) = 28 mod 11 = 6.

h2(28) = 1 + (28 mod 7) = 1 + 0 = 1 (step size = 1).

- Probe 0 (i=0): Slot 6 is occupied by [15]! Collision 1!

- Probe 1 (i=1): Slot (6 + 1 · 1) mod 11 = 7 is empty.

Placed at Slot 7! (1 collision).

Final Double Hashing Table:

[ 22, None, None, None, 4, None, 15, 28, None, 31, 10 ]

Total collisions = 2 collisions.

Problem 2 (Robin Hood Hashing Step-by-Step Eviction Trace):

A Robin Hood hash table has capacity m = 8 (slots 0 through 7).

Initial hash function: h(k) = k mod 8.

Current state of the table:

• Slot 0: [ Key 16, PSL = 0 ] (since 16 mod 8 = 0)
• Slot 1: [ Key 8, PSL = 1 ] (since 8 mod 8 = 0, distance = 1)
• Slot 2: [ Key 24, PSL = 2 ] (since 24 mod 8 = 0, distance = 2)
• Slot 3: Empty
• Slots 4, 5, 6, 7: Empty

Now, an engineer inserts Key 9 (where 9 mod 8 = 1):

1. Trace the insertion of Key 9 step-by-step: record each probed slot, compare PSLs, show any Robin Hood eviction swaps, and follow displaced keys until the table stabilizes.
2. State the final contents and PSL of every slot in the table.
3. Show how a search for absent Key 17 (where 17 mod 8 = 1) executes and demonstrate the Early-Exit condition.

Solution:

Step 1: Insertion Trace for Key 9

Key 9 has ideal home: h(9) = 9 mod 8 = 1.

Incoming packet: (Key = 9, PSL = 0).

• Step 1 (Inspect Slot 1):

- Current Slot: Slot 1.

- Resident: [ Key 8, PSL = 1 ].

- Compare PSLs: incoming_psl (0) <= resident_psl (1).

- The incoming key is RICHER (or equal). It does not steal!

- Key 9 yields. Advance probe: incoming_psl = 0 + 1 = 1. Advance slot to Slot 2.

• Step 2 (Inspect Slot 2):

- Current Slot: Slot 2.

- Resident: [ Key 24, PSL = 2 ].

- Compare PSLs: incoming_psl (1) <= resident_psl (2).

- Key 9 is still RICHER. It yields. Advance probe: incoming_psl = 1 + 1 = 2. Advance slot to Slot 3.

• Step 3 (Inspect Slot 3):

- Current Slot: Slot 3.

- Resident: Empty.

- Slot 3 is empty! Place incoming key:

Slot 3 becomes [ Key 9, PSL = 2 ].

- Insertion terminates cleanly with zero evictions!

Now consider an alternative insert demonstrating a Robin Hood swap:

Suppose we now insert Key 33 (where 33 mod 8 = 1).

Incoming packet: (Key = 33, PSL = 0).

• At Slot 1: Resident [8, PSL = 1]. Incoming (PSL 0) <= Resident (PSL 1) -> Yields, incoming becomes PSL = 1.
• At Slot 2: Resident [24, PSL = 2]. Incoming (PSL 1) <= Resident (PSL 2) -> Yields, incoming becomes PSL = 2.
• At Slot 3: Resident [9, PSL = 2]. Incoming (PSL 2) <= Resident (PSL 2) -> Yields, incoming becomes PSL = 3.
• At Slot 4: Slot 4 is Empty! Placed at Slot 4 with PSL = 3.

Step 2: Table State After Key 9 Insertion

• Slot 0: [ Key 16, PSL = 0 ]
• Slot 1: [ Key 8, PSL = 1 ]
• Slot 2: [ Key 24, PSL = 2 ]
• Slot 3: [ Key 9, PSL = 2 ]
• Slots 4..7: Empty

Step 3: Early-Exit Search Trace for Absent Key 17

Search for Key 17:

Ideal home: h(17) = 17 mod 8 = 1.

Start search at Slot 1 with search_psl = 0.

• Probe 1 (Slot 1):

Resident is [Key 8, PSL = 1].

Key 8 ≠ 17.

Compare: search_psl (0) <= resident_psl (1). Continue search.

Increment search_psl = 1. Advance to Slot 2.

• Probe 2 (Slot 2):

Resident is [Key 24, PSL = 2].

Key 24 ≠ 17.

Compare: search_psl (1) <= resident_psl (2). Continue search.

Increment search_psl = 2. Advance to Slot 3.

• Probe 3 (Slot 3):

Resident is [Key 9, PSL = 2].

Key 9 ≠ 17.

Compare: search_psl (2) == resident_psl (2). Continue search.

Increment search_psl = 3. Advance to Slot 4.

• Probe 4 (Slot 4):

Slot 4 is Empty!

Search terminates: Key 17 NOT FOUND.

Early Exit Example:

If we had probed a slot where search_psl > resident_psl (e.g. searching for a key that started at 0 and reached PSL 3 at Slot 3 where resident had PSL 2), the search would have terminated immediately at that slot without ever checking Slot 4!

Problem 3 (Cuckoo Hashing Eviction Cascade & Cycle Detection):

A Cuckoo hash table maintains two tables, T1 and T2, each with m = 5 slots (indices 0 to 4).

Hash functions:

• h1(k) = k mod 5
• h2(k) = floor(k / 5) mod 5

Currently, the tables store the following keys:

• Table T1:

- T1[1] = Key 11 (h1(11) = 1)

- T1[2] = Key 22 (h1(22) = 2)

- T1[3] = Key 13 (h1(13) = 3)

- T1[0], T1[4] = Empty

• Table T2:

- T2[1] = Key 6 (h2(6) = floor(6/5) mod 5 = 1)

- T2[3] = Key 18 (h2(18) = floor(18/5) mod 5 = 3)

- T2[0], T2[2], T2[4] = Empty

Now, an engineer inserts Key 21:

1. Calculate h1(21) and h2(21).
2. Trace the entire cuckoo eviction cascade step-by-step: show each eviction, the displaced key, its alternate table and hash location, until an empty slot is reached.
3. Draw the final contents of both tables T1 and T2.

Solution:

Step 1: Hash Calculation for Key 21

• h1(21) = 21 mod 5 = 1.
• h2(21) = floor(21 / 5) mod 5 = 4 mod 5 = 4.

Step 2: Trace the Eviction Cascade

• Step 1: Insert Key 21 into Table T1 at slot h1(21) = 1.

- T1[1] is currently OCCUPIED by Key 11!

- Cuckoo Eviction!

- Key 21 claims T1[1]: T1[1] = 21.

- Key 11 is evicted from T1!

• Step 2: Relocate evicted Key 11 to Table T2.

- Compute alternate location: h2(11) = floor(11 / 5) mod 5 = 2 mod 5 = 2.

- Inspect T2[2]:

- T2[2] is currently EMPTY!

- Place Key 11 into T2[2]: T2[2] = 11.

- The eviction cascade terminates successfully in just 2 steps!

Step 3: Final Tables State

Table T1:

• T1[0]: Empty
• T1[1]: Key 21 (newly placed)
• T1[2]: Key 22
• T1[3]: Key 13
• T1[4]: Empty

Table T2:

• T2[0]: Empty
• T2[1]: Key 6
• T2[2]: Key 11 (relocated from T1[1])
• T2[3]: Key 18
• T2[4]: Empty

Lookup Verification for Key 11:

• Check T1[h1(11)] = T1[1] -> holds Key 21 (mismatch).
• Check T2[h2(11)] = T2[2] -> FOUND Key 11!

Lookup resolves in exactly 2 memory inspections.

Problem 4 (Google SwissTable SIMD Control Byte & Bitmask Extraction):

A Google SwissTable implementation uses 16-slot group probing.

A 64-bit integer key hashes to:

Hash = 0xA73F_9B14_2C80_5E17 (hexadecimal).

• The table extracts the lower 57 bits for Group Indexing and the upper 7 bits for the H2 Fingerprint:

H2 = (Hash >> 57) & 0x7F.

1. Calculate the exact numerical 7-bit H2 fingerprint (in both binary and hexadecimal).
2. The 16 control bytes of the target group in memory currently contain the following hexadecimal values:

Group = [ 0xFF, 0x12, 0x53, 0xFF, 0x53, 0x7E, 0x00, 0x53, 0xFF, 0x2B, 0x53, 0xFE, 0x53, 0x10, 0xFF, 0x53 ]

(Note: 0xFF = Empty, 0xFE = Tombstone, values <= 0x7F = Valid H2 fingerprints).

1. The CPU executes the 128-bit SIMD instruction _mm_cmpeq_epi8 comparing all 16 bytes against the target H2 fingerprint, followed by _mm_movemask_epi8 to extract a 16-bit integer bitmask.

- Determine which slot indices match.

- Write the exact 16-bit binary integer bitmask produced by _mm_movemask_epi8.

- Explain how many full-key equality comparisons the CPU must perform.

Solution:

Step 1: Calculate H2 Fingerprint

Given Hash = 0xA73F_9B14_2C80_5E17.

Convert top byte 0xA7 to binary:

0xA7 = 1010 0111 (8 bits).

Shift right by 57 bits extracts the top 7 bits:

Bits 63..57:

Top 8 bits: bit 63 is 1, bit 62 is 0, bit 61 is 1, bit 60 is 0, bit 59 is 0, bit 58 is 1, bit 57 is 1.

The 7-bit slice is 101 0011 (binary).

Convert 101 0011 to hexadecimal:

0101 0011 = 0x53.

Target H2 Fingerprint = 0x53 (decimal 83).

Step 2: Evaluate Matching Slots in the 16-Byte Group

Target fingerprint: 0x53.

Compare each index 0 through 15 against 0x53:

• Slot 0: 0xFF (Empty) -> No
• Slot 1: 0x12 -> No
• Slot 2: 0x53 -> MATCH!
• Slot 3: 0xFF (Empty) -> No
• Slot 4: 0x53 -> MATCH!
• Slot 5: 0x7E -> No
• Slot 6: 0x00 -> No
• Slot 7: 0x53 -> MATCH!
• Slot 8: 0xFF (Empty) -> No
• Slot 9: 0x2B -> No
• Slot 10: 0x53 -> MATCH!
• Slot 11: 0xFE (Tombstone) -> No
• Slot 12: 0x53 -> MATCH!
• Slot 13: 0x10 -> No
• Slot 14: 0xFF (Empty) -> No
• Slot 15: 0x53 -> MATCH!

Matching slot indices: { 2, 4, 7, 10, 12, 15 }.

Step 3: 16-Bit SIMD Bitmask Generation

_mm_cmpeq_epi8 outputs 0xFF for matching bytes and 0x00 for non-matching bytes.

_mm_movemask_epi8 extracts the most significant bit (bit 7) of each of the 16 bytes into a 16-bit unsigned integer, where bit k corresponds to slot k:

• Bit 0: 0
• Bit 1: 0
• Bit 2: 1
• Bit 3: 0
• Bit 4: 1
• Bit 5: 0
• Bit 6: 0
• Bit 7: 1
• Bit 8: 0
• Bit 9: 0
• Bit 10: 1
• Bit 11: 0
• Bit 12: 1
• Bit 13: 0
• Bit 14: 0
• Bit 15: 1

Binary bitmask (bit 15 to bit 0):

1001 0100 1001 0100 (binary).

Hexadecimal bitmask: 0x9494.

Performance Conclusion:

Out of 16 slots, 10 slots (empty, deleted, or mismatched) were eliminated in 1 CPU cycle!

The CPU only needs to perform full 64-bit key comparisons on the 6 candidate slots {2, 4, 7, 10, 12, 15}, iterating through them using the hardware instruction _tzcnt_u32 (count trailing zeroes) to find the first match in nanoseconds.