We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
On the insertion time of random walk cuckoo hashing.
- Authors
Frieze, Alan; Johansson, Tony
- Abstract
Cuckoo Hashing is a hashing scheme invented by pervious study of Pagh and Rodler. It uses d ≥ 2 distinct hash functions to insert n items into the hash table of size m = (1 + ε)n. In their original paper they treated d = 2 and m = (2 + ε)n. It has been an open question for some time as to the expected time for Random Walk Insertion to add items when d > 2. We show that if the number of hash functions d ≥ dε = O(1) then the expected insertion time is O(1) per item.
- Subjects
RANDOM walks; CUCKOOS; HASHING; OPEN-ended questions
- Publication
Random Structures & Algorithms, 2019, Vol 54, Issue 4, p721
- ISSN
1042-9832
- Publication type
Article
- DOI
10.1002/rsa.20808