@inbook {IOPORT.01962820,
    author       = {Fotakis, Dimitris and Pagh, Rasmus and Sanders, Peter and Spirakis, Paul},
    title        = {Space efficient hash tables with worst case constant access time.},
    year         = {2003},
    booktitle    = {STACS 2003. 20th annual symposium of theoretical aspects on computer science, Berlin, Germany, February 27 -- March 1, 2003. Proceedings},
    isbn         = {3-540-00623-0},
    pages        = {271-282},
    publisher    = {Berlin: Springer},
    abstract     = {Summary: 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+{\epsilon}) n$ memory cells, for any constant ${\epsilon} > 0$. Assuming uniform hashing, accessing or deleting table entries takes at most $d=\text{O}({\ln\frac{1}{{\epsilon}})}$ 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+{\epsilon}) n$ space, and supports satellite information. Experiments indicate that $d=4$ choices suffice for ${\epsilon}\approx 0.03$. We also describe a hash table data structure using explicit constant time hash functions, using at most $d=\text{O}({\ln^2\frac{1}{{\epsilon}}})$ 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.},
    identifier   = {01962820},
}