de.mpg.escidoc.pubman.appbase.FacesBean
English

# Item

ITEM ACTIONSEXPORT

Released

Conference Paper

#### Space Efficient Hash Tables with Worst Case Constant Access Time

##### MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons44436

Fotakis,  Dimitris
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45344

Sanders,  Peter
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons45532

Spirakis,  Paul G.
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Alt,  Helmut
Max Planck Society;

Habib,  Michel
Max Planck Society;

##### Locator
There are no locators available
##### Fulltext (public)
There are no public fulltexts available
##### Supplementary Material (public)
There is no public supplementary material available
##### Citation

Fotakis, D., Pagh, R., Sanders, P., & Spirakis, P. G. (2003). Space Efficient Hash Tables with Worst Case Constant Access Time. In Proceedings of the 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2003) (pp. 271-282). Berlin, Germany: Springer.

Cite as: http://hdl.handle.net/11858/00-001M-0000-000F-2E2A-4
##### Abstract
We generalize Cuckoo Hashing \cite{PagRod01} to \emph{$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 = 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= 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.