On the Insertion Time of Cuckoo Hashing

Details On the Insertion Time of Cuckoo Hashing On the Insertion Time of Cuckoo Hashing

2010-06-07

arxiv.org/abs/1006.1231v1

Computer Science

Data Structures and Algorithms

26 pages

Scientific 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.

Affiliated with

Also associated with

No associations

Rating

On the Insertion Time of Cuckoo Hashing does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Insertion Time of Cuckoo Hashing, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Insertion Time of Cuckoo Hashing will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-367082