通常，一个简单的散列函数的工作原理是将输入的“组成部分”(字符串中的字符)乘以某个常量的幂，然后以某种整数类型将它们相加。因此，例如，一个典型的(虽然不是特别好的)字符串散列可能是：
代码语言：javascript运行复制(first char) + k * (second char) + k^2 * (third char) + ...然后，如果输入了一串具有相同第一个字符的字符串，那么结果都将是相同的模k，至少在整数类型溢出之前是这样。
例如，使用k=31，Java的字符串hashCode与此非常相似-它颠倒了字符的顺序。所以你得到了相同结尾的字符串之间模数为31的显著关系，以及除了结尾附近之外相同的字符串之间的模数为2^32的显著关系。这不会严重扰乱哈希表的行为。
哈希表的工作原理是取散列的模除以存储桶的数量。
在哈希表中，重要的是不要在可能的情况下产生冲突，因为冲突会降低哈希表的效率。
现在，假设有人将一大堆值放到一个哈希表中，这些值在项之间有一些关系，比如所有项都具有相同的第一个字符。我想说，这是一个相当可预测的使用模式，所以我们不希望它产生太多的冲突。
事实证明，“由于数学的本质”，如果散列中使用的常量和桶的数量是coprime，那么在一些常见情况下冲突就会最小化。如果它们不是coprime，那么在输入之间存在一些不会最小化冲突的相当简单的关系。所有的散列都是以公因子为模的，这意味着它们都会落入以公因子为模的值的第1/n个存储桶中。你会得到n倍的碰撞，其中n是公因子。由于n至少是2，我想说对于一个相当简单的用例来说，生成至少是正常情况的两倍的冲突是不可接受的。如果一些用户要将我们的发行版分成几个桶，我们希望它是一个奇怪的意外，而不是一些简单的可预测的使用。
现在，哈希表实现显然无法控制放入其中的项。他们不能阻止他们之间的联系。因此，要做的事情是确保常数和桶计数是互质的。这样，您就不会仅仅依靠“最后”组件来确定相对于某个小公因子的桶的模数。据我所知，他们不一定要是最好的，只要是共同的。
但是如果哈希函数和哈希表是独立编写的，那么哈希表就不知道哈希函数是如何工作的。它可能会使用一个带有小因子的常量。如果你幸运的话，它的工作方式可能完全不同，而且是非线性的。如果散列足够好，那么任何存储桶计数都可以。但是一个偏执的哈希表不能假设一个好的哈希函数，所以应该使用质数的桶。类似地，偏执的散列函数应该使用较大的素数常量，以减少某人使用许多碰巧与常量有公因子的桶的机会。
在实践中，我认为使用2的幂作为存储桶的数量是相当正常的。这是方便的，并且省去了不得不到处搜索或预先选择正确大小的质数。因此，您依赖于哈希函数而不使用乘法器，这通常是一个安全的假设。但是，您仍然可以根据上面的哈希函数偶尔得到糟糕的哈希行为，而主存储桶计数可能会进一步帮助您。
据我所知，提出“一切都必须是质数”的原则是在哈希表上良好分布的充分条件，但不是必要条件。它允许每个人进行互操作，而不需要假设其他人遵循相同的规则。
编辑:使用质数存储桶还有另一个更专业的原因，那就是如果您使用线性探测来处理冲突。然后从哈希码计算步幅，如果步幅是存储桶计数的一个因素，那么您只能在返回开始之前执行(bucket_count / stride)探测。您最希望避免的情况是stride = 0，当然，它必须是特殊大小写的，但为了避免特殊大小写的bucket_count / stride等于一个小整数，您可以将bucket_count设为素数，而不关心步长是什么，只要它不是0。
