TY - UNPB
T1 - On the Insertion Time of Cuckoo Hashing
AU - Fountoulakis, Nikolaos
AU - Panagiotou, Konstantinos
AU - Steger, Angelika
PY - 2013
Y1 - 2013
N2 - 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.
AB - 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.
M3 - Working paper
BT - On the Insertion Time of Cuckoo Hashing
PB - Cornell University Library
ER -