散列 - M 应该是 2 的幂

Question

听说knuth乘法哈希中m应该是2的幂。否则，二的幂总是一个不错的选择。有人可以简单地告诉我为什么这样更有效吗？

亲切的问候

Answer 1

对于上下文，Knuth 乘法哈希的一般形式是这样的：

如果w = 2³²且M为2^位，则这简化为

h(K) = A * K >> (32 - bits)

这显然非常好。诀窍是将除以 w 留到以后使用，使用 mod w （这是自动的），然后从 top 中提取，但是如果它是，我们会得到很多位以正常方式完成（这对应于除以 w，按比例缩小，然后做 floor - 一次完成）。

但是这个技巧依赖于 w 和 M 是 2 的幂。如果 M 不是 2 的幂，则会有另一个定点乘法（而不是右移）来映射
的中间结果 [0 .. 2³²-1] 到 [0 .. M-1]，并且由于 M 不会除以 2³² 那也在分布中引入偏差。