很久以前，我以 1.25 美元的价格从便宜的 table 上买了一本数据结构书。在其中，对散列函数的解释说，由于“数学的性质”，它最终应该用素数进行模数。
你对一本 1.25 美元的书有什么期望？
无论如何，我已经有多年思考数学的本质，但仍然无法弄清楚。
即使有质数的桶，数字的分布是否真的更多？
或者这是一个每个人都接受的老程序员故事，因为其他人都接受它？
最佳答案
通常一个简单的散列函数的工作原理是获取输入的“组成部分”(字符串中的字符)，将它们乘以某个常数的幂，然后将它们以某种整数类型相加。例如，字符串的典型(虽然不是特别好)哈希可能是:
(first char) + k * (second char) + k^2 * (third char) + ...
然后，如果输入一堆具有相同第一个字符的字符串，那么结果都将是相同的模 k，至少在整数类型溢出之前是这样。
[举个例子，Java 的字符串 hashCode 与这个非常相似——它以相反的顺序处理字符，k=31。因此，您会在以相同方式结束的字符串之间获得模 31 模数的显着关系，并且除了接近结尾之外的其他字符串之间的模数 2^32 模数之间的显着关系。这不会严重扰乱哈希表行为。]
哈希表的工作原理是在桶数上取哈希的模数。
在哈希表中，重要的是不要在可能的情况下产生冲突，因为冲突会降低哈希表的效率。
现在，假设有人将一大堆值放入哈希表中，这些值在项目之间具有某种关系，例如所有项目都具有相同的第一个字符。这是一个相当可预测的使用模式，我想说，所以我们不希望它产生太多的冲突。
事实证明，“由于数学的性质”，如果散列中使用的常量和桶的数量是 coprime ，然后在一些常见情况下最小化冲突。如果不是 coprime ，那么在输入之间存在一些相当简单的关系，它们的碰撞不会最小化。所有散列都以公因数为模得到相等，这意味着它们都将落入具有该值以公因数为模的桶的 1/n 中。碰撞次数是 n 倍，其中 n 是公因数。由于 n 至少为 2，我认为对于一个相当简单的用例来说，产生至少两倍于正常情况的碰撞是 Not Acceptable 。如果某个用户打算将我们的分发分成多个桶，我们希望它是一个奇怪的事故，而不是一些简单的可预测的使用。
现在，哈希表实现显然无法控制放入其中的项目。他们无法阻止他们发生关系。所以要做的是确保常量和桶数是互质的。这样你就不会仅仅依靠“最后一个”组件来确定桶的模数与一些小的公因数有关。据我所知，他们不必是素数来实现这一点，只是互素。
但是如果hash函数和hashtable是独立写的，那么hashtable就不知道hash函数是怎么工作的。它可能使用具有小因子的常数。如果幸运的话，它的工作方式可能完全不同并且是非线性的。如果散列足够好，那么任何桶数都可以。但是偏执的哈希表不能假设一个好的哈希函数，所以应该使用质数的桶。类似地，偏执哈希函数应该使用较大的素数常数，以减少有人使用多个桶的机会，这些桶恰好与常数具有公因子。
在实践中，我认为使用 2 的幂作为桶数是相当正常的。这很方便，而且不必四处搜索或预先选择大小合适的素数。所以你依赖哈希函数甚至不使用乘数，这通常是一个安全的假设。但是，您仍然可以根据上面的散列函数偶尔获得不良的散列行为，并且主要桶计数可以进一步提供帮助。
据我所知，关于“一切都必须是素数”的原则是散列表良好分布的充分但不是必要条件。它允许每个人进行互操作，而无需假设其他人遵循相同的规则。
[编辑:使用质数桶还有另一个更专业的原因，那就是如果您使用线性探测处理碰撞。然后您从哈希码计算步幅，如果该步幅是桶数的一个因素，那么您只能在返回起点之前进行 (bucket_count/stride) 探测。您最想避免的情况是 stride = 0，当然，这必须是特殊情况，但是为了避免特殊情况，bucket_count/stride 等于一个小整数，您可以只使 bucket_count 为素数，而不必关心是什么如果步幅不是 0。]
关于language-agnostic - 为什么散列函数应该使用质数模数？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/1145217/