为了提供另一种观点，这里有一个网站:

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

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

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

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

Primes are used because you have good chances of obtaining a unique value for a typical hash-function which uses polynomials modulo P. Say, you use such hash-function for strings of length <= N, and you have a collision. That means that 2 different polynomials produce the same value modulo P. The difference of those polynomials is again a polynomial of the same degree N (or less). It has no more than N roots (this is here the nature of math shows itself, since this claim is only true for a polynomial over a field => prime number). So if N is much less than P, you are likely not to have a collision. After that, experiment can probably show that 37 is big enough to avoid collisions for a hash-table of strings which have length 5-10, and is small enough to use for calculations.

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

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

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

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

假设表的大小(或模数)是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也是不好的，因为类似的原因(模式是十进制数而不是二进制数)。

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

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

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