de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Paper

On the Insertion Time of Cuckoo Hashing

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

Fountoulakis,  Nikolaos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

Panagiotou,  Konstantinos
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

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

Steger,  Angelika
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

arXiv:1006.1231.pdf
(Preprint), 316KB

Supplementary Material (public)
There is no public supplementary material available
Citation

Fountoulakis, N., Panagiotou, K., & Steger, A. (2010). On the Insertion Time of Cuckoo Hashing. Retrieved from http://arxiv.org/abs/1006.1231.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0015-863E-D
Abstract
Cuckoo hashing is an efficient technique for creating large hash tables with high space utilization and guaranteed constant access times. There, each item can be placed in a location given by any one out of k different hash functions. In this paper we investigate further the random walk heuristic for inserting in an online fashion new items into the hash table. Provided that k > 2 and that the number of items in the table is below (but arbitrarily close) to the theoretically achievable load threshold, we show a polylogarithmic bound for the maximum insertion time that holds with high probability.