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

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

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

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

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

我想说，这个链接的第一个答案是我找到的关于这个问题的最清晰的答案。

考虑键K ={0,1，…，100}和一个哈希表，其中桶数为m = 12。因为3是12的因数，所以是3倍数的键将被散列到是3倍数的存储桶中:

键{0,12、24、36…}将被散列到bucket 0。 键{3,15日,27日,39岁,…}将被散列到桶3。 键{42 6日,18日,30日,…}将被散列到桶6。 键{9日,21日,33岁,45岁,…}将被散列到桶9。

如果K是均匀分布的(即K中的每个键出现的可能性都是相等的)，那么m的选择就不是那么关键了。但是，如果K不是均匀分布的呢?想象最有可能出现的键是3的倍数。在这种情况下，所有不是3倍数的桶都很可能是空的(这在哈希表性能方面非常糟糕)。

这种情况比看起来更常见。例如，想象一下，您正在根据对象在内存中的存储位置来跟踪它们。如果您的计算机的字大小是4个字节，那么您将哈希键是4的倍数。不用说，选择m是4的倍数将是一个糟糕的选择:你将有3m/4个桶完全空了，所有的键都在剩下的m/4个桶中碰撞。

一般来说:

K中每一个与桶数m有公因数的键都将被哈希为这个因数的倍数。

因此，为了尽量减少碰撞，减少m和k的元素之间的公因数的数量是很重要的，这是如何实现的呢?通过选择m是一个因数很少的数，一个质数。

来自马里奥的回答。

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.

博士tl;

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

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

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

这取决于哈希函数的选择。

许多哈希函数通过将数据中的各种元素与一些因子相乘，再乘以与机器的字大小相对应的2的幂的模(这个模可以通过让计算溢出来释放)来组合数据中的各种元素。

您不希望在数据元素的乘数和哈希表的大小之间有任何公共因子，因为这样可能会发生改变数据元素不会将数据分散到整个表上的情况。如果你为表的大小选择一个质数，这样的公因数是极不可能的。

另一方面，这些因数通常由奇数质数组成，因此在哈希表中使用2的幂也应该是安全的(例如，Eclipse在生成Java hashCode()方法时使用31)。