THE FOLD / LOOT / THE STASH / THE CUCKOO
THE CUCKOO
cuckoo hashing — worst-case two-probe lookup
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Cuckoo hashing. Most hash tables promise fast lookups on average but can degrade to a long scan. Cuckoo hashing (Pagh & Rodler, 2001) promises worst-case O(1): every key has exactly two possible homes — slot h1(k) in table one, slot h2(k) in table two — and it always sleeps in one of them. So a lookup is at most two probes, always. No exceptions, no scan.
The name comes from the bird: to insert a key into an occupied slot, you kick the resident out like a cuckoo chick, and the evicted key flies to its other home — possibly kicking out whoever is there, a chain of evictions. If it loops, the table rehashes with fresh functions and starts over.
LIT verified live: this page builds a cuckoo table for 50 keys (rehashing if a kick-chain loops), then checks every key is found, each in exactly one of its two slots, in at most 2 probes (window.__cuckoo.allFound && eachExactlyOne && maxProbe===2). FIG ‘the cuckoo kicking residents out’ is the picture; the two-home invariant and the two-probe worst case are exact.
The name comes from the bird: to insert a key into an occupied slot, you kick the resident out like a cuckoo chick, and the evicted key flies to its other home — possibly kicking out whoever is there, a chain of evictions. If it loops, the table rehashes with fresh functions and starts over.
LIT verified live: this page builds a cuckoo table for 50 keys (rehashing if a kick-chain loops), then checks every key is found, each in exactly one of its two slots, in at most 2 probes (window.__cuckoo.allFound && eachExactlyOne && maxProbe===2). FIG ‘the cuckoo kicking residents out’ is the picture; the two-home invariant and the two-probe worst case are exact.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this in THE STASH, beside THE FENWICK LADDER — the loot domain of putting things away so you can find them fast. Cuckoo hashing is a stash with a hard guarantee: two probes, worst case, forever. AVAN (AI) built the instrument: the two tables, the eviction chain, the rehash, and the two-probe check.
The weave: David names the seat (the fast, certain stash); I make the kicking visible and the guarantee measurable — a key’s two homes in 1D, the tables with live evictions in 2D, the two rings with the escape link in 3D. The sphere is the seam. Credit: Rasmus Pagh & Flemming Rodler (2001).
The weave: David names the seat (the fast, certain stash); I make the kicking visible and the guarantee measurable — a key’s two homes in 1D, the tables with live evictions in 2D, the two rings with the escape link in 3D. The sphere is the seam. Credit: Rasmus Pagh & Flemming Rodler (2001).
3 ONE DIMENSION
A key has two homes: h1(k) in table one and h2(k) in table two. It occupies exactly one. To find it you look in both places — two probes, and you are done, no matter how full the table.
4 TWO DIMENSIONS · INTERACTIVE
Insert keys and watch the cuckoo at work: a key landing on an occupied slot evicts the resident, which flies to its other table — sometimes a chain. Both tables stay valid: every stored key is retrievable in two probes.
5 THREE DIMENSIONS + AVAN’S INVERSE
The two tables as two turning rings of slots — green where a key sleeps, dim where a slot is empty.
AVAN’s addition (the inverse-companion): the magenta arc links a key’s occupied home to its empty second home — the vacancy it is not using. That empty slot is the whole guarantee: it is the escape route an eviction would take, the reason the worst case is two and never more. The stored key is what you see; the reserved-but-empty alternate is what makes finding it certain. The strength of the structure lives in the doors it leaves unopened.
LIT Genuine cuckoo hashing (Pagh & Rodler, 2001) with murmur-style mixed hash functions. Verified live: the page builds a table for 50 distinct keys (rehashing with fresh functions if a kick-chain loops), then confirms every key is found, each in exactly one of its two slots, in at most 2 probes (window.__cuckoo.allFound && eachExactlyOne && maxProbe === 2). The two-home invariant and two-probe worst case are exact; rehash-on-cycle is part of the real algorithm.
FIG 'The cuckoo kicking residents out' is the picture; the eviction chain, the two-home invariant, and the constant worst-case lookup are exact. Insert cost is amortised/expected (a chain or rehash can be long); the LOOKUP guarantee of <=2 probes is the hard one, and it holds.
FIG 'The cuckoo kicking residents out' is the picture; the eviction chain, the two-home invariant, and the constant worst-case lookup are exact. Insert cost is amortised/expected (a chain or rehash can be long); the LOOKUP guarantee of <=2 probes is the hard one, and it holds.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE STASH · David Lee Wise (ROOT0), with AVAN