4

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

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

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

4

2 回答 2

6

计算机中的所有数据都存储为二进制数据。二进制数以 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 的数字的原因。这样，最左边的位在计算散列时确实很重要，并且两条相似的数据创建相同散列的可能性要小得多。

于 2014-02-15T12:23:30.727 回答
1

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

  1110001111100001₂   58337
- 0000000100000000₂      2⁸
= 1110001011100001₂   58081
___________________________

  1110001011100001₂   58081
- 0000000100000000₂      2⁸
- 0000000100000000₂      2⁸
  ...
= 0000000011100001₂   57569

当除数不均匀时，重复删除它会影响所有低位：

  1110001111100001₂   58337
- 0000000011000011₂     195
= 1110001100011110₂   58142
___________________________

  1110001111100001₂   58337
- 0000000011000011₂     195
- 0000000011000011₂     195
  ...
= 0000000000100000₂      32

请注意，除数不能被二整除就足够了，因为二的每个因子将二进制数向左移动一位数，而减法只能将数字向左移动，而不能向右移动。

除数离2的幂越远，也就是说，0和1相等的数字越多，每次减法都会影响到余数的更多数字。这意味着例如模数 78985 (10011010010001001₂) 比 65537 (10000000000000001₂) 好得多，即使它不是素数，而 65537 是。

这一切都适用于散列“差”的情况，即在所有输出位中分布不均。如果我们有一个好的散列，我们可以使用所有散列表大小，因此我们想要的除数以及任何范围缩小的方法，如fastrange。

*通常不会像这样实际计算，但结果是等价的

于 2019-10-09T10:03:25.973 回答