为什么仅将质数用于哈希函数除法

Question

使用除法散列意味着h（k）= k mod m。我读过

m不应为2的幂。这是因为如果m = 2 ^ p，则h变为只是k的p个最低位。通常我们选择m作为素数数字不太接近2的幂。

有人可以用一个小例子来说明最低位部分吗？我认为（mod m）所做的就是将结果包装在m范围内。如果m是2的幂，则某种程度上看不到问题。

Answer 1

计算机中的所有数据都存储为二进制数据。二进制数写在base-2中。

如果对数据进行散列，则要创建一个易于比较的指纹。如果我们有与原始数据不完全相同的相似数据，则不应创建相同的指纹（哈希）。

[如果在m = 2^p (p is int >= 0)中使用m，会发生什么情况。例如，因为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远的数字的原因。这样，最左位在计算散列时很重要，并且两个相似的数据片段创建相同的散列的可能性要小得多。

Answer 2

除数的余数*可以通过重复去除除数直到待除数小于除数来计算。对于二进制数和两个除数的幂，此减法仅影响左侧的位，使其为0，但使右侧的位保持不变。