On the insertion time of random walk cuckoo hashing. Issue 4 (21st September 2018)

• Record Type: Journal Article
• Authors: Frieze, Alan; Johansson, Tony
• Is Part Of: Random structures & algorithms. Volume 54:Issue 4(2019)
• Page Start: 721
• Page End: 729
• Publication Date: 2018-09-21
• Subjects: Cuckoo hashing -- random walk -- insertion time; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20808
• Languages: English
• ISSNs: 1042-9832

Abstract

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.