On the Insertion Time of Cuckoo Hashing

Nikolaos Fountoulakis, Konstantinos Panagiotou, Angelika Steger

Research output: Working paper/PreprintWorking paper


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.
Original languageEnglish
PublisherCornell University Library
Number of pages27
Publication statusPublished - 2013


Dive into the research topics of 'On the Insertion Time of Cuckoo Hashing'. Together they form a unique fingerprint.

Cite this