Two homes per key with recursive displacement
Cuckoo hashing assigns each key two possible bucket positions, computed by two independent hash functions h1(key) and h2(key). On insert, the key goes into one of its two homes if vacant. If both are occupied, the algorithm 'evicts' the current resident and relocates it to its other home, recursively evicting as needed. This chaining of displacements resembles a cuckoo pushing other birds out of their nests.
The name comes from this eviction behavior. If done carefully with cycle detection, the algorithm guarantees O(1) lookups: the key is either at h1(key) or h2(key). Insertions are amortized O(1) as long as the load factor stays below a threshold, typically around 0.5.
Guarantees and failure scenarios
If the insertion process enters an infinite loop (a displacement cycle with no resolution), the table must be resized and all entries rehashed with new hash functions. This rehashing is expensive but rare if load factors are kept low and hash functions are chosen carefully. A load factor near 0.5 typically keeps cycles infrequent.
Cuckoo hashing offers worst-case O(1) lookups, which regular chaining hash tables cannot provide (they can degrade to O(n) on collision chains). This makes cuckoo hashing valuable for latency-critical applications. However, its insertion overhead and strict load-factor management make it less convenient than simpler alternatives like linear probing or chaining for general use.