Evict

Every key has exactly two homes — slot h1(key) in table 1, slot h2(key) in table 2 — and a key is in one of its own two homes or it is nowhere. That single invariant is what makes the lookup a constant:

get(key):  look at t1[h1(key)];  look at t2[h2(key)];  done.

Two reads. At a tenth full and at a hair under the limit. No probe sequence to walk, no tombstones to skip, no clustering to measure — and no average, either, which is the part worth sitting with. Linear probing has a mean cost that is fine and a tail that is not; this has no tail, because the second read is the last read. The header counts it on every frame and the number never moves.

Nothing is free, so the question is where the cost went, and all of it went into insert. Writing a key into an occupied home does not go looking for somewhere else to put the newcomer. It puts the newcomer in and throws the resident out, and the resident goes to its other home, which may also be occupied, which starts the same move again. One insert is a chain of displacements that ends when it reaches a free slot — or when it has been going long enough that we stop and call the table unusable.

Watch that cost in the strip along the bottom: one bar per insert, height in kicks, with the load factor drawn over it as a faint line. For most of the run the bars are nothing — the mean is well under one kick. Then the load line crosses ½ and the bars go vertical. The average was never the story.

The jam is structural, and that is the whole piece

Press graph. The two rows stop being tables and become what they always were: 2m vertices, one per slot. Every key is an edge joining its two homes, and storing the keys means orienting every edge — each key pointing at the one slot it occupies — so that no slot is pointed at twice. A connected component with v slots can hold at most v keys, so each component gets one of three verdicts, and the demo paints them:

• tree (teal), edges < vertices — orientable, always, from any free slot outward. Chains inside it cannot be longer than the component.
• saturated (amber), edges == vertices — one cycle, every slot full, the orientation forced. An insert that lands here walks the whole cycle and comes back with nothing.
• impossible (red), edges > vertices — there is no assignment at all. No insertion order places these keys, because no order exists that would.

The key currently in hand is drawn as a dashed edge, which matters more than it sounds: without counting the key that could not get in, a jammed component still reads as merely saturated. Counting it, the picture tips over to red and the verdict line underneath says 4 slots, 5 keys — impossible. The insert did not fail because the order was unlucky. It failed because of that.

Which also says what the escape is. You cannot reorder your way out of a component that holds more keys than slots; you can only get a different graph, which means different hash functions. That is what a rehash is here, and the saturated preset is built to show it: four keys whose homes form a 4-cycle, a few bystanders, then a fifth key whose two homes are a pair already inside the cycle.

Three rules, because the second is what gets written first

• evict and re-home the resident is cuckoo hashing.
• nothing moves — drop the key is the two-choice table you write before you have heard of the first one: same two tables, same two-read lookup, no displacement. It starts dropping keys at a load the real thing has not noticed yet, and the readout says where both of them first jammed. That gap is the measurement of what the eviction chain buys — and in the graph it is drawn as keys refused by components that were perfectly orientable, if anything had been willing to move.
• evict; a jam parks in a stash is Kirsch–Mitzenmacher–Wieder: a two-slot side buffer catches the homeless key instead of condemning the whole table. It mostly stops the rehash happening. It also costs a third read on every lookup, forever, in use or not — so the constant that was the entire point goes from 2 to 3, and the header says so.

About the wall at ½

Two hashes hold a load factor of ½ and no more. That is an asymptotic statement — as the table grows, the probability that a random cuckoo graph is orientable goes to 1 below ½ and to 0 above it — and the demo is honest about the fact that a table of twelve slots is nowhere near asymptotic. The fluctuations are the same size as the table, so a jam at load 0.5 can genuinely be rescued by a different pair of hash functions.

The rehashes slider is that caveat made operable: it is how many fresh hash pairs a jam may try before the run gives up. At 0 the first jam ends it, near enough to ½. Wind it to 12 and the same key stream reaches load 0.875 — not because cuckoo hashing beats its own threshold, but because at this size you can buy enough lottery tickets to find a rare orientable graph. The readout counts the tickets (hash pairs). On a table with a million slots that search never pays, which is why real implementations resize rather than reroll.

Three hashes instead of two move the same wall to about 0.918.

Reading it

Click or hover any key to pin its lookup: both homes light with a dashed ring, the readout spells out h1 and h2, and the count says 2 (or 3 with a stash). Hovering also picks that key’s component out of the graph and prints its verdict. ←/→ scrub, space plays, g toggles the graph.

Reuse

src/evict.js is a framework-free ES module:

• hashSlot(key, seed, m), homes(key, seeds, m) — the two candidate slots.
• keyPool(count, seed) — deterministic consonant–vowel–consonant keys, so a chain reads as things being moved rather than as indices.
• trace({ keys, m, seeds, rule, maxKicks, maxRehash }) — one frame per step, each carrying the state after it, so a renderer can scrub in both directions. Frame kinds: probe | place | kick | reject | cycle | stashed | rehash | stuck | dup. Reports firstJam (the load factor at the first refusal — the honest number to compare rules on), attempts, longestChain, meanChain, rehashes, rejected, reads. Same trace-per-tick shape as canonical, lowest-common and prune.
• graphOf(state, pending) — the cuckoo graph, components classified tree | full | over. Pass the in-hand key as pending or a jammed component reads as merely saturated.
• lookup(state, key, rule) — which slots a get touches, and how many.
• simulate({ keys, m }) — the same key stream under all three rules.

No rendering or timers in the module; the canvas demo is reference code.

Gotchas

• no-relocate is deliberately worse. It is there to be measured against, not reused.
• firstJam.load is the comparable number between rules, not load: a rule that drops keys keeps accepting later ones and ends up looking fuller than one that stops, which is backwards.
• trace mutates nothing the caller owns, but graphOf walks the whole table on every call — fine at these sizes, not a hot path.
• The demo bundles its own copy of evict.js (self-contained by contract); re-copy after editing src/.
• node scripts/screenshot-demo.mjs [out] [--preset=] [--rule=] [--tries=] [--slots=] [--graph] [--pin=key] [--at=end|<frame>] [--w= --h=] regenerates thumb.png through site/scripts/lib/chromium.mjs.