为什么哈希函数应该使用素数模数？

通常一个简单的散列函数通过获取输入的“组成部分”（字符串的情况下的字符），并将它们乘以某个常数的幂，然后将它们以某种整数类型相加。因此，例如，字符串的典型（虽然不是特别好）散列可能是：

(first char) + k * (second char) + k^2 * (third char) + ...

然后，如果输入了一堆都具有相同的第一个字符的字符串，那么结果将都是相同的模 k，至少直到整数类型溢出。

[例如，Java 的字符串 hashCode 与此非常相似——它使字符倒序，k=31。因此，您会在以相同方式结束的字符串之间获得惊人的模 31 关系，以及在除接近结尾之外相同的字符串之间获得模2 ^ 32 的惊人关系。这不会严重破坏哈希表的行为。]

哈希表通过将哈希的模数与桶的数量相乘来工作。

在哈希表中重要的是不要在可能的情况下产生冲突，因为冲突会降低哈希表的效率。

现在，假设有人将一大堆值放入一个哈希表中，这些值在项目之间具有某种关系，就像所有值都具有相同的第一个字符。这是一个相当可预测的使用模式，我想说，所以我们不希望它产生太多的冲突。

事实证明，“由于数学的性质”，如果散列中使用的常数和桶的数量是 coprime，那么在某些常见情况下可以最大限度地减少冲突。如果它们不是 coprime，那么在输入之间存在一些相当简单的关系，其冲突没有被最小化。所有的哈希值都以公因数为模，这意味着它们都将落入具有以公因数为模的值的桶的 1/n 中。你会得到 n 倍的碰撞，其中 n 是公因数。由于 n 至少为 2，我想说对于一个相当简单的用例来说，产生至少两倍于正常情况的碰撞是不可接受的。如果某个用户要将我们的分发分成几桶，我们希望它是一个奇怪的意外，而不是一些简单的可预测的使用。

现在，哈希表实现显然无法控制放入其中的项目。他们无法阻止他们发生关系。所以要做的是确保常数和桶数互质。这样，您就不会单独依赖“最后一个”组件来确定桶的模数相对于一些小的公因数。据我所知，他们不必是素数来实现这一点，只需互素即可。

但是如果hash函数和hashtable是独立写的，那么hashtable就不知道hash函数是怎么工作的。它可能使用带有小因子的常数。如果幸运的话，它的工作方式可能完全不同并且是非线性的。如果哈希足够好，那么任何桶数都可以。但是偏执的哈希表不能假设一个好的哈希函数，所以应该使用质数的桶。类似地，偏执散列函数应该使用较大的素数常数，以减少有人使用多个恰好与常数具有共同因子的桶的机会。

在实践中，我认为使用 2 的幂作为存储桶的数量是相当正常的。这很方便，并且不必四处搜索或预先选择正确大小的素数。因此，您依靠哈希函数不使用偶数乘数，这通常是一个安全的假设。但是您仍然会偶尔遇到基于上述哈希函数的不良哈希行为，而素数桶计数可以进一步提供帮助。

据我所知，提出“一切都必须是素数”的原则是在哈希表上进行良好分布的充分但不是必要条件。它允许每个人进行互操作，而无需假设其他人遵循相同的规则。

[编辑：使用质数桶还有另一个更专业的原因，即如果您使用线性探测处理冲突。然后你从哈希码计算一个步幅，如果这个步幅是桶数的一个因素，那么你只能在你回到你开始的地方之前做 (bucket_count / stride) 探测。你最想避免的情况是 stride = 0，当然，它必须是特殊情况，但为了避免也特殊情况 bucket_count / stride 等于一个小整数，你可以让 bucket_count 素数而不关心什么提供的步幅不为 0。]

---

从哈希表中插入/检索时，您要做的第一件事是计算给定键的 hashCode，然后通过执行 hashCode % table_length 将 hashCode 修剪为 hashTable 的大小来找到正确的存储桶。以下是您很可能在某处读过的 2 条“声明”

