On the insertion time of random walk cuckoo hashing

Alan Frieze, Tony Johansson

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…