On the insertion time of random walk cuckoo hashing

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.