论文标题
广泛的杜鹃藏有藏匿处，重新审视
Generalized Cuckoo Hashing with a Stash, Revisited
论文作者
论文摘要
杜鹃哈希是一种常见的哈希技术，可以保证在最坏的情况下持续的时间查找。 Kirsch，Mitzenmacher和Sicomp 2010的Wieder提出了储藏室，以减少失败的概率（即有效的杜鹃分配不存在的概率）。此后，它已成为加密术等领域的一种标准技术，那里经常需要忽略不计的故障可能性。我们专注于杜鹃哈希的扩展，每个杜鹃均允许每个水桶多个项目，从而改善了负载因子。在存在藏匿处的情况下，Kirsch \ emph {et al。}也分析了该扩展。特别是，让$ d $是每个存储桶的项目数，而$ s $是藏匿大小，kirsch \ emph {et al。}表明，对于常数$ d $和$ s $，失败概率为$ \ nathcal {o}（o}（n^（n^{（s+1）（1-d）（1-d）}）$。在本文中，我们首先在Kirsch \ emph {et al。}的分析中报告一个错误，该错误通过显示一个导致失败$ω（n^{ - d-s-1}）$的反示例概率。然后，我们提供了（几乎）任意$ d $和$ s $的故障概率的一般分析和上限，而不仅仅是恒定，这对于密码学应用程序很有用。我们最终从一般分析中推导出一个紧密的限制$θ（n^{ - d-s}）$，用于失败的可能性，对于常数$ d $和$ s $。
Cuckoo hashing is a common hashing technique, guaranteeing constant-time lookups in the worst case. Adding a stash was proposed by Kirsch, Mitzenmacher, and Wieder at SICOMP 2010, as a way to reduce the probability of failure (i.e., the probability that a valid Cuckoo assignment fails to exist). It has since become a standard technique in areas such as cryptography, where a negligible probability of failure is often required. We focus on an extension of Cuckoo hashing that allows multiple items per bucket, which improves the load factor. That extension was also analyzed by Kirsch \emph{et al.} in the presence of a stash. In particular, letting $d$ be the number of items per bucket, and $s$ be the stash size, Kirsch \emph{et al.} showed that, for constant $d$ and $s$, the failure probability is $\mathcal{O}(n^{(s+1)(1-d)})$. In this paper, we first report a bug in the analysis by Kirsch \emph{et al.} by showing a counter-example leading to an asymptotically-larger probability of failure $Ω(n^{-d-s-1})$. Then we provide a general analysis and upper bound of the failure probability for (almost) arbitrary $d$ and $s$, instead of just constant, which is useful for applications in cryptography. We finally deduce from the general analysis a tight bound $Θ(n^{-d-s})$ for the probability of failure, for constants $d$ and $s$.
