Cuckoo Hashing

Authors

  • Rasmus Pagh
  • Flemming Friche Rodler

DOI:

https://doi.org/10.7146/brics.v8i32.21692

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. (Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput., 23(4):738-761, 1994). 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.

Downloads

Published

2001-08-04

How to Cite

Pagh, R., & Rodler, F. F. (2001). Cuckoo Hashing. BRICS Report Series, 8(32). https://doi.org/10.7146/brics.v8i32.21692