如果对 table_length 使用 2 的幂，则查找 (hashCode(key) % 2^n ) 与 (hashCode(key) & (2^n -1)) 一样简单快捷。但是，如果您计算给定键的 hashCode 的函数不好，那么您肯定会受到在几个哈希桶中聚集许多键的影响。但是如果你对 table_length 使用素数，即使你有一个稍微愚蠢的 hashCode 函数，计算出来的 hashCodes 也可以映射到不同的 hash 桶中。

这就是证据。

如果假设您的 hashCode 函数导致以下 hashCodes 以及其他 {x, 2x, 3x, 4x, 5x, 6x...}，那么所有这些都将聚集在 m 个桶中，其中 m = table_length/GreatestCommonFactor （表长度，x）。 （验证/推导这一点很简单）。现在您可以执行以下操作之一来避免集群

确保您不会生成太多的 hashCodes，这些 hashCodes 是另一个 hashCode 的倍数，例如 {x, 2x, 3x, 4x, 5x, 6x...}。但是如果您的 hashTable 应该有这可能有点困难数以百万计的条目。或者简单地通过使 GreatestCommonFactor(table_length, x) 等于 1 使 m 等于 table_length，即通过使 table_length 与 x 互质。如果 x 几乎可以是任何数字，那么请确保 table_length 是质数。

从 - http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

---

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

很清楚的解释，还有图片。

编辑：总而言之，使用素数是因为在将值乘以所选素数并将它们全部相加时，您最有可能获得唯一值。例如，给定一个字符串，将每个字母值与质数相乘，然后将它们全部相加将得到它的哈希值。

一个更好的问题是，为什么是数字 31？

---

tl;博士

index[hash(input)%2] 将导致所有可能的哈希值的一半和一系列值发生冲突。 index[hash(input)%prime] 导致所有可能的哈希值小于 2。将除数固定为表大小还可以确保数字不能大于表。

---

使用素数是因为您很有可能获得使用多项式模 P 的典型哈希函数的唯一值。比如说，您将这种哈希函数用于长度 <= N 的字符串，并且您有冲突。这意味着 2 个不同的多项式产生相同的模 P 值。这些多项式的差异再次是相同次数 N（或更小）的多项式。它有不超过 N 个根（这就是数学的本质，因为这种说法仅适用于域上的多项式 => 素数）。因此，如果 N 远小于 P，则很可能不会发生碰撞。之后，实验可能会证明 37 足够大，可以避免长度为 5-10 的字符串哈希表的冲突，并且足够小以用于计算。

---

只是为了放下从答案中收集的一些想法。

散列使用模数，因此任何值都可以适合给定范围

我们想要随机化碰撞

随机化碰撞意味着没有模式可以作为碰撞发生的方式，或者，改变输入中的一小部分会导致完全不同的哈希值

为了随机化碰撞，避免使用底数（十进制的 10，十六进制的 16）作为模数，因为 11 % 10 -> 1, 21 % 10 -> 1, 31 % 10 -> 1，它显示了哈希值的清晰模式分布：最后一位数字相同的值会发生冲突

避免使用基数 (10^2, 10^3, 10^n) 作为模数，因为它也会创建一个模式：具有相同最后 n 位数字的值会发生冲突

实际上，避免使用任何具有自身和 1 以外的因子的东西，因为它会创建一个模式：一个因子的倍数将被散列为选定的值

例如，9 有 3 作为因子，因此 3, 6, 9, ...999213 将始终被散列为 0, 3, 6

12 有 3 和 2 作为因子，因此 2n 将始终散列为 0、2、4、6、8、10，而 3n 将始终散列为 0、3、6、9

如果输入不是均匀分布的，这将是一个问题，例如，如果许多值是 3n，那么我们只能得到所有可能哈希值的 1/3，并且冲突很高

因此，通过使用素数作为模数，唯一的模式是模数的倍数将始终散列为 0，否则散列值分布均匀分布

