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

在计算散列时,您需要尽可能多的信息,以便在整个比特范围内以较低的成本将其分解为具有良好分布的信息:例如,32位无符号整数通常是好的,除非您有大量(>30亿)项要存储在散列表中。

它将散列代码转换成您真正感兴趣的bucket索引。当bucket数n是2的幂时,只需要在散列码h和(n-1)之间做一个and操作,结果等于h mod n。

这可能不好的一个原因是和操作只是从哈希代码中丢弃位(高级位)。这可能是好的或坏的,取决于其他事情。一方面,它将非常快,因为和比除法快得多(这也是为什么你选择使用2个桶的幂的通常原因),但另一方面,较差的哈希函数在较低的位中可能具有较差的熵:即,当被哈希的数据发生变化时,较低的位变化不大。

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