Information about Cuckoo Hashing

Cuckoo hashing is a scheme in computer programming for resolving hash collisions of values of hash functions in a table. Cuckoo hashing was first described by Rasmus Pagh and Flemming Friche Rodler in 2001. ^[1]

The basic idea is to use two hash functions instead of only one. This provides two possible locations in the hash table for each key.

When a new key is inserted, a greedy approach is used: The new key is inserted in one of its two possible locations, "kicking out", that is, displacing any key that might already reside in this location. This displaced key is then inserted in its alternative location, again kicking out any key that might reside there, until a vacant position is found, or the procedure enters an infinite loop. In the latter case, the hash table is rebuilt using new hash functions.

Lookup requires just inspection of two locations in the hash table, which takes constant time in the worst case (see Big O notation). This is in contrast to many other hash table algorithms, which may not have a constant bound on the time to do a lookup.

It can also be shown that insertions succeed in expected constant time ^[1], even considering the possibility of having to rebuild the table, as long as the number of keys is kept below half of the capacity of the hash table.

The basic version of cuckoo hashing has load factor limited to 49%.

Generalizations of cuckoo hashing that use more than 2 alternative hash functions can be expected to utilize a larger part of the capacity of the hash table efficiently while sacrificing some lookup and insertion speed. Using just three hash functions increases the load to 91%. Another generalization of cuckoo hashing consists in using more than one key per bucket. Using just 2 keys per bucket permits a load factor above 80%.

(Other algorithms that use multiple hash functions include the Bloom filter). Cuckoo hashing can be used to implement a data structure equivalent to a Bloom filter.

The name derives from the behavior of some species of cuckoo, where the mother bird pushes eggs out of another bird's nest to lay her own. A study by Zukowski et al. ^[2] has showed that cuckoo hashing is much faster than chained hashing for small, cache-resident hash tables on modern processors. K. Ross ^[3] has shown bucketized versions of cuckoo hashing (variants that use buckets that contain more than one key) to be faster than conventional methods also for large hash tables, when space utilization is high. However as of 2007 cuckoo hashing remains widely unknown outside the research community.

See also

• Perfect hashing
• Linear probing
• Double hashing
• Hash collision
• Hash function
• Quadratic probing
• Two choice paradigm

References

• ^  Cuckoo Hashing, Pagh, Rodler, 2001.
• ^  Architecture-Conscious Hashing, Zukowski et al, 2006.
• ^  Efficient Hash Probes on Modern Processors, Kenneth A. Ross, 2006.
• A cool and practical alternative to traditional hash tables, U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
• Cuckoo Hashing for Undergraduates, 2006, R. Pagh, 2006.
• Three blog posts by Michael Mitzenmacher expounding cuckoo hashing.