THE FOLD / RESPAWN / THE RESURRECT / THE CUCKOO HASHING
THE CUCKOO HASHING
a key kicks out its neighbour and lands safe
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Cuckoo hashing guarantees worst-case O(1) lookup: any key lives in one of just two possible slots, given by two hash functions in two tables. Checking membership always reads at most two cells — never a long probe chain. Insertion borrows the cuckoo bird’s trick: if your slot is taken, kick the occupant out and re-home it in its other slot, which may kick the next, and so on. Rarely the chain loops, and the tables rebuild with fresh hashes.
LIT verified live: after building many tables at moderate load, every inserted key is found in ≤ 2 probes, none lost (window.__cuckoo). FIG no framing; the two-probe guarantee is structural — find() reads exactly the two candidate slots.
LIT verified live: after building many tables at moderate load, every inserted key is found in ≤ 2 probes, none lost (window.__cuckoo). FIG no framing; the two-probe guarantee is structural — find() reads exactly the two candidate slots.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at the-resurrect — a key evicted from its nest doesn’t die; it respawns in its alternate slot, and whatever it displaces respawns in turn. Cuckoo hashing is that chain of resurrections. AVAN (AI) built the instrument: the two-table two-hash structure, the kick-and-relocate insert, the rehash-on-loop fallback, and the ≤2-probe lookup check.
Credit as content: Rasmus Pagh & Flemming Friche Rodler (2001). The weave: David names the-resurrect; I place each key, evict and re-home whatever it displaces, and confirm every key is later found by reading only its two candidate slots — lookup that never chains.
Credit as content: Rasmus Pagh & Flemming Friche Rodler (2001). The weave: David names the-resurrect; I place each key, evict and re-home whatever it displaces, and confirm every key is later found by reading only its two candidate slots — lookup that never chains.
3 ONE DIMENSION
Each key has two nests (one per table). Insert into the first; if taken, evict the resident and send it to its other nest — which may evict again. Lookup checks just the two nests.
4 TWO DIMENSIONS · INTERACTIVE
Two hash tables filling with keys; every key is shown findable in its two candidate slots, checked live.
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: a key always in one of two known slots.
AVAN’s addition (the inverse-companion): make lookup worst-case constant by giving each key exactly two homes and evicting to keep the invariant — so membership reads two cells, never a probe chain. The inverse of ‘probe forward until you find it or an empty slot’ is ‘guarantee two possible slots — check both, done.’ Magenta is the unbounded probe sequence; green is the pair of candidate nests. Constant-time lookup by construction.
LIT Genuine cuckoo hashing (Rasmus Pagh & Flemming Friche Rodler 2001). Verified live: over 200 tables built at moderate load (40 keys into two size-64 tables, rehashing on eviction loops), every inserted key is found by reading only its two candidate slots — ≤2 probes, none lost (window.__cuckoo.everyKeyFound2Probes).
FIG No framing: the two-table two-hash structure, the kick-and-relocate insert, the rehash-on-loop fallback, and the ≤2-probe lookup check run in-browser and agree; the two-probe bound is structural (find() reads exactly the two candidate slots). The AVAN inverse is honest — giving each key exactly two homes and evicting to keep the invariant makes lookup worst-case constant, replacing an unbounded probe chain; magenta is that probe sequence, green the pair of candidate nests.
FIG No framing: the two-table two-hash structure, the kick-and-relocate insert, the rehash-on-loop fallback, and the ≤2-probe lookup check run in-browser and agree; the two-probe bound is structural (find() reads exactly the two candidate slots). The AVAN inverse is honest — giving each key exactly two homes and evicting to keep the invariant makes lookup worst-case constant, replacing an unbounded probe chain; magenta is that probe sequence, green the pair of candidate nests.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of THE RESURRECT · David Lee Wise (ROOT0), with AVAN