问散列函数和大小为2^p的表

EN

当计算散列时，你想要尽可能多的信息，因为你可以在整个比特范围内很好地分布:例如，32位无符号整数通常是好的，除非你有很多(>30亿)项要存储在哈希表中。

它将散列代码转换为您真正感兴趣的存储桶索引。当存储桶的数量n是2的幂时，您所需要做的就是在hash代码h和(n-1)之间进行AND操作，结果等于need n。

这可能很糟糕的一个原因是，AND操作只是从散列码中丢弃了位-高级位。这可能是好的，也可能是坏的，这取决于其他事情。一方面，它将非常快，因为和比除法快得多(这也是您选择使用2个桶的幂的原因)，但另一方面，糟糕的散列函数在较低的位可能具有较差的熵:也就是说，当被散列的数据发生变化时，较低的位不会有太多变化。

假设表的大小是m= 2^p，k是一个键。这样，当我们执行k mod m时，我们将只得到k的二进制表示的最后p位。因此，如果我放入几个具有相同最后p位的键，则哈希函数的性能将非常非常差，因为所有键都将被哈希到表中的相同位置。因此，避免2的幂