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

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\ge 3$ random hashes, let $c_d^{\ast }$ 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\ge 3$ hashes and load factor $c<c_d^{\ast }$, the expectation of the random walk insertion time is $O(1)$, that is, a constant depending only on $d$ and $c$ but not $m$.

arXiv commentA preliminary version of this paper appeared in FOCS 2024. Major update from v4 to v6 to fix errors in the previous version and include the $d=3$ case. Minor update to v7. 34 pages