Deep autumn; goose-cries skim the ridgeline of the Cloud-Mist Mountains. In the fold of the hills lies a valley every migrating bird knows by name: Two-Nest Valley.

Two groves grow there, east and west, their trunks honeycombed with a thousand hollows — a waystation on the long southern road, run by stationmasters going back generations. The keeper now is Old Gray, a man who has walked between those trees with a lantern for forty years.

The valley’s rules were laid down in his master’s day. Every bird that stops over is registered and receives two nest tokens — one naming a hollow in the east grove, one in the west. The tokens are divined by two old registrars, each reading the bird’s feather-pattern with a method of her own; neither method can be bent to name a third hollow. And the iron rule: at any moment, a bird lives in exactly one of its two nests.

The rule buys something no other valley has. When Old Gray needs a bird, he opens no ledger and calls no search party: the hollow on the first token; not there? the second. Two looks, and the bird is found. In other valleys a roosting sparrow can hide from torches all night; in Two-Nest Valley one lantern visits two doorways.

That is the valley’s fame: to find a bird, look in at most two hollows.

The price of that fame comes out at night.

A newcomer flies in and goes first to the hollow on its first token. If it’s empty, everyone is happy. But at the height of migration, hollows are usually full. Then the valley invokes an old custom it isn’t proud of — nest-yielding: the newcomer moves in and shoves the sitting tenant out.

The displaced bird — after waking half the mountain in protest — shakes out its feathers and flies to the hollow on its second token. And if that one is full? It yields in turn: shoves its tenant out and settles. The newly evicted one flies to its own other hollow… link after link, bird displacing bird, hollow trading hollow, wingbeats down the whole ridge past midnight.

Most nights the chain quiets after a dozen hops — some bird finds its other hollow standing empty, the tail of the chain settles in, and the valley sleeps.

But one night, the chain came home.

It was the busiest evening of the season. A newcomer yielded, a tenant moved, one link, two, a dozen — until the last bird displaced, circling back, wings tilting down onto the very hollow where the chain began. Sitting in it: the newcomer who had started everything. Evict it, and it must go displace the second link of the chain… The valley exploded — bird chasing bird around a closed circle, nobody settling, wingbeats from midnight to dawn.

Old Gray came out with his lantern, watched for the time an incense stick takes to burn, and went inside for three things.

The first was an old rule, nailed that dawn to a board at the valley mouth: one arrival may cause at most a hundred hops. Past a hundred, no more yielding — a chain that long is circling, and a circle has no morning.

The second stood in the valley’s center: an old locust tree five men couldn’t link arms around, a row of guest hollows carved low on its trunk, sealed in ordinary years. Old Gray broke the seals. A bird whose chain has hit the limit with nowhere to go sleeps that night in the locust. The guest hollows are few — a handful — but they exist precisely for the both-nests-full, chain-spent bird. A line is added to the register: to find this one, check its two tokens, then the locust.

The third was a notice Old Gray had written long ago and kept pressed at the bottom of a chest: Moving Day. If even the locust fills — migration swells year after year; that day always comes — the whole valley relocates to the denser forest over the back hill, hollows doubled, every bird re-registered and re-nested. Moving Day takes no newcomers and costs one chaotic day. It comes rarely; spread across every bird and every season, it amounts to one shake of feathers per quarter.

And so the valley gained the second half of its fame: crowded, yes — but no bird in the register is ever unfindable. Departures are even cleaner: a bird leaves, its hollow sits empty, and the register changes by not one stroke.

— By now you’ve probably recognized it: this is cuckoo hashing. And the custom of shoving out the sitting tenant is the cuckoo’s own nature — laying its egg in another bird’s nest and evicting the original occupant. That is where the algorithm got its name.

What it is

Cuckoo hashing is an open-addressed hash table proposed by Rasmus Pagh and Flemming Friche Rodler in 2001. Each key is assigned two candidate buckets by two hash functions, h₁ and h₂, and lives in exactly one of them at any moment. On insert, if both buckets are full, one sitting key is kicked out to its alternate bucket — and the evicted key may evict the next, forming a displacement chain. A chain can loop into a cycle and fail, so inserts carry a hop limit; keys left homeless at the limit go into a small stash; and when even the stash fills, the table rehashes into a larger one. Its signature property: lookup and deletion are worst-case O(1) — two buckets (plus the stash); there is nowhere else to look.

Why it matters

Chained hash tables are O(1) on average, but a worst-case lookup can drag to O(n): one bucket grows a long queue, and nobody can promise how far down it you will count. Cuckoo hashing trades that away — “at most two places per key” buys deterministic worst-case O(1) lookup and deletion, a hard guarantee for latency-sensitive paths (routing tables, network gear, packet processing), with a memory layout that is cache-friendly, hardware-friendly, and easy to parallelize. Its descendant, the cuckoo filter, is a modern replacement for the Bloom filter: tighter space, and it supports deletion. It is also a textbook trade: costlier inserts (displacement chains, the occasional rehash) in exchange for certain lookups — a bargain that pays when reads far outnumber writes.

Metaphor mapping

• Each bird’s two nest tokens → each key’s two hash buckets, h₁(x) and h₂(x)
• A bird lives in only one nest at a time → a key exists in exactly one bucket at any moment
• Find a bird in at most two hollows → worst-case O(1) lookup and deletion
• Two registrars, each with her own method, no third hollow possible → two independent hash functions
• A newcomer shoves out the sitting tenant → displacement on insert conflict
• The evicted bird flies to its other hollow and evicts the next → the displacement chain
• The night the chain came back to its starting hollow → a displacement cycle; the insert fails
• The hundred-hop rule → the per-insert maximum chain length
• The guest hollows on the old locust → the stash
• Moving Day: the bigger forest, new tokens for everyone → rehash into a larger table
• Moving Day takes no newcomers → the write pause during a rehash
• A bird departs, its hollow sits empty, the register unchanged → deletion costs nothing; no cleanup needed