MAD（乘、加、除）散列函数如何工作？

Question

作为大学项目，我被分配了从头开始创建数据结构（例如 minheap、哈希表等）的任务。然而，哈希表或更具体地说是哈希映射 - 函数给我带来了很多麻烦。我遇到了 MAD（乘法、加法、除法）函数，它基本上是：h(x) = [(a*x + b) % p] % N，其中 a、b：随机整数，p：大质数和 N ：哈希表中的元素数。

我的问题是这个函数是如何（以及为什么）均匀分布哈希表中的值的。

Answer 1

h(x) = [(a*x + b) % p] % N

让我们先单独看一下a*x + b。如果您想象 a 分解为 2 的幂之和，那么 a*x 就是 x 的和左移少量 2 的幂，这样 x 中的每一位 x 影响在 a 中设置的其他位位置，以及当求和在特定位产生进位时的一些其他位。添加 b 混合在另一组随机位中：很像异或运算，但进位有一些额外的复杂性。如果说 x 有一个介于 0 和 255 之间的值，位 abcdefgh（每个都是 0 或 1），那么到目前为止我们有：

         (a&1 ? abcdefgh : 0) +
        (a&2 ? abcdefgh0 : 0) +
       (a&4 ? abcdefgh00 : 0) +
      (a&8 ? abcdefgh000 : 0) +
                     ...      +  // continues for a&16, a&32 etc.
        ABCDEFGHIJKLMNOP         // however many random bits in "b"

因此，在“1s”列中，我们对 h 和 P 求和，这可能会与 g、h 一起进入“2s”列和 O，继续下去。

如果 a 是 37，即 32+4+1，那么我们将添加 x 本身、x << 2 和 x << 5：每一位in x 从而影响散列值中的更多位（这很好，确实有 cryptographic-strength 散列函数，更改密钥中的任何位 - 无论是单个位，一半还是全部 - 应该很漂亮随机翻转散列值中大约一半的位）。

回到完整的公式，假设我们跳过了 % p 而只有 % N，但是当前的 table 大小是二的幂：% N然后等同于 bitwise-AND 一些 less-significant 位的操作。换句话说，它丢弃了我们在 a * x + b 计算的更重要位中建立的大量随机性。因此，为了使哈希函数可以安全地用于任意数量的桶，我们可以首先引入 % p，这意味着如果哈希值中存在与求和步骤中的 power-of-two 个位置相关的模式，它们'有效地分散在 0..p 范围内的随机位置。

假设一个介于 0 和 255 之间的散列 - 如果 N 是 200，我们将散列到 0..55 范围内的桶的可能性是原来的两倍。为了使这种影响不那么明显，我们希望散列值比 MOD 值具有更多的位，并且该原则以分层方式应用于我们应该为 p 和 [=36 选择的值=]:

a * x + b 值应该明显大于 p，并且分布在比 p 大得多的范围内，因此 % p将它们更多地跨桶分开，但是
p 应该比 N 大得多，所以我们没有 low-indexed 具有明显更高碰撞概率的桶（如果你我正在使用线性探测来解决冲突）。

例如，如果我们想支持 N 的值最多为 2²⁴，并且我们使用 32 位无符号整数进行这些计算，因此 a 和 b 具有该范围内的随机值，我们可以拆分差异选择一个大约 2²⁸.

左右的素数

MAD（乘、加、除）散列函数如何工作？

How does the MAD (Multiply, Add, Divide) Hashing function work?

c++

hashtable

hashmap