research unit 1

This site is powered by Aigaion - A PHP/Web based management system for shared and annotated bibliographies. For more information visit


Type of publication:Inproceedings
Entered by:
TitleSpace Efficient Hash Tables with Worst Case Constant Access Time
Bibtex cite IDRACTI-RU1-2003-50
Series Lecture Notes in Computer Science
Year published 2003
Month January
Volume 2607/2003
Pages 271-282
Publisher Springer Berlin / Heidelberg
DOI 10.1007/3-540-36494-3_25
We generalize Cuckoo Hashing [16] 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)”.
Fotakis, Dimitris
Pagh, Rasmus
Sanders, Peter
Spirakis, Paul
fulltext.pdf (main file)
Publication ID345