We generalize Cuckoo Hashing  to d-ary Cuckoo Hashing and show how this yields a simple hash table data structure that stores n elements in (1 + ∈) n memory cells, for any constant ∈ > 0. Assuming uniform hashing, accessing or deleting table entries takes at most d = O(ln 1/∈ ) 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+∈) n space, and supports satellite information. Experiments indicate that d = 4 choices suffice for ∈ ≈ 0.03. We also describe a hash table data structure using explicit constant time hash functions, using at most d = O(ln2 1/∈ ) probes in the worst case.
A corollary is an expected linear time algorithm for finding maximum cardinality matchings in a rather natural model of sparse random bipartite graphs.
This work was partially supported by DFG grant SA 933/1-1 and the Future and Emerging Technologies programme of the EU under contract number IST-1999- 14186 (ALCOM-FT).
The present work was initiated while this author was at BRICS, Aarhus University, Denmark.
Part of this work was done while the author was at MPII. 1 In this paper “whp.” will mean “with probability 1 - O(1/n)”.