为什么一个很好的选择mod是"一个不太接近精确2的素数"

Question

为了生成散列函数,通过将k的余数除以m,将密钥k映射到m个时隙之一.也就是说,哈希函数是

h(k)= k mod m.

我已经在几个地方读到了m的好选择

1. 素数 - 我理解我们想要删除公因子,因此选择素数
2. 不太接近2的精确力量 - 为什么会这样？

Answer 1

从算法简介：

当使用除法时，我们避免使用某些 m 值。例如，m 不应该是 2 的幂。因为如果 m=2^p，则 h(k) 是 k 的 p 个最低位。 除非已知所有低阶 p 位模式的可能性相同，
否则最好使哈希函数依赖于密钥的所有位。

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