Cuckoo Hashing

By Rasmus Pagh, Flemming Friche Rodler. 2001

1,550 citations recorded by the source corpus.

We present a simple dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. [SIAM J. Comput. 23 (4) (1994) 738-761]. The space usage is similar to that of binary search trees. Besides being conceptually much simpler than previous dynamic dictionaries with worst case constant lookup time, our data structure is interesting in that it does not use perfect hashing, but rather a variant of open addressing where keys can be moved back in their probe sequences. An implementation inspired by our algorithm, but using weaker hash functions, is found to be quite practical. It is competitive with the best known dictionaries having an average case (but no nontrivial worst case) guarantee on lookup time.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “In Cuckoo hashing [63], items are moved around following the Cuckoo hashing algorithm (we explain this algorithm in Section 4.”
Searching Efficient 3D Architectures with Sparse Point-Voxel Convolution (2020, methodology): “As the lookup over the hash table requires O(1) time [37], this query step will in total take O(m) time.”
Forwarding metamorphosis: fast programmable match-action processing in hardware for SDN (2013, methodology): “Exact match tables are implemented as Cuckoo hash tables [10, 26, 32] with (at least) four ways of 1K entries each, each way requiring one RAM block.”
Fast Private Set Intersection from Homomorphic Encryption (2017, methodology): “Cuckoo hashing [16, 22, 47] is a way to build dense hash tables by using h > 1 hash functions H1, .”
Oblivious RAM Revisited (2010, methodology): “Cuckoo hashing [16,17] is a relatively new hashing algorithm, which in its basic form maps each item to one of two potential entries of a hash table, while ensuring constant lookup and deletion time in the worst case, and amortized constant time for insertions.”
On Deploying Secure Computing Commercially: Private Intersection-Sum Protocols and their Business Applications (2019, background): “To check if an item x is in the Cuckoo Hash Table, one checks each of the bins in {hi(x)}ki=1 for the item.”
Balls into Bins Made Faster (2013, background): “An important example of an allocation strategy in this direction is cuckoo hashing [14, 4].”
Faster Private Set Intersection Based on OT Extension (2014, methodology): “Cuckoo Hashing Similar to balanced allocations hashing , Cuckoo hashing [51] uses two hash functions h 1 , h 2 : {0, 1} σ → [1, b] to map m elements to b = 2(1 + ε)m bins.”
Using One-Sided RDMA Reads to Build a Fast, CPU-Efficient Key-Value Store (2013, methodology): “memory efficiency with fewer probes, Pilaf uses n-way Cuckoo hashing [21, 15].”
SILT: a memory-efficient, high-performance key-value store (2011, methodology): “Hashing Cuckoo hashing [34] is an open-addressing scheme to resolve hash collisions efﬁciently with high space occupancy.”
Backyard Cuckoo Hashing: Constant Worst-Case Operations with a Succinct Representation (2009, background): “However, for memory utilization close to 100% it is rather inefficient, and the average search time becomes linear in the number of elements stored (for more details we refer the reader to Theorem K and the subsequent discussion in [Knu98, Chapter 6.4]).”
Theory and Practice of Bloom Filters for Distributed Systems (2012, methodology): “[61]), approximate dictionary-inspired approaches [6], [35], ca cheefficient variants (blocked Bloom filter) and Golomb coding implementations as proposed by Putze et al [62], spaceefficient versions of cuckoo hashing [63], and more complex but space-optimal alternatives [5], [6].”
The Case for Learned Index Structures (2017, background): “However, many alternatives exist including secondary probing, using buckets with several slots, up to simultaneously using more than one hash function (e.g., as done by Cuckoo Hashing [57]).”
Using RDMA efficiently for key-value services (2014, methodology): “In recent years, several systems have used advanced hash table designs such as Cuckoo hashing [24, 17, 9] and Hopscotch hashing [12].”
ChunkStash: Speeding Up Inline Storage Deduplication Using Flash Memory (2010, methodology): “In the original cuckoo hashing scheme [35], a recursive strategy is used to relocate one of the keys yi – in the worst case, this strategy could take many key relocations or get into an infinite loop, the probability for which can be shown to be very small and decreasing exponentially in n [35].”
A Pragmatic Introduction to Secure Multi-Party Computation (2019, methodology): “For example, additively homomorphic encryption schemes (including Paillier (1999) and Damgård and Jurik (2001)) can perform large additions much more e ciently than can be done with Boolean circuits.”