很久以前，我花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的幂的数字将确保哈希函数实际上是所有输入位的函数，而不是它们的子集。
其他回答
对于一个哈希函数来说，重要的不仅仅是尽量减少冲突，而且是不可能在改变几个字节的同时保持相同的哈希。
假设你有一个方程: (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，并且仍然得到相同的哈希值。
我读过一个流行的wordpress网站，上面有一些流行的答案。根据我的理解，我想分享一个简单的观察。
你可以在这篇文章中找到所有的细节，但假设以下是正确的:
使用质数给我们提供了一个唯一值的“最佳机会”
一个通用的hashmap实现需要有两个东西是唯一的。
键的唯一哈希码 用于存储实际值的唯一索引
我们如何得到唯一索引?通过使内部容器的初始大小也是质数。基本上，质数的存在是因为它具有产生唯一数字的独特特性，我们最终用它来标识对象并在内部容器中查找索引。
例子:
Key = " Key "
Value = " Value " uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1 ' + “y”
映射到唯一id
现在我们想要一个独特的位置来存放我们的价值，所以我们
uniqueId % internalContainerSize == uniqueLocationForValue，假设internalContainerSize也是质数。
我知道这是简化的，但我希望你能理解我的大意。
http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/
解释得很清楚，还有图片。
编辑:作为一个总结，使用质数是因为当数值乘以所选质数并将它们全部相加时，获得唯一值的可能性最大。例如，给定一个字符串，将每个字母的值与质数相乘，然后将它们全部相加，就会得到它的哈希值。
一个更好的问题是，为什么是数字31?
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/
为了提供另一种观点，这里有一个网站:
http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth
它认为你应该使用尽可能多的桶而不是四舍五入到质数桶。这似乎是个合理的可能性。直观地说，我当然可以看到桶的数量越多越好，但我无法对此进行数学论证。
