假设表的大小(或模数)是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的碰撞。将除数固定为表的大小还可以确保数字不能大于表。

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

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

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

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

我想为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.

希望能有所帮助。

通常，一个简单的哈希函数的工作原理是，取输入的“组成部分”(在字符串的情况下是字符)，将它们乘以某个常数的幂，然后以某种整数类型将它们相加。例如，一个字符串的典型哈希值(虽然不是特别好)可能是:

(first char) + k * (second char) + k^2 * (third char) + ...

然后，如果输入了一堆具有相同首字符的字符串，那么结果将都是相同的k模，至少在整数类型溢出之前是这样。

[举个例子，Java的字符串hashCode与此惊人地相似——它将字符的顺序颠倒，k=31。所以你会得到以31为模的惊人的关系在以相同方式结束的字符串之间，以及以2^32为模的惊人的关系在除了接近结尾的字符串之间都是相同的。这并没有严重扰乱哈希表行为。]

哈希表的工作原理是将哈希的模数除以桶的数量。

在哈希表中，不为可能的情况产生冲突是很重要的，因为冲突会降低哈希表的效率。

现在，假设有人将一大堆值放入一个哈希表中，这些值在项目之间有某种关系，比如所有的第一个字符都相同。我想说，这是一种相当可预测的使用模式，所以我们不希望它产生太多冲突。

It turns out that "because of the nature of maths", if the constant used in the hash, and the number of buckets, are coprime, then collisions are minimised in some common cases. If they are not coprime, then there are some fairly simple relationships between inputs for which collisions are not minimised. All the hashes come out equal modulo the common factor, which means they'll all fall into the 1/n th of the buckets which have that value modulo the common factor. You get n times as many collisions, where n is the common factor. Since n is at least 2, I'd say it's unacceptable for a fairly simple use case to generate at least twice as many collisions as normal. If some user is going to break our distribution into buckets, we want it to be a freak accident, not some simple predictable usage.

现在，哈希表实现显然无法控制放入其中的项。他们不能阻止他们之间的联系。所以要做的就是确保常量和桶数都是互质。这样你就不需要单独依靠“最后一个”分量来确定桶的模数相对于某个小的公共因子。据我所知，它们不一定是质数，只要是质素就可以了。

But if the hash function and the hashtable are written independently, then the hashtable doesn't know how the hash function works. It might be using a constant with small factors. If you're lucky it might work completely differently and be nonlinear. If the hash is good enough, then any bucket count is just fine. But a paranoid hashtable can't assume a good hash function, so should use a prime number of buckets. Similarly a paranoid hash function should use a largeish prime constant, to reduce the chance that someone uses a number of buckets which happens to have a common factor with the constant.

在实践中，我认为使用2的幂作为桶的数量是相当正常的。这很方便，并且省去了四处搜索或预先选择正确大小的质数的麻烦。所以你依赖于哈希函数而不是使用偶数乘数，这通常是一个安全的假设。但是，基于上面的哈希函数，您仍然会偶尔遇到糟糕的哈希行为，而素数桶计数可能会有进一步的帮助。

就我所知，提出“所有东西都必须是质数”的原则是在哈希表上进行良好分布的充分条件，而不是必要条件。它允许每个人进行互操作，而不需要假设其他人遵循相同的规则。

[Edit: there's another, more specialized reason to use a prime number of buckets, which is if you handle collisions with linear probing. Then you calculate a stride from the hashcode, and if that stride comes out to be a factor of the bucket count then you can only do (bucket_count / stride) probes before you're back where you started. The case you most want to avoid is stride = 0, of course, which must be special-cased, but to avoid also special-casing bucket_count / stride equal to a small integer, you can just make the bucket_count prime and not care what the stride is provided it isn't 0.]

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/