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

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

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

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

质模的优势在于:

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

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

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

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

抄袭我的其他答案https://stackoverflow.com/a/43126969/917428。有关更多细节和示例，请参阅它。

我相信这和电脑在2进制下工作有关。想想以10为基数的情况:

8%10 = 8 18%10 = 8 87865378%10 = 8

不管这个数是多少只要它以8结尾，它对10的模就是8。

选择一个足够大的、非2的幂的数字将确保哈希函数实际上是所有输入位的函数，而不是它们的子集。

插入/从哈希表中检索时要做的第一件事是计算给定键的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?

博士tl;

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