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 name derives from the behavior of some species of cuckoo, where the cuckoo chick pushes the other eggs or young out of the nest when it hatches.
Theory
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. In one of the commonly used variants of the algorithm, the hash table is split into two smaller tables of equal size, and each hash function provides an index into one of these two tables.
When a new key is inserted, a greedy algorithm 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 in-place[2] using new hash functions.
Lookup requires inspection of just 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 worst-case 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, i.e., the load factor is below 50%. One method of proving this uses the theory of random graphs: one may form an undirected graph called the "Cuckoo Graph" that has a vertex for each hash table location, and an edge for each hashed value, with the endpoints of the edge being the two possible location of the value. Then, the greedy insertion algorithm for adding a set of values to a cuckoo hash table succeeds if and only if the Cuckoo Graph for this set of values is a pseudoforest, a graph with at most one cycle in each of its connected components. This property is true with high probability for a random graph in which the number of edges is less than half the number of vertices.[3]
Generalizations and applications
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.[citation needed] A simplified generalization of cuckoo hashing called skewed-associative cache is used in some CPU caches.[citation needed]
A study by Zukowski et al.[4] has shown that cuckoo hashing is much faster than chained hashing for small, cache-resident hash tables on modern processors. Kenneth Ross[5] 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. The performance of the bucketized cuckoo hash table was investigated further by Askitis,[6] with its performance compared against alternative hashing schemes.
A survey by Mitzenmacher[7] presents open problems related to cuckoo hashing as of 2009.
See also
References
- ^ a b Pagh, Rasmus (2001). "Cuckoo Hashing" (PDF, PS). doi:10.1.1.25.4189. Retrieved 2008-10-16.
{{cite journal}}: Check|doi=value (help); Cite journal requires|journal=(help); Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ Pagh and Rodler: "There is no need to allocate new tables for the rehashing: We may simply run through the tables to delete and perform the usual insertion procedure on all keys found not to be at their intended position in the table."
- ^ Kutzelnigg, Reinhard (2006), "Bipartite random graphs and cuckoo hashing", Fourth Colloquium on Mathematics and Computer Science, Discrete Mathematics and Theoretical Computer Science, vol. AG, pp. 403–406.
- ^ Zukowski, Marcin (2006-06). "Architecture-Conscious Hashing" (pdf). Proceedings of the International Workshop on Data Management on New Hardware (DaMoN). Retrieved 2008-10-16.
{{cite journal}}: Check date values in:|date=(help); Cite journal requires|journal=(help); Unknown parameter|coauthors=ignored (|author=suggested) (help) - ^ Ross, Kenneth (2006-11-08). "Efficient Hash Probes on Modern Processors" (pdf). IBM Research Report RC24100. RC24100. Retrieved 2008-10-16.
{{cite journal}}: Cite journal requires|journal=(help) - ^ Askitis, Nikolas (2009). Fast and Compact Hash Tables for Integer Keys (PDF). Vol. 91. pp. 113–122. ISBN 978-1-920682-72-9.
{{cite book}}:|journal=ignored (help) - ^ Mitzenmacher, Michael (2009-09-09). "Some Open Questions Related to Cuckoo Hashing" (pdf). Retrieved 2010-11-10.
{{cite journal}}: Cite journal requires|journal=(help); Text "Proceedings of ESA 2009" ignored (help)
- A cool and practical alternative to traditional hash tables, U. Erlingsson, M. Manasse, F. Mcsherry, 2006.
- Cuckoo Hashing for Undergraduates, 2006, R. Pagh, 2006.
- Cuckoo Hashing, Theory and Practice (Part 1, Part 2 and Part 3), Michael Mitzenmacher, 2007.
- Naor, Moni (2008). "History-Independent Cuckoo Hashing". International Colloquium on Automata, Languages and Programming (ICALP). Reykjavik, Iceland. Retrieved 2008-07-21.
{{cite conference}}: External link in|author2-link=|booktitle=ignored (|book-title=suggested) (help); Unknown parameter|coauthors=ignored (|author=suggested) (help)