On The Insertion Time Of Random Walk Cuckoo Hashing

Frieze Alan, Johansson Tony. Arxiv 2016

[Paper]    
ARXIV Independent

Cuckoo Hashing is a hashing scheme invented by Pagh and Rodler. It uses $d\ge 2$ distinct hash functions to insert items into the hash table. It has been an open question for some time as to the expected time for Random Walk Insertion to add items. We show that if the number of hash functions $d=O(1)$ is sufficiently large, then the expected insertion time is $O(1)$ per item.

Similar Work

• On The Insertion Time Of Cuckoo Hashing
• A Faster Algorithm For Cuckoo Insertion And Bipartite Matching In Large Graphs
• Wear Minimization For Cuckoo Hashing How Not To Throw A Lot Of Eggs Into One Basket
• Cuckoo Hashing In Cryptography Optimal Parameters Robustness And Applications