Cuckoo Hashing: Guaranteed Constant-Time Lookups

How Cuckoo Hashing Works

Cuckoo hashing relies on two independent hash functions, commonly called h1 and h2, and (in the classic two-table variant) two arrays of equal size. Every key k has exactly two legal homes: position h1(k) in table one and position h2(k) in table two. To look up a key, you simply compute both hash values and check both slots; if the key is in neither, it is definitely not in the table. This is what makes lookup so predictable: no chain to walk, no probe sequence to follow, just two direct array accesses. Insertion is where the scheme gets interesting. To insert key k, first check its slot in table one. If that slot is empty, place k there and you are done. If the slot is occupied by some other key j, k evicts j, taking its place, and now j must be reinserted at its own alternate slot, in table two. If that slot is also occupied, the key sitting there gets evicted in turn, and the process repeats, bouncing back and forth between the two tables. Each evicted key always has a well-defined alternate location because every key's two positions are fixed the moment it is hashed, regardless of how many times it gets kicked out and reinserted. Deletion is simple too: locate the key in one of its two slots and remove it directly, no restructuring of a chain or shifting of probe sequences required. The elegance of the design is that the two-hash-function, two-slot invariant is preserved after every operation, so the guarantee that a lookup only ever needs to check two places never breaks, no matter how the table has been shuffled internally by past insertions.

The Eviction Chain: A Cuckoo's Nest of Keys

The eviction process is the heart of cuckoo hashing, and it behaves exactly like its namesake bird. A cuckoo lays an egg in another bird's nest, and when it hatches, the cuckoo chick shoves the original eggs out to claim all the parental care for itself. In the hash table, inserting a new key can shove an existing key out of its slot, forcing that displaced key to move to its other nest, which might itself already be occupied, displacing yet another key, and so on. In practice, most insertions settle down after just one or two evictions, especially when the table is not too full. Picture inserting a handful of keys into a small table: the first few slide into empty slots without any drama, but eventually a new key lands on an occupied slot, bumps the resident key out, that resident finds its alternate slot occupied too, bumps another key out, and the chain continues until some key finally lands in an empty slot and the cascade terminates. Most of the time this chain is short and resolves quickly, giving insertion an expected running time close to constant, even though a single insertion can occasionally touch many keys. The danger is that the chain of evictions can, in rare cases, loop back on itself: key A displaces key B, which displaces key C, which eventually displaces key A again, recreating the exact situation that started the chain. This is called a cycle, and it means the current pair of hash functions simply cannot accommodate the current set of keys in their two fixed slots each. Implementations guard against this by capping the number of evictions allowed for a single insertion, for example at some multiple of the logarithm of the table size.

Breaking Cycles: Rehashing the Table

When an insertion's eviction chain exceeds the allowed threshold, or an actual cycle is detected, cuckoo hashing does not simply fail; it rebuilds. The standard remedy is to choose a fresh pair of hash functions, h1 and h2, and rehash every key currently stored in the table, along with the key that triggered the failure, into new slots determined by the new functions. Because the new hash functions scatter keys differently, the specific configuration that caused a cycle almost certainly will not reappear immediately, and insertion proceeds normally afterward. This rehashing step is sometimes paired with growing the table if the load has become high, which reduces both the frequency of long eviction chains and the chance of future cycles. Rehashing an entire table sounds expensive, and a single rehash does cost time proportional to the number of keys stored, but the key theoretical result underlying cuckoo hashing is that with well-chosen, sufficiently random hash functions and a load factor kept comfortably below the danger zone, the probability of needing a rehash on any given insertion is small enough that the amortized cost of insertion remains constant on average across a long sequence of operations. Some practical implementations also use a small auxiliary structure called a stash to hold a handful of keys that could not be placed after an eviction chain, avoiding a full rehash for occasional bad luck. Whether via rehashing, table growth, or a stash, the underlying strategy is the same: treat a stuck eviction chain as a rare structural failure of the current hash functions, not a flaw in the algorithm, and fix it by changing the functions rather than by relaxing the two-slot guarantee that makes lookups fast.

Load Factor: Why Cuckoo Hashing Wants Room to Breathe

The load factor of a hash table is the fraction of slots that are currently occupied, and it profoundly affects how cuckoo hashing behaves. When the table is mostly empty, insertions almost always land directly or trigger only a very short eviction chain, because there is a good chance a key's alternate slot is free. As the load factor climbs, the odds that both of a key's candidate slots are already taken rise sharply, and eviction chains grow longer and more likely to loop into a cycle. Theoretical analysis of the classic two-table, two-hash-function version shows that the scheme works well as long as the load factor stays below roughly one half, meaning the table should hold no more than about fifty percent as many keys as it has total slots combined across both tables. Push much past that point and the probability of a cycle rises quickly, triggering frequent, costly rehashes that erode the constant-time guarantee in practice even though lookups technically remain fast once the table is stable. This fifty percent ceiling is noticeably more conservative than schemes like linear probing, which can often tolerate loads of seventy or eighty percent before performance degrades badly, or separate chaining, which barely degrades at all since chains simply grow longer. The tradeoff is deliberate: cuckoo hashing spends extra space, roughly double what a maximally packed structure would need, in exchange for a hard ceiling on lookup cost. Variants that use more than two hash functions, more than two tables, or buckets that hold a small number of keys each (sometimes called bucketized cuckoo hashing) can push the safe load factor considerably higher, often above ninety percent, at the cost of slightly more complex lookups that check more than two locations.

Comparing Cuckoo Hashing to Chaining and Linear Probing

The two classic alternatives to cuckoo hashing are separate chaining and open addressing schemes like linear probing, and the comparison illuminates exactly what cuckoo hashing buys you. In separate chaining, each slot holds a linked list (or similar structure) of every key that hashes there; lookup means walking that list, so in the worst case, if many keys collide into one slot, a lookup can take time proportional to the number of keys in the table. Average-case performance is good with a well-spread hash function, but there is no guarantee against a bad run of luck or an adversarial input producing a long chain. Linear probing stores keys directly in the array and, on collision, scans forward slot by slot until it finds an empty one; lookup similarly must follow that same probe sequence, and as the table fills up, probe sequences can become long, degrading performance, particularly through a phenomenon called primary clustering where occupied runs of slots grow and merge. Cuckoo hashing sidesteps both problems by fixing, in advance, exactly two locations a key could ever occupy. A lookup is never longer than two probes, period, regardless of how full the table is (up to its safe operating load factor) or how unlucky the hash values happen to be. This is a genuine worst-case guarantee, not merely an average-case one, which matters enormously in real-time systems, hardware implementations, and networking applications like routing tables where a single slow lookup can violate latency requirements. The price paid is a lower usable load factor, more complex insertion logic involving potential eviction chains and rehashing, and a need for good-quality, independent hash functions to keep cycle probability low.

Frequently asked questions

Try it live

Everything above runs in your browser — open Cuckoo Hashing: Guaranteed Constant-Time Lookups and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.