(data structure)
Definition: A dictionary implemented with two hash tables, T1 and T2, and two different hash functions, h1 and h2. Each key, k, is either in T1[h1(k)] or T2[h2(k)]. A new key, k, is stored in T1[h1(k)]. If that location is already occupied by another key, l, the other key is moved to T2[h2(l)]. Keys are moved back and forth until a key moves to an empty location or a limit is reached. If the limit is reached, new hash functions are chosen, and the tables are rehashed. For tables that are a bit less than half full and with carefully chosen universal hashing functions, performance is good. A key is deleted by removing it from a table.
Generalization (I am a kind of ...)
hash table.
Aggregate parent (I am a part of or used in ...)
dictionary.
Aggregate child (... is a part of or used in me.)
array, hash function.
See also 2-left hashing.
Note: The name comes from the European cuckoo, whose young pushes other, competing eggs out of the nest.
Author: PEB
Rasmus Pagh and Flemming Friche Rodler, Cuckoo Hashing, Proceedings of ESA 2001, Lecture Notes in Computer Science, vol. 2161, pages 121-?, 2001.
Generalized in Úlfar Erlingsson, Mark Manasse, and Frank McSherry, A cool and practical alternative to traditional hash tables, proc 7th Workshop on Distributed Data and Structures (WDAS'06), Santa Clara, CA, January 2006.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 30 March 2009.
HTML page formatted Mon Feb 2 13:10:39 2015.
Cite this as:
Paul E. Black, "cuckoo hashing", in
Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 30 March 2009. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/cuckooHashing.html