Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
Explicit and Efficient Hash Families Suffice for Cuckoo Hashing with a Stash
复制标题
DOI：
10.1007/s00453-013-9840-x
复制
发表时间：
2012-04
期刊：
影响因子：
1.1
通讯作者：
Martin Aumüller;Martin Dietzfelbinger;Philipp Woelfel
中科院分区：
文献类型：
--
作者：
Martin Aumüller;Martin Dietzfelbinger;Philipp Woelfel
结果表明，布谷鸟散列与藏匿提出的基尔希等人。（Proc.16th European Symposium on Algorithms（ESA），pp.611 -622，Springer，柏林，2008）可以使用非常简单的散列函数族，保持有利的性能保证：在恒定的存储大小的情况下，散列的概率为O（1/ns+1），在最坏的情况下，查找时间和删除时间为O（s），并且摊销的预期插入时间也为O（s）。代替Kirsch等人和Kutzelnigg（Discrete Math. Theor. Comput.科学，12（3）：81-102，2010）（相应地，标准布谷鸟散列的Θ（logn）明智独立性）新方法甚至使用2明智独立散列族作为构建块。构造和分析都建立在Dietzfelbinger和Woelfel的工作基础上（Proc.35th ACM Symp.计算理论（STOC），第629-638页，2003）。分析，这也可以适用于完全随机的情况下，利用图计数参数，是比以前的证明简单得多。结果可以推广到的情况下，隐藏大小是不恒定的。
It is shown that for cuckoo hashing with a stash as proposed by Kirsch et al. (Proc. 16th European Symposium on Algorithms (ESA), pp. 611–622, Springer, Berlin, 2008) families of very simple hash functions can be used, maintaining the favorable performance guarantees: with constant stash sizesthe probability of a rehash isO(1/ns+1), the lookup time and the deletion time areO(s) in the worst case, and the amortized expected insertion time isO(s) as well. Instead of the full randomness needed for the analysis of Kirsch et al. and of Kutzelnigg (Discrete Math. Theor. Comput. Sci., 12(3):81–102, 2010) (resp.Θ(logn)-wise independence for standard cuckoo hashing) the new approach even works with 2-wise independent hash families as building blocks. Both construction and analysis build upon the work of Dietzfelbinger and Woelfel (Proc. 35th ACM Symp. on Theory of Computing (STOC), pp. 629–638, 2003). The analysis, which can also be applied to the fully random case, utilizes a graph counting argument and is much simpler than previous proofs. The results can be generalized to situations where the stash size is non-constant.