随机游走d叉布谷鸟哈希的O(1)插入时间可达负载阈值 (O(1) Insertion for Random Walk d-ary Cuckoo Hashing up to the Load Threshold)

from arxiv, In Lemma 4.3 of Section 4 (in the most recent version), there is an error in assuming the independence of events that occur over overlapping time intervals. Therefore, the proof of Theorem 1.1 is not correct as written. We are continuing to work on resolving this issue, with the goal of recovering a proof of Theorem 1.1

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$ 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$ likely exists. We show that for any $d\ge 4$ hashes and load factor $c<c_d^*$, the expectation of the random walk insertion time is $O(1)$, that is, a constant depending only on $d$ and $c$ but not $m$.

翻译：随机游走d叉布谷鸟哈希算法由Fotakis、Pagh、Sanders和Spirakis提出，用于推广并改进Pagh与Rodler的标准布谷鸟哈希算法。该算法具有低空间开销、有保障的快速访问能力以及实际应用中快速的插入时间。本文为该算法提供了插入时间的理论界。具体而言，对于任意$d\ge 3$个哈希函数，令$c_d^*$为负载因子的尖锐阈值，当负载因子达到该阈值时，将$cm$个对象分配到大小为$m$的哈希表中的有效分配方案很可能存在。我们证明：对于任意$d\ge 4$个哈希函数及负载因子$c<c_d^*$，随机游走插入时间的期望值为$O(1)$，即该常数仅取决于$d$和$c$，而与$m$无关。