散列函数和大小为2^p的表
提问于 2008-11-10 03:12:45
当从键的哈希码计算哈希表存储桶索引时，当存储桶数组的大小是2的幂时，为什么我们要避免使用除法(模数)后的余数？
回答 2
Stack Overflow用户
回答已采纳
发布于 2008-11-10 03:21:25
当计算散列时，你想要尽可能多的信息，因为你可以在整个比特范围内很好地分布:例如，32位无符号整数通常是好的，除非你有很多(>30亿)项要存储在哈希表中。
它将散列代码转换为您真正感兴趣的存储桶索引。当存储桶的数量n是2的幂时，您所需要做的就是在hash代码h和(n-1)之间进行AND操作，结果等于need n。
这可能很糟糕的一个原因是，AND操作只是从散列码中丢弃了位-高级位。这可能是好的，也可能是坏的，这取决于其他事情。一方面，它将非常快，因为和比除法快得多(这也是您选择使用2个桶的幂的原因)，但另一方面，糟糕的散列函数在较低的位可能具有较差的熵:也就是说，当被散列的数据发生变化时，较低的位不会有太多变化。
Stack Overflow用户
发布于 2010-12-12 14:54:43
假设表的大小是m= 2^p，k是一个键。这样，当我们执行k mod m时，我们将只得到k的二进制表示的最后p位。因此，如果我放入几个具有相同最后p位的键，则哈希函数的性能将非常非常差，因为所有键都将被哈希到表中的相同位置。因此，避免2的幂
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/277638
复制相关文章
腾讯云开发者
