Cuckoo hashing made lookup constant-time by evicting a key like a cuckoo egg

Standard open-addressed hash tables degrade when entries cluster and probing chains grow long. Rasmus Pagh and Flemming Friche Rodler asked what would happen if each key had exactly two possible slots instead of one.

Their dictionary, presented in 2001 at BRICS in Aarhus, uses two hash functions and two tables. On a collision, the arriving key evicts the occupant, which recurses to its other home. Lookup is guaranteed in at most two probes.

Because the tables only need to be about half full on average, the structure stays memory-efficient while providing a hard worst-case constant lookup.

Give every key two places and relocate the loser

Two possible positions bound a search to two probes, no matter the key set.

Eviction resolves collisions without a long probe chain or a chained list.

It keeps high occupancy, so it uses memory well while remaining cache-friendly.

Pick a data structure that is fast in the worst case, not just on average. The two-choice eviction turns a rare, expensive collision into a bounded two-probe lookup.

Cuckoo hashing became a reference result in the theory and practice of dictionaries. Its constant-time guarantee and cache locality made it attractive for hardware and high-performance routing, and the eviction idea influenced later hash and sketching schemes.