为什么散列函数使用素数模数？
很久以前，我以1.25美元的价格从便宜的桌子上买了一本数据结构书。 其中，哈希函数的解释说，由于“math的本质”，它最终应该被素数修改。
你对1.25美元的书有什么期望？
无论如何，我已经有数年的时间来思考math的本质了，至今仍然无法解决这个问题。
数字的分布是否真的更加平均，当存在一个素数的桶时？ 还是这是一个老的程序员的故事，每个人都接受，因为其他人都接受它？
通常，一个简单的散列函数通过将input的“组成部分”（string中的字符）乘以某个常量的幂，然后将它们以某种整数types相加来工作。 例如，一个string的典型（尽pipe不是特别好）散列可能是：
(first char) + k * (second char) + k^2 * (third char) + ... 然后，如果一串string都有相同的第一个字符，那么结果将全部是相同的模k，至less直到整数types溢出。
[举个例子，Java的stringhashCode与此类似，它的字符反序排列，k = 31。 因此，你可以得到以相同的方式结束的string之间的模31关系，并且在接近结尾的string之间以2 ^ 这并不会严重破坏散列表行为。]
散列表的工作方式是将散列的模数作为桶的数量。
在散列表中，不要为可能的情况产生冲突，因为冲突会降低散列表的效率。
现在，假设某人将一大堆值放入一个散列表中，这些散列表之间有一些关系，就像所有的第一个字符一样。 这是一个相当可预测的使用模式，我想说，所以我们不希望它产生太多的冲突。
事实certificate，“由于math的性质”，如果哈希中使用的常量和桶的数量是互质的 ，则在一些常见情况下，碰撞被最小化。 如果它们不是相互矛盾的，那么在input之间有一些相当简单的关系，这些关系之间的冲突不会被最小化。 所有的哈希都等同于公共因素，这意味着它们全部落入具有该公共因子模值的桶中的第1 / n个桶中。 碰撞的次数是n次，其中n是公因子。 由于n至less是2，所以我认为这是一个相当简单的用例，至less产生两倍于正常的碰撞是不可接受的。 如果一些用户打算把我们的configuration分成桶，我们希望它是一个怪胎事故，而不是一些简单的可预测的用法。
现在，散列表实现显然无法控制放入它们的项目。 他们不能阻止他们相关。 所以要做的是确保常量和桶计数是相互矛盾的。 这样你就不依赖于单独的“最后”组件来确定桶相对于一个小公因子的模量。 据我所知，他们并不一定要做到这一点，只是互相矛盾。
但是如果散列函数和散列表是独立编写的，那么散列表就不知道散列函数是如何工作的。 这可能是使用一个常数与小因素。 如果幸运的话，它可能完全不同，并且是非线性的。 如果哈希足够好，那么任何桶计数就好了。 但是，一个偏执的哈希表不能假定一个好的哈希函数，所以应该使用一个素数的桶。 类似的，一个偏执散列函数应该使用一个较大的素数常量，以减less某人使用多个桶的机会，这个桶恰好与常数有一个共同的因子。
在实践中，我认为使用2的幂作为桶的数量是相当正常的。 这很方便，不必search或预先select正确幅度的素数。 所以你依靠哈希函数不使用偶数乘法器，这通常是一个安全的假设。 但是你仍然可以得到偶尔的基于散列函数的散列行为，像上面这样，散列函数可以进一步帮助。
说到“一切都必须成功”的原则，就我所知，一个充分的，但不是一个好的散列表分发的必要条件。 它允许每个人互相操作，而不必假设其他人遵循相同的规则。
[编辑：有另一个更专业的理由使用素数桶，这是如果你处理碰撞与线性探测。 然后你从哈希码计算出一个步幅，如果这个步幅是桶数的一个因素，那么你只能在你回到开始之前做（bucket_count / stride）探测。 你最想避免的情况是stride = 0，当然这必须是特殊的，但是为了避免特殊情况下的bucket_count / stride等于一个小整数，你可以使bucket_count成为prime，而不用关心提供的步幅不是0.]
从哈希表插入/返回时，您要做的第一件事就是计算给定键的hashCode，然后通过hashCode％table_length将hashCode修改为hashTable的大小来查找正确的桶。 这里是你可能已经读过的2个“陈述”
- 如果对table_length使用2的幂，则find（hashCode（key）％2 ^ n）与（hashCode（key）＆（2 ^ n-1））一样简单快捷。 但是，如果你的函数为一个给定的密钥计算hashCode不好，你肯定会受到几个哈希桶中许多密钥的集群的影响。
- 但是，如果你使用素数的table_length，hashCodes计算可以映射到不同的哈希桶，即使你有一个愚蠢的hashCode函数。
这是certificate。
如果假设你的hashCode函数产生下面的hashCode（其中{x，2x，3x，4x，5x，6x …}），那么所有这些将被聚集在m个桶中，其中m = table_length / GreatestCommonFactor （table_length，x）。 （这是微不足道的validation/派生这个）。 现在您可以执行以下操作之一来避免集群
确保你不会生成太多的hashCode，这些hashCode是{x，2x，3x，4x，5x，6x …}中另一个hashCode的倍数。但是如果你的hashTable应该有数百万条目。 或者通过使GreatestCommonFactor（table_length，x）等于1，即通过使table_length与x互质来简单地使m等于table_length。 如果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/
很清楚的解释，也有图片。
编辑：作为一个总结，素数的使用是因为你有最好的机会获得一个独特的价值乘以所select的素数数值，并把它们全部加起来。 例如给定一个string，将每个字母值与素数相乘，然后将这些加起来就会得到它的哈希值。
更好的问题是，为什么数字31？
TL;博士
index[hash(input)%2]将导致所有可能的散列和值的范围的一半发生冲突。 index[hash(input)%prime]导致<2所有可能的散列冲突。 将除数修正为表大小还可以确保数字不能大于表。
使用素数是因为对于使用多项式模P的典型哈希函数，您有很好的机会获得唯一的值。比如说，对长度<= N的string使用这样的哈希函数，并且碰撞。 这意味着2个不同的多项式产生相同的P值模。这些多项式的差异又是一个相同度N（或更小）的多项式。 它只有N个根（这里是math演示本身的本质，因为这个说法对于一个场上的多项式=>素数是正确的）。 所以如果N比P小得多，你很可能不会碰撞。 之后，实验可能会显示37足够大，以避免长度为5-10的string散列表的冲突，并且足够小，可用于计算。
只是为了提供一个替代的观点有这个网站：
http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth
其中争辩说，你应该使用最大数量的桶，而不是四舍五入到一个质数桶。 这似乎是一个合理的可能性。 直觉上，我当然可以看到更多数量的桶会更好，但我无法对此进行math论证。
素数是唯一的数字。 它们是独一无二的，因为素数与任何其他数的乘积具有最好的独特性（不像素数本身那样独一无二），因为素数被用来构成它。 该属性用于散列函数。
给定一个string“Samuel”，可以通过将每个组成数字或字母与一个素数相乘并将它们相加来生成一个唯一的哈希。 这就是使用素数的原因。
然而使用素数是一个古老的技术。 这里的关键是要明白，只要你能生成一个足够独特的密钥，你也可以移动到其他的哈希技术。 去这里http://www.azillionmonkeys.com/qed/hash.html关于这个话题更多;
http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
这取决于散列函数的select。
许多散列函数将数据中的各个元素乘以一些因子，模仿与机器的字大小相对应的因子（通过让计算溢出而使模块免费），从而组合了数据中的各种元素。
您不希望数据元素的乘数与散列表的大小之间有任何共同的因素，因为这样可能发生的情况是，改变数据元素不会将数据散布在整个表格上。 如果你select一个表的大小，这样一个共同的因素是不太可能的。
另一方面，这些因素通常由奇素数组成，所以你也应该安全地使用两个幂的哈希表（例如Eclipse在生成Java hashCode（）方法时使用31）。
假设你的表大小（或模数）是T =（B * C）。 现在，如果你的input的散列是（N * A * B），其中N可以是任何整数，那么你的输出将不会很好地分布。 因为每当n成为C，2C，3C等，你的输出将开始重复。 即你的输出将只分配在C位置。 注意这里的C是（T / HCF（table-size，hash））。
这个问题可以通过使HCF 1消除。素数是非常好的。
另一个有趣的事情是当T是2 ^ N时。 这些将输出完全相同的input哈希的所有较低的N位。 由于每个数字都可以表示为2的幂，所以当我们用T来取模任意数时，我们将减去2个forms数的所有幂次，这是> = N，因此总是发出特定模式的数字，取决于input。 这也是一个不好的select。
同样，由于类似的原因，T为10 ^ N也不好（数字的十进制表示而不是二进制）。
因此，素数往往会给出更好的分布式结果，因此是表大小的不错select。
我想添加一些史蒂夫·杰索普的答案（我不能评论，因为我没有足够的声誉）。 但是我find了一些有用的材料。 他的回答是非常有帮助的，但他犯了一个错误：桶的大小不应该是2的大小。我将引用Thomas Cormen，Charles Leisersen等人在第263页上的“Introduction to Algorithm”
在使用除法的时候，我们通常会避免m的某些值。 例如，m不应该是2的幂，因为如果m = 2 ^ p，那么h（k）就是k的p个最低位。 除非我们知道所有低阶p位模式的可能性相同，否则我们最好devise散列函数以取决于密钥的所有位。 当练习11.3-3要求你展示的时候，当k是一个以2 * p解释的string时，selectm = 2 ^ p-1可能是一个不好的select，因为排列k的字符不会改变它的散列值。
希望它有帮助。
从我的其他答案复制https://stackoverflow.com/a/43126969/917428 。 看到更多的细节和例子。
我相信这只是与计算机在基数2下工作的事实有关。只要考虑基数10同样的工作情况：
- 8％10 = 8
- 18％10 = 8
- 87865378％10 = 8
不pipe数字是多less，只要以8结尾，它的模10就是8。
select一个足够大的非幂次数将确保散列函数真的是所有input位的函数，而不是它们的一个子集。
对于一个散列函数来说，它通常会尽可能地减lesscolys，但是在链接几个字节时不可能保留相同的散列值。
假设你有一个方程： (x + y*z) % key = x ， 0<x<key和0<z<key 。 如果key是一个primenumber n * y = key对于N中的每个n都是对的，对于其他每个数都是false。
一个例子，其中的密钥不是一个主要的例子：x = 1，z = 2和key = 8因为key / z = 4仍然是一个自然数，所以4成为我们方程的解，在这种情况下（n / 2） *对于N中的每个n，y = key是正确的。由于8不是素数，所以方程的解的数量已经增加了一倍。
如果我们的攻击者已经知道8是可能的解决scheme，他可以将文件从生成8更改为4，仍然获得相同的散列。