---

只是为了提供另一种观点，有这个网站：

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

它认为您应该使用尽可能多的存储桶，而不是四舍五入到一个质数的存储桶。这似乎是一个合理的可能性。直观地说，我当然可以看到更多数量的存储桶会更好，但我无法对此进行数学论证。

---

这取决于哈希函数的选择。

许多散列函数通过将数据中的各种元素与一些因子相乘来组合数据中的各种元素，这些因子对应于机器的字长（该模数是免费的，只需让计算溢出）。

您不希望数据元素的乘数与哈希表的大小之间存在任何公因子，因为这样可能会发生改变数据元素不会将数据分布到整个表的情况。如果您为表格的大小选择一个素数，那么这样一个共同因素是极不可能的。

另一方面，这些因素通常由奇数组成，因此您也应该安全地为哈希表使用 2 的幂（例如 Eclipse 在生成 Java hashCode() 方法时使用 31）。

---

关于素幂模的“数学本质”是它们是finite field的一个组成部分。另外两个构建块是加法和乘法运算。素数模数的特殊性质是它们通过“常规”加法和乘法运算形成一个有限域，仅取模数。这意味着每次乘法都映射到以素数为模的不同整数，每次加法也是如此。

素数模数是有利的，因为：

在二级散列中选择二级乘数时，它们提供了最大的自由度，除 0 之外的所有乘数最终将只访问所有元素一次

如果所有哈希都小于模数，则根本不会发生冲突

随机素数比两个模数的幂更好地混合，并压缩所有位的信息而不仅仅是一个子集

然而，它们有一个很大的缺点，它们需要整数除法，即使在现代 CPU 上也需要很多（~ 15-40）个周期。大约一半的计算可以确保哈希很好地混合在一起。两次乘法和异或移位操作将比素数模数更好地混合。然后我们可以使用任何哈希表大小和哈希减少最快的方法，总共为 2 个表大小的幂提供 7 个操作，而对于任意大小，总共提供大约 9 个操作。

我最近查看了许多 fastest hash table implementations，其中大多数不使用素数模数。

哈希表索引的分布主要取决于使用的哈希函数。 素数模数不能修复错误的散列函数，good hash function 不能从素数模数中受益。 但在某些情况下它们可能是有利的。例如，它可以修复一个半坏的哈希函数。

---

素数是唯一的数字。它们的独特之处在于，素数与任何其他数字的乘积最有可能是唯一的（当然，不像素数本身那么独特），因为它使用了素数。此属性用于散列函数。给定一个字符串“Samuel”，您可以通过将每个组成数字或字母与质数相乘并将它们相加来生成唯一的哈希。这就是使用素数的原因。然而，使用素数是一项古老的技术。这里要理解的关键是，只要您可以生成足够唯一的密钥，您也可以转移到其他散列技术。转到此处了解有关此主题的更多信息 http://www.azillionmonkeys.com/qed/hash.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

---

从我的其他答案 https://stackoverflow.com/a/43126969/917428 复制。有关更多详细信息和示例，请参阅它。

我相信这与计算机以 2 为基数工作这一事实有关。想想同样的事情如何以 10 为基数工作：

8 % 10 = 8

18 % 10 = 8

87865378 % 10 = 8

数字是多少并不重要：只要它以 8 结尾，它的模 10 就是 8。

选择一个足够大的、非二次幂的数字将确保散列函数确实是所有输入位的函数，而不是它们的子集。

---

假设您的表格大小（或模数）是 T = (B*C)。现在，如果您输入的哈希值类似于 (N*A*B) ，其中 N 可以是任何整数，那么您的输出将不会很好地分布。因为每次 n 变为 C、2C、3C 等时，您的输出都会开始重复。即您的输出将仅分布在 C 位置。注意这里的 C 是 (T / HCF(table-size, hash))。

这个问题可以通过将 HCF 设为 1 来解决。素数对此非常有用。

