hide
Free keywords:
-
Abstract:
We generalize Cuckoo Hashing to \emph{$d$-ary Cuckoo Hashing} and show how this
yields a simple hash table data structure that stores $n$ elements in
$(1+\e)\,n$ memory cells, for any constant $\e > 0$. Assuming uniform hashing,
accessing or deleting table entries takes at
most $d=\Oh{\ln\frac{1}{\e}}$ probes and the expected amortized insertion
time is constant. This is the first dictionary that has worst case
constant access time and expected constant update time, works with
$(1+\e)\,n$ space, and supports satellite information. Experiments
indicate that $d=4$ probes suffice for $\e\approx 0.03$.
We also describe variants of the data structure
that allow the use of hash functions that can be evaluated in constant time.
