The encyclopedia · Software & IT · Technical decision · 2001
Cuckoo hashing made lookup constant-time by evicting a key like a cuckoo egg
Pagh & Rodler gave each key two homes; on collision the newcomer evicts the resident, guaranteeing O(1) worst-case search.
BRICS (Aarhus University)
the move
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.
why it works
- 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.
what transfers
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.
what came after
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.
references
spotted an error? The archive wants to know.