Cuckoo Hashing
📜 Abstract
We present a simple and efficient dictionary with worst case constant lookup time, equaling the theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger et al. The space usage is similar to that of binary search trees, i.e., three words per key on average. The practicality of the scheme is backed by extensive experiments and comparisons with known methods, showing it to be quite competitive also in the average case.
✨ Summary
The paper introduced cuckoo hashing, a dynamic dictionary using two candidate locations for each key and displacement of previously stored keys during insertion. Its principal result is worst-case constant-time lookup using only two memory accesses, together with amortized expected constant-time updates and space usage of approximately three machine words per key. The paper also supported the theoretical construction with empirical comparisons against established hashing methods. (rasmuspagh.net)
Subsequent research developed more precise analyses of construction time and failure probability, generalized the method to multiple hash functions and higher load factors, and studied alternative insertion strategies such as random walks and stash-based schemes. (sciencedirect.com) The technique has also been used as a practical constant-time lookup structure in scientific software and has been documented by the U.S. National Institute of Standards and Technology as a standard hash-table design pattern. (pmc.ncbi.nlm.nih.gov)