很久以前，我花1.25美元在便宜货桌上买了一本数据结构的书。在这篇文章中，哈希函数的解释说，由于“数学的本质”，它最终应该被一个质数mod。
你对一本1.25美元的书有什么期待?
不管怎么说，我花了很多年思考数学的本质，但还是没弄明白。
当有质数个桶时，数字的分布真的更均匀吗?
或者这是一个老程序员的故事，每个人都接受，因为其他人都接受?
当前回答
抄袭我的其他答案https://stackoverflow.com/a/43126969/917428。有关更多细节和示例，请参阅它。
我相信这和电脑在2进制下工作有关。想想以10为基数的情况:
8%10 = 8 18%10 = 8 87865378%10 = 8
不管这个数是多少只要它以8结尾，它对10的模就是8。
选择一个足够大的、非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.
希望能有所帮助。
插入/从哈希表中检索时要做的第一件事是计算给定键的hashCode，然后通过执行hashCode % table_length将hashCode修剪为哈希表的大小来找到正确的bucket。这里有两个“陈述”，你很可能在某处读到过
如果对table_length使用2的幂，那么查找(hashCode(key) % 2^n)就像查找(hashCode(key) & (2^n -1))一样简单快捷。但是如果你为一个给定的键计算hashCode的函数不是很好，你肯定会在几个散列桶中聚集许多键。 但是，如果table_length使用质数，即使使用稍微愚蠢的hashCode函数，计算出来的hashCode也可以映射到不同的散列桶中。
这就是证明。
如果假设你的hashCode函数的结果是以下hashCode {x, 2x, 3x, 4x, 5x, 6x…}，那么所有这些都将聚集在m个桶中，其中m = table_length/GreatestCommonFactor(table_length, x)。(验证/推导这个很简单)。现在可以执行以下操作之一来避免集群
确保你不会生成太多的hashCode，这些hashCode是另一个hashCode的倍数，比如{x, 2x, 3x, 4x, 5x, 6x…}。但如果你的hashTable应该有数百万个条目，这可能有点困难。 或者通过使GreatestCommonFactor(table_length, x)等于1使m等于table_length，即使table_length与x为coprime。如果x可以是任何数字，则确保table_length是质数。
来自- http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html
http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
解释得很清楚，还有图片。
编辑:作为一个总结，使用质数是因为当数值乘以所选质数并将它们全部相加时，获得唯一值的可能性最大。例如，给定一个字符串，将每个字母的值与质数相乘，然后将它们全部相加，就会得到它的哈希值。
一个更好的问题是，为什么是数字31?
抄袭我的其他答案https://stackoverflow.com/a/43126969/917428。有关更多细节和示例，请参阅它。
我相信这和电脑在2进制下工作有关。想想以10为基数的情况:
8%10 = 8 18%10 = 8 87865378%10 = 8
不管这个数是多少只要它以8结尾，它对10的模就是8。
选择一个足够大的、非2的幂的数字将确保哈希函数实际上是所有输入位的函数，而不是它们的子集。
博士tl;
Index [hash(input)%2]将导致所有可能哈希值的一半和一段值发生冲突。Index [hash(input)%prime]导致所有可能哈希值中的<2的碰撞。将除数固定为表的大小还可以确保数字不能大于表。
