data-structures - 哈希函数和表格大小为 2^p 的表

Question

在从一个键的​​哈希码计算哈希表桶索引时，为什么当桶数组的大小是 2 的幂时，我们避免使用除法后的余数（模）？

Answer 1

在计算散列时，您需要尽可能多的信息，并且可以在整个位范围内以良好的分布情况廉价地将其转换为：例如，32 位无符号整数通常是好的，除非您有很多（> 30 亿）项要存储在哈希表中。

它将哈希码转换为您真正感兴趣的存储桶索引。当存储桶的数量 n 是 2 的幂时，您需要做的就是在哈希码 h 和 (n-1) 之间进行 AND 运算，结果等于 h mod n。

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

Answer 2

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