hash-function - 为什么 mod 的好选择是 "a prime not too close to an exact of 2"

Question

要生成散列函数，通过将 k 的余数除以 m 将 key k 映射到 m 个槽之一。也就是说，哈希函数是

h(k) = k mod m。

我在几个地方读到， m 是一个不错的选择

素数 - 我知道我们想要去除公因数，因此选择素数

不太接近 2 的精确幂 - 为什么会这样？

Answer 1

从算法介绍:

When using the division method we avoid certain values of m. For example m should not be power of 2. Since if m=2^p then h(k) is p lowest-order bits of k. Unless it is known that all low-order p-bit patterns are equally likely,
it is better to make a hash function depend on all bits of the key.

正如你从下图中看到的，如果我选择了 2^3，这意味着 p=3 和 m=8。散列的键只依赖于最低的 3(p) 位，这是不好的，因为当您进行散列时，您希望包含尽可能多的数据以获得良好的分布。