很久以前，我花1.25美元在便宜货桌上买了一本数据结构的书。在这篇文章中，哈希函数的解释说，由于“数学的本质”，它最终应该被一个质数mod。
你对一本1.25美元的书有什么期待?
不管怎么说，我花了很多年思考数学的本质，但还是没弄明白。
当有质数个桶时，数字的分布真的更均匀吗?
或者这是一个老程序员的故事，每个人都接受，因为其他人都接受?
当前回答
假设表的大小(或模数)是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也是不好的，因为类似的原因(模式是十进制数而不是二进制数)。
因此，质数往往会给出更好的分布结果，因此是表大小的好选择。
其他回答
对于一个哈希函数来说，重要的不仅仅是尽量减少冲突，而且是不可能在改变几个字节的同时保持相同的哈希。
假设你有一个方程: (x + y*z) % key = x且0<x<key且0<z<key。 如果key是一个质数n*y=key对于n中的每一个n为真，对于其他所有数为假。
一个key不是主要示例的例子: X =1, z=2, key=8 因为key/z=4仍然是一个自然数，4成为我们方程的一个解，在这种情况下(n/2)*y = key对于n中的每一个n都成立。这个方程的解的数量实际上翻了一番，因为8不是质数。
如果我们的攻击者已经知道8是方程的可能解，他可以将文件从产生8改为产生4，并且仍然得到相同的哈希值。
博士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也是不好的，因为类似的原因(模式是十进制数而不是二进制数)。
因此，质数往往会给出更好的分布结果，因此是表大小的好选择。
抄袭我的其他答案https://stackoverflow.com/a/43126969/917428。有关更多细节和示例，请参阅它。
我相信这和电脑在2进制下工作有关。想想以10为基数的情况:
8%10 = 8 18%10 = 8 87865378%10 = 8
不管这个数是多少只要它以8结尾，它对10的模就是8。
选择一个足够大的、非2的幂的数字将确保哈希函数实际上是所有输入位的函数，而不是它们的子集。
我读过一个流行的wordpress网站，上面有一些流行的答案。根据我的理解，我想分享一个简单的观察。
你可以在这篇文章中找到所有的细节，但假设以下是正确的:
使用质数给我们提供了一个唯一值的“最佳机会”
一个通用的hashmap实现需要有两个东西是唯一的。
键的唯一哈希码 用于存储实际值的唯一索引
我们如何得到唯一索引?通过使内部容器的初始大小也是质数。基本上，质数的存在是因为它具有产生唯一数字的独特特性，我们最终用它来标识对象并在内部容器中查找索引。
例子:
Key = " Key "
Value = " Value " uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1 ' + “y”
映射到唯一id
现在我们想要一个独特的位置来存放我们的价值，所以我们
uniqueId % internalContainerSize == uniqueLocationForValue，假设internalContainerSize也是质数。
我知道这是简化的，但我希望你能理解我的大意。
