Primes are unique numbers. They are unique in that, the product of a prime with any other number has the best chance of being unique (not as unique as the prime itself of-course) due to the fact that a prime is used to compose it. This property is used in hashing functions. Given a string “Samuel”, you can generate a unique hash by multiply each of the constituent digits or letters with a prime number and adding them up. This is why primes are used. However using primes is an old technique. The key here to understand that as long as you can generate a sufficiently unique key you can move to other hashing techniques too. Go here for more on this topic about 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。

选择一个足够大的、非2的幂的数字将确保哈希函数实际上是所有输入位的函数，而不是它们的子集。

我想说，这个链接的第一个答案是我找到的关于这个问题的最清晰的答案。

考虑键K ={0,1，…，100}和一个哈希表，其中桶数为m = 12。因为3是12的因数，所以是3倍数的键将被散列到是3倍数的存储桶中:

键{0,12、24、36…}将被散列到bucket 0。 键{3,15日,27日,39岁,…}将被散列到桶3。 键{42 6日,18日,30日,…}将被散列到桶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是一个因数很少的数，一个质数。

来自马里奥的回答。

假设表的大小(或模数)是T = (B*C)。如果你输入的散列是(N*A*B) N可以是任何整数，那么你的输出就不会很好地分布。因为每次n变成C、2C、3C等，你的输出就会开始重复。也就是说，你的输出只会分布在C位。注意这里的C是(T / HCF(表大小，哈希))。

这个问题可以通过制造hcf1来消除。质数是很好的选择。

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

类似地，T作为10^N也是不好的，因为类似的原因(模式是十进制数而不是二进制数)。

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

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

质模的优势在于:

它们在二次哈希中选择次乘数时给予了最大的自由，除了0之外的所有乘数最终都将访问所有元素一次 如果所有哈希值都小于模量，则根本不会发生碰撞 随机质数比两个模的幂更好地混合，并压缩所有比特的信息，而不仅仅是一个子集

然而，它们有一个很大的缺点，它们需要整数除法，这需要很多(~ 15-40)个周期，即使在现代CPU上也是如此。用大约一半的计算就可以确保散列混合得很好。两次乘法和异移运算比一个质数模更容易混合。然后，我们可以使用任何哈希表的大小，哈希约简是最快的，对于2个表大小的幂，总共给出7个操作，对于任意大小的表，大约9个操作。

我最近研究了许多最快的哈希表实现，其中大多数都不使用质数模块。

哈希表索引的分布主要依赖于所使用的哈希函数。质数模量不能修复一个坏的哈希函数，一个好的哈希函数也不能从质数模量中受益。然而，在某些情况下，它们可能是有利的。例如，它可以修复半坏的哈希函数。

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

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

编辑:作为一个总结，使用质数是因为当数值乘以所选质数并将它们全部相加时，获得唯一值的可能性最大。例如，给定一个字符串，将每个字母的值与质数相乘，然后将它们全部相加，就会得到它的哈希值。

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