哈希函数和表格的大小表格2^p

Question

在从密钥的哈希码计算哈希表桶索引时，为什么我们在分区（模）时避免使用余数是2的力量？

Answer 1

在计算散列时，您需要尽可能多的信息，因为您可以在整个位的范围内以低成本实现事物分配，例如： 32位无符号整数通常很好，除非你有大量（> 30亿）的项目存储在散列表中。

它将哈希码转换为您真正感兴趣的桶索引。当桶的数量n是2的乘方时，您需要做的就是在哈希码h和（n -1），结果等于h mod n。

这可能不好的一个原因是AND操作只是简单地丢弃哈希码中的比特 - 高位比特。这可能是好的或坏的，取决于其他事情。一方面，它会非常快，因为AND比分割快很多（并且是你选择使用2个桶数的权力的常见原因），但是另一方面，可能存在较差的哈希函数较低位的熵较差：也就是说，当散列数据改变时，较低位不会有太大变化。

Answer 2

让我们说，表大小是m = 2^p。 让k是一个关键。然后，每当我们做k mod m时，我们只会得到k的二进制表示的最后p个比特。因此，如果我放入几个具有相同最后p位的密钥，散列函数将非常糟糕地执行，因为所有密钥都将散列到表中的同一个插槽。因此，避免幂2