hash - 为什么Hash函数除法只用素数

Question

使用除法的散列意味着 h(k) = k mod m 。我读到了

m should not be power of 2. This is because if m = 2^p, h becomes just the p lowest-order bits of k. Usually we choose m to be a prime number not too close to a power of 2.

有人可以用一个小例子来解释最低阶位部分吗？我认为所有 (mod m) 所做的就是将结果包裹在范围 m 周围。如果 m 是 2 的幂，不知何故看不到问题。

Answer 1

计算机中的所有数据都存储为二进制数据。二进制数以 2 为基数写入。

如果您对数据进行哈希处理，您希望创建一个易于比较的指纹。如果我们有与原始数据不完全相同的相似数据，则不应创建相同的指纹(哈希)。

猜猜如果你使用 m where m = 2^p (p is int >= 0) 会发生什么.例如，因为 2^7 是 2^4 的倍数，所以从 2^4 剩下的所有位都将减少为 0。您剪掉了部分数据。这意味着如果数据在二进制数的最左侧位不同，它们将创建相同的散列。

例子:

k:    1111111111010101
m:    0000000001000000 (2^6)
k(m): 0000000000010101

现在做同样的事情:

k:    0000000000010101
m:    0000000001000000 (2^6)
k(m): 0000000000010101

嘿，那是同一个哈希!这正是选择远离 2^p 的数字的原因。这样，最左边的位在计算散列时确实很重要，并且两个相似的数据创建相同散列的可能性要小得多。