◄ WORLD V · SONNY 5DART 549 · a helldive at the table

THE CUCKOO HASHING two nests, and you kick out the occupant

Guarantee O(1) worst-case lookup: every key has exactly two possible slots (via two hashes), so a lookup checks just those two — never more. On insert, if both are full, evict an occupant to its other nest (like a cuckoo chick), and repeat; rare cycles trigger a rehash. Here key 42 has nests 9 and 6; a reader checks exactly two places and stops.

THE TECHNIQUE key lives in slot h₁(k) or h₂(k) — lookup checks 2

The demo shows key 42’s two nests and that lookup is a fixed 2 checks: live demo







  
HISTORY & CREDIT Pagh & Rodler · 2001

  
“Cuckoo inserts are O(1).” — lookups are worst-case O(1); inserts are expected O(1) but can cascade and occasionally force a rehash. cited

  
two nests · h₁(k) and h₂(k) — a key is in one of them, always.
the kick · insert evicts the occupant to its other nest; cycles → rehash.
2001 · Rasmus Pagh & Flemming Friche Rodler — “Cuckoo hashing.”

  
Worst-case two reads, forever. data structure






  
RECOMMEND FOR I-13 the two nests, on the compiler

  
On i-13, key 42 hashes to nests 9 and 6; a lookup is a constant 2 checks:

  
$ i13 run hs_cuckoo.i13
RUN OK · 30 step(s) · peak stack 3
slotA         = 9   -- h1(42)
slotB         = 6   -- h2(42)
two_choices   = 1
lookup_checks = 2   -- worst case, always

  
Recommend as a NULL — a resource guarantee (B40) + a pinned map (B39). Worst-case-two-reads is an amortized/worst-case cost bound; which nest a key occupies is a coordinate-dependent eviction history (B44), and lookups return the same map as any table. A cost property, not a keeper. NULL — two nests.