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

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

博士tl;

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

我想为Steve Jessop的回答补充一些东西(我不能评论，因为我没有足够的声誉)。但我找到了一些有用的材料。他的回答很有帮助，但他犯了一个错误:桶的大小不应该是2的幂。我引用Thomas Cormen, Charles Leisersen等人写的《算法导论》263页

When using the division method, we usually avoid certain values of m. For example, m should not be a power of 2, since if m = 2^p, then h(k) is just the p lowest-order bits of k. Unless we know that all low-order p-bit patterns are equally likely, we are better off designing the hash function to depend on all the bits of the key. As Exercise 11.3-3 asks you to show, choosing m = 2^p-1 when k is a character string interpreted in radix 2^p may be a poor choice, because permuting the characters of k does not change its hash value.

希望能有所帮助。

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

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?

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.