hide
Free keywords:
Computer Science, Data Structures and Algorithms, cs.DS
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.