另一个有趣的事情是当 T 为 2^N 时。这些将给出与输入哈希的所有低 N 位完全相同的输出。由于每个数字都可以表示为 2 的幂，所以当我们将任何数字与 T 取模时，我们将减去 2 形式数字的所有幂，即 >= N，因此总是给出特定模式的数量，具体取决于输入.这也是一个糟糕的选择。

同样，由于类似的原因，T as 10^N 也很糟糕（数字的十进制而不是二进制的模式）。

因此，素数往往会给出更好的分布结果，因此是表大小的不错选择。

---

我想为史蒂夫杰索普的回答添加一些东西（我无法评论它，因为我没有足够的声誉）。但我找到了一些有用的材料。他的回答很有帮助，但他犯了一个错误：桶大小不应该是 2 的幂。我将引用 Thomas Cormen、Charles Leisersen 等人在第 263 页的“算法简介”一书：

在使用除法时，我们通常会避免某些 m 值。例如，m 不应该是 2 的幂，因为如果 m = 2^p，那么 h(k) 只是 k 的 p 个最低位。除非我们知道所有低阶 p 位模式的可能性相同，否则我们最好将散列函数设计为依赖于密钥的所有位。正如练习 11.3-3 要求你展示的那样，当 k 是一个以基数 2^p 解释的字符串时选择 m = 2^p-1 可能是一个糟糕的选择，因为置换 k 的字符不会改变它的哈希值。

希望能帮助到你。

---

这个问题与更合适的问题合并，为什么哈希表应该使用素数大小的数组，而不是 2 的幂。对于哈希函数本身，这里有很多很好的答案，但对于相关问题，为什么一些安全关键哈希表，像 glibc 一样，使用素数大小的数组，目前还没有。

一般来说，2张桌子的力量要快得多。有昂贵的 h % n => h & bitmask，其中位掩码可以通过大小为 n 的 clz（“计数前导零”）来计算。模函数需要进行整数除法，这比逻辑 and 慢约 50 倍。有一些技巧可以避免取模，例如使用 Lemire 的 https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/，但通常快速哈希表使用 2 的幂，而安全哈希表使用素数。

为什么这样？

在这种情况下，安全性是通过对冲突解决策略的攻击来定义的，对于大多数哈希表来说，它只是在冲突链表中进行线性搜索。或者用更快的开放寻址表直接在表中进行线性搜索。因此，借助 2 个表的能力和表的一些内部知识，例如某些 JSON 接口提供的键列表的大小或顺序，您可以获得使用的正确位数。位掩码上的个数。这通常低于 10 位。对于 5-10 位，即使使用最强和最慢的哈希函数，暴力冲突也是微不足道的。您不再获得 32 位或 64 位哈希函数的全部安全性。重点是使用快速的小哈希函数，而不是像 murmur 甚至 siphash 这样的怪物。

因此，如果您为哈希表提供外部接口，例如 DNS 解析器、编程语言……您想关心那些喜欢 DOS 此类服务的滥用者。对于这些人来说，用更简单的方法关闭你的公共服务通常更容易，但它确实发生了。所以人们确实在乎。

因此，防止此类碰撞攻击的最佳选择是

1）使用素数表，因为那时

所有 32 位或 64 位都与找到存储桶相关，而不仅仅是少数。

哈希表调整大小功能比双倍更自然。最好的增长函数是斐波那契数列，素数比加倍更接近。

2）针对实际攻击使用更好的措施，以及2大小的快速功率。

计数碰撞并在检测到的攻击上中止或休眠，这是概率<1％的碰撞数。就像 100 和 32 位哈希表一样。这就是例如 djb 的 dns 解析器所做的。

当检测到碰撞攻击时，使用 O(log n) 搜索而不是 O(n) 将碰撞链接列表转换为树。这就是例如 java 所做的。

