Cuckoo Hashing

Worked Example

Let's trace the insertion of keys [0, 5, 10, 15] into two tables of size 5, using hash functions:

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

1. Insert 0: h1(0) = 0. Table 1, index 0 is empty. Place 0.
2. Insert 5: h1(5) = 0. Table 1, index 0 contains 0. Evict 0 and place 5 in Table 1, index 0.
   Re-insert 0: h2(0) = 0. Table 2, index 0 is empty. Place 0.
3. Insert 10: h1(10) = 0. Table 1, index 0 contains 5. Evict 5 and place 10 in Table 1, index 0.
   Re-insert 5: h2(5) = 1. Table 2, index 1 is empty. Place 5.
4. Insert 15: h1(15) = 0. Table 1, index 0 contains 10. Evict 10 and place 15 in Table 1, index 0.
   Re-insert 10: h2(10) = 2. Table 2, index 2 is empty. Place 10.

All 4 keys are successfully placed without exceeding the maximum displacement limit.

Experiment

Explore different insertion sequences to see how cuckoo hashing handles evictions and detects cycles:https://riano.app/module/cuckoo-hashing

1. Select the Evictions option from the Keys dropdown and click Step to observe the chained displacements described in the worked example.
2. Select the Impossible pair option and step through the insertions. Observe how keys 0, 25, and 50 all share the exact same hash locations: h1(x) = 0 and h2(x) = 0.
3. Notice that after reaching the displacement limit (10 steps), the status changes to Rehash required and the unplaceable key is moved to the overflow pool.

Limitations

This module implements a bounded cuckoo hash table insertion. It caps displacements during a single insertion at 10 to prevent infinite loops when a cycle is detected. In a real-world implementation, detecting a cycle or exceeding a displacement threshold triggers a rehash, where new hash functions are chosen and all existing keys are re-inserted into newly sized tables.

Cuckoo hashing guarantees O(1) worst-case lookup time because a key can only be in one of two locations. However, insertion time is amortized expected O(1), and degrades significantly if the load factor (ratio of keys to table slots) approaches 50%. The "Impossible pair" example demonstrates a boundary case where a cycle of three keys maps to the same two slots, making placement impossible regardless of the table's overall empty space.

References

Pagh, R., & Rodler, F. F. (2001). Cuckoo Hashing. BRICS Report Series.
https://www.brics.dk/RS/01/32/BRICS-RS-01-32.pdf
This foundational paper introduces the cuckoo hashing algorithm, proving its worst-case constant lookup time and amortized constant insertion time under typical load factors.