hash - 散列 - M 应该是 2 的幂

Question

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

亲切的问候

Answer 1

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

如果 w = 2 ³²并且 M 是 2 ^bits，那么这简化为

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

这显然非常好。诀窍是将除以 w 留待以后使用mod w（这是自动的），然后从顶部提取如果以正常方式完成，我们会得到多少位（这对应于除以 w，缩小由 M，并做地板 - 一次）。

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