On the insertion time of random walk cuckoo hashing. Issue 4 (21st September 2018) - 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.