O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold

2024/01/25 by Tolson Bell, Alan Frieze, Bell, Tolson +1 · 1 citation
Computer Science · Biochemistry, Genetics and Molecular Biology · #Algorithms and Data Compression #Advanced Image and Video Retrieval Techniques #Hedgehog Signaling Pathway Studies

paper · pdf · doi:10.48550/arxiv.2401.14394

Abstract

The random walk d-ary cuckoo hashing algorithm was defined by Fotakis, Pagh, Sanders, and Spirakis to generalize and improve upon the standard cuckoo hashing algorithm of Pagh and Rodler. Random walk d-ary cuckoo hashing has low space overhead, guaranteed fast access, and fast in practice insertion time. In this paper, we give a theoretical insertion time bound for this algorithm. More precisely, for every d≥ 3 random hashes, let c_d^* be the sharp threshold for the load factor at which a valid assignment of cm objects to a hash table of size m exists with high probability. We show that for any d≥ 3 hashes and load factor c

Cited by

• Fast Insertion for Bucketized Cuckoo Hashing

Related

• On the insertion time of random walk cuckoo hashing
• On the Insertion Time of Cuckoo Hashing
• Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold
• Efficient d-ary Cuckoo Hashing at High Load Factors by Bubbling Up
• Fast Insertion for Bucketized Cuckoo Hashing