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

许多哈希函数通过将数据中的各种元素与一些因子相乘，再乘以与机器的字大小相对应的2的幂的模(这个模可以通过让计算溢出来释放)来组合数据中的各种元素。

您不希望在数据元素的乘数和哈希表的大小之间有任何公共因子，因为这样可能会发生改变数据元素不会将数据分散到整个表上的情况。如果你为表的大小选择一个质数，这样的公因数是极不可能的。

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

对于一个哈希函数来说，重要的不仅仅是尽量减少冲突，而且是不可能在改变几个字节的同时保持相同的哈希。

假设你有一个方程: (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，并且仍然得到相同的哈希值。

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

考虑键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是一个因数很少的数，一个质数。

来自马里奥的回答。

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

质模的优势在于:

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

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

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

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

只是把从答案中得到的一些想法写下来。

Hashing uses modulus so any value can fit into a given range We want to randomize collisions Randomize collision meaning there are no patterns as how collisions would happen, or, changing a small part in input would result a completely different hash value To randomize collision, avoid using the base (10 in decimal, 16 in hex) as modulus, because 11 % 10 -> 1, 21 % 10 -> 1, 31 % 10 -> 1, it shows a clear pattern of hash value distribution: value with same last digits will collide Avoid using powers of base (10^2, 10^3, 10^n) as modulus because it also creates a pattern: value with same last n digits matters will collide Actually, avoid using any thing that has factors other than itself and 1, because it creates a pattern: multiples of a factor will be hashed into selected values For example, 9 has 3 as factor, thus 3, 6, 9, ...999213 will always be hashed into 0, 3, 6 12 has 3 and 2 as factor, thus 2n will always be hashed into 0, 2, 4, 6, 8, 10, and 3n will always be hashed into 0, 3, 6, 9 This will be a problem if input is not evenly distributed, e.g. if many values are of 3n, then we only get 1/3 of all possible hash values and collision is high So by using a prime as a modulus, the only pattern is that multiple of the modulus will always hash into 0, otherwise hash values distributions are evenly spread

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

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

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

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