A precise analysis of Cuckoo hashing
A precise analysis of Cuckoo hashing
复制标题
DOI：
10.1145/2151171.2151174
复制
发表时间：
2012-04
期刊：
影响因子：
--
通讯作者：
M. Drmota;Reinhard Kutzelnigg
中科院分区：
文献类型：
--
作者：
M. Drmota;Reinhard Kutzelnigg
布谷鸟散列是由Pagh和Rodler在2001年引入的。它的主要特点是提供恒定的最坏情况搜索时间。本文的目的是提出一个精确的平均情况下分析布谷鸟散列。特别是，我们确定的概率，布谷鸟散列产生没有冲突，并给出一个上限的建设时间，这是线性的表的大小。分析依赖于生成函数的方法，所谓的布谷鸟图，一个随机的二分图，并应用双鞍点方法获得渐近展开。此外，我们提供了一些结果，这些类型的随机图的结构。我们的结果扩展了Devroye和Morin [2003]的分析。此外，我们提供的数值结果证实了数学分析。
Cuckoo hashing was introduced by Pagh and Rodler in 2001. Its main feature is that it provides constant worst-case search time. The aim of this article is to present a precise average case analysis of Cuckoo hashing. In particular, we determine the probability that Cuckoo hashing produces no conflicts and give an upper bound for the construction time, that is linear in the size of the table. The analysis rests on a generating function approach to the so called Cuckoo Graph, a random bipartite graph, and an application of a double saddle point method to obtain asymptotic expansions. Furthermore, we provide some results concerning the structure of these kinds of random graphs. Our results extend the analysis of Devroye and Morin [2003]. Additionally, we provide numerical results confirming the mathematical analysis.