有一个广泛流传的神话，即更安全的哈希函数有助于防止此类攻击，正如我所解释的那样，这是错误的。只有低位没有安全性。这仅适用于素数大小的表，但这将使用两种最慢的方法的组合，慢散列加慢素模。

哈希表的哈希函数主要需要小（可内联）和快速。安全性只能来自防止冲突中的线性搜索。并且不要使用非常糟糕的散列函数，比如对某些值不敏感的散列函数（比如使用乘法时的 \0）。

使用随机种子也是一个不错的选择，人们首先从它开始，但是如果有足够的表信息，即使是随机种子也无济于事，动态语言通常使得通过其他方法获取种子变得微不足道，因为它存储在已知的内存位置。

---

我想说 this link 的第一个答案是我找到的关于这个问题的最清楚的答案。

考虑一组键 K = {0,1,...,100} 和一个哈希表，其中桶数为 m = 12。由于 3 是 12 的因数，因此将散列 3 的倍数的键到 3 的倍数的桶：

密钥 {0,12,24,36,...} 将被散列到存储桶 0。

密钥 {3,15,27,39,...} 将被散列到存储桶 3。

密钥 {6,18,30,42,...} 将被散列到存储桶 6。

密钥 {9,21,33,45,...} 将被散列到存储桶 9。

如果 K 是均匀分布的（即 K 中的每个键出现的可能性相同），那么 m 的选择就不是那么关键了。但是，如果 K 不是均匀分布的，会发生什么？想象一下，最有可能出现的键是 3 的倍数。在这种情况下，所有不是 3 的倍数的桶都很有可能是空的（这在哈希表性能方面确实很糟糕）。

这种情况比它看起来更常见。例如，想象一下，您正在根据对象在内存中的存储位置跟踪对象。如果您的计算机的字长是 4 个字节，那么您将散列 4 的倍数的键。不用说，选择 m 为 4 的倍数将是一个糟糕的选择：您将有 3m/4 个完全空的桶，并且您的所有密钥都在剩余的 m/4 个存储桶中发生冲突。

一般来说：

K 中与桶数 m 共享一个公因子的每个键将被散列到一个是该因子的倍数的桶。

因此，为了尽量减少碰撞，重要的是减少 m 和 K 的元素之间的公因数的数量。如何实现呢？通过将 m 选择为具有很少因数的数：质数。

来自 Mario 的回答。

---

对于散列函数，不仅要尽量减少一般的冲突，而且要使在改变几个字节时不可能保持相同的散列。

假设您有一个等式：(x + y*z) % key = x 与 0<x<key 和 0<z<key。如果 key 是素数 n*y=key 对于 N 中的每个 n 为真，对于其他每个数字为假。

key 不是主要例子的例子：x=1, z=2 和 key=8 因为 key/z=4 仍然是一个自然数，4 成为我们方程的解，在这种情况下 (n/2) *y = key 对于 N 中的每个 n 都为真。由于 8 不是素数，因此方程的解数实际上翻了一番。

如果我们的攻击者已经知道 8 是方程的可能解，他可以将文件从产生 8 更改为 4 并且仍然获得相同的哈希。

---

我已经阅读了上面一些热门答案中链接的热门 wordpress 网站。根据我的理解，我想分享一个简单的观察。

您可以在文章 here 中找到所有详细信息，但假设以下情况成立：

使用素数为我们提供了唯一值的“最佳机会”

一个通用的 hashmap 实现需要两件事是唯一的。

密钥的唯一哈希码

存储实际值的唯一索引

我们如何获得唯一索引？通过使内部容器的初始大小也成为素数。所以基本上，涉及素数是因为它具有产生唯一数字的独特特性，我们最终使用它来标识对象并在内部容器中查找索引。

例子：

键=“键”

价值=“价值” uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

映射到唯一 ID

现在我们想要一个独特的位置来实现我们的价值 - 所以我们

uniqueId % internalContainerSize == uniqueLocationForValue ，假设 internalContainerSize 也是素数。

我知道这是简化的，但我希望能够通过总体思路。

---