On risks of using cuckoo hashing with simple universal hash classes
On risks of using cuckoo hashing with simple universal hash classes
复制标题
关于使用带有简单通用哈希类的布谷鸟哈希的风险
DOI：
10.1137/1.9781611973068.87
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Ulf Schellbach
中科院分区：
文献类型：
--
作者：
Martin Dietzfelbinger;Ulf Schellbach
由Pagh和Rodler [10]引入的Cuckoo hashing是一种动态字典数据结构，用于存储来自universeU的setSofnkeys，具有恒定的查找时间和摊销的预期常数插入时间。对于分析，散列函数的空间（2+ n）<$Ω（logn）独立性是足够的。在文献[10]中的实验中，几个较弱的散列类都能很好地工作，然而，某个简单的乘法散列族却不能很好地工作.本文证明了，即使在给定空间4的情况下，当cuckoo散列与乘法类或素域上非常常见的线性散列函数类一起运行时，失败概率也很高.密钥集是完全随机的，但它必须在所有密钥的集合中相对密集（如|S| ≥ |U| 11/12）。在实验中也可以观察到这种不良行为以及这种效应依赖于SinU密度的事实。从不同的角度来看，我们的结果表明，在应用Mitzenmacher和Vadhan（[12]，SODA 2008）的最新结果时必须小心，该结果证明了通用哈希类与具有一定熵的密钥集组合的良好行为。他们的结果适用于cuckoo hashing。[12]中的一个技术假设，即“碰撞概率”或“最大概率”很小的假设，转化为以下条件：|S|相对较小，|U|.我们的结果表明，[12]关于2-泛类的结果不再成立，如果|S|/|U|即使对于非常常见的2-universal hash类和完全随机的密钥集，也不够小。
Cuckoo hashing, introduced by Pagh and Rodler [10], is a dynamic dictionary data structure for storing a setSofnkeys from a universeU, with constant lookup time and amortized expected constant insertion time. For the analysis, space (2+∊)nand Ω(logn)-wise independence of the hash functions is sufficient. In experiments mentioned in [10], several weaker hash classes worked well; however, a certain simple multiplicative hash family worked badly.In this paper, we prove that the failure probability is high when cuckoo hashing is run with the multiplicative class or with the very common class of linear hash functions over a prime field, even if space 4nis provided. The key setSis fully random, but it must be relatively dense in the universeUof all keys (like |S| ≥ |U|11/12). The bad behavior and the fact that this effect depends on the density ofSinUcan also be observed in experiments. The result transfers to larger universes if the keys are chosen from a suitable smaller domain.Viewed from a different perspective, our result illustrates that care must be taken when applying a recent result of Mitzenmacher and Vadhan ([12], SODA 2008) proving good behavior of universal hash classes in combination with key sets that have some entropy. Their result is applicable to cuckoo hashing. A technical hypothesis in [12], namely the assumption that either the “collision probability” or the “maximum probability” is small, translates into the condition that |S| is relatively small in comparison to |U|. Our result shows that the result from [12] on 2-universal classes ceases to hold if |S|/|U| is not small enough, even for very common 2-universal hash classes and fully random key sets.
关于单元探测成员资格的复杂性和完美散列
DOI：
10.1145/380752.380836
发表时间：
2001
期刊：
Current topics in membranes and transport
影响因子：
--
作者：
R. Pagh
通讯作者：
R. Pagh