论文标题
随机步行杜鹃的插入时间以下脱皮门槛
Insertion Time of Random Walk Cuckoo Hashing below the Peeling Threshold
论文作者
论文摘要
大多数哈希表的插入时间为$ O（1）$，可能是根据预期和/或摊销的资格。虽然插入杜鹃丛中的桌子似乎确实花费了$ O（1）$预期的时间，但除了最简单的实际相关案例外，只有polyrogarithmic的保证才能证明。鉴于杜鹃的广泛使用来实施紧凑的词典和绽放过滤器的替代方案，因此缩小此差距是理论家的重要开放问题。 In this paper, we show that random walk insertions into cuckoo hash tables take $O(1)$ expected amortised time when any number $k \geq 3$ of hash functions is used and the load factor is below the corresponding peeling threshold (e.g. $\approx 0.81$ for $k = 3$).据我们所知，这是对杜鹃的持续时间插入的第一个有意义的保证，该保证适用于\ {3，\ dots，9 \} $。 除了本身有用外，我们希望我们的以钥匙为中心的分析方法可以成为实现最终目标的道路上的垫脚石：$ o（1）$（1）$时间插入所有负载阈值以下的负载因子的时间插入（例如，$ \ $ \ 0.91 $ for $ k = 3 $）。
Most hash tables have an insertion time of $O(1)$, possibly qualified as expected and/or amortised. While insertions into cuckoo hash tables indeed seem to take $O(1)$ expected time in practice, only polylogarithmic guarantees are proven in all but the simplest of practically relevant cases. Given the widespread use of cuckoo hashing to implement compact dictionaries and Bloom filter alternatives, closing this gap is an important open problem for theoreticians. In this paper, we show that random walk insertions into cuckoo hash tables take $O(1)$ expected amortised time when any number $k \geq 3$ of hash functions is used and the load factor is below the corresponding peeling threshold (e.g. $\approx 0.81$ for $k = 3$). To our knowledge, this is the first meaningful guarantee for constant time insertion for cuckoo hashing that works for $k \in \{3,\dots,9\}$. In addition to being useful in its own right, we hope that our key-centred analysis method can be a stepping stone on the path to the true end goal: $O(1)$ time insertions for all load factors below the load threshold (e.g. $\approx 0.91$ for $k = 3$).
