c++ - MAD(乘、加、除)散列函数如何工作？

Question

作为一个大学项目，我被分配了从头开始创建数据结构(例如 minheap、哈希表等)的任务。然而，哈希表或更具体地说是 HashMap - 函数给我带来了很多麻烦。我遇到了 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分解为二的幂之和，a*x那么是x的总和将位左移少量的 2 的幂，使得 x 中的每一位影响 a 中设置的其他位位置，以及当求和产生特定位进位时的一些其他位。添加b混入另一组随机位:很像异或运算，但进位有一些额外的复杂性。如果说x has 是一个介于 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 ，它可能会带入“2s”列 g , h和 O ，然后继续。

如果a比如说 37，也就是 32+4+1，那么我们要加上 x本身，x << 2 , 和 x << 5 : x 中的每一位从而影响散列值中的更多位(这很好，实际上使用加密强度散列函数，更改 key 中的任何位 - 无论是单个位，一半还是全部 - 应该几乎随机翻转大约一半的位哈希值)。

回到完整的公式，假设我们跳过了 % p并且刚刚 % N , 但当前表大小是二的幂:% N然后等同于对一些较低有效位的按位与运算。换句话说，它丢弃了我们在 a * x + b 的更重要位中建立的大量随机性。计算。因此，为了使哈希函数可以安全地用于任意数量的桶，我们可以引入 % p首先，这意味着如果哈希值中存在与求和步骤中的二次幂位置相关的模式，它们实际上分散在 0..p 范围内的随机位置。

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

• a * x + b值应该明显大于 p ，并且分布在比 p 大得多的范围内, 所以 % p将它们更多地跨桶分开，但是

• p应该比 N 大得多，因此我们没有具有明显更高碰撞概率的低索引桶(如果您使用线性探测来解决碰撞，这尤其糟糕)。

例如，如果我们想支持 N 的值最多 2²⁴，我们使用 32 位无符号整数进行这些计算所以 a和 b有那个范围内的随机值，我们可能会 split 差异选择一个大约 2²⁸ 左右的素数。