问为什么哈希函数应该使用素数模数？

EN

通常，一个简单的散列函数的工作原理是将输入的“组成部分”(字符串中的字符)乘以某个常量的幂，然后以某种整数类型将它们相加。因此，例如，一个典型的(虽然不是特别好的)字符串散列可能是：

(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。

在从哈希表中插入/检索时，您要做的第一件事是计算给定键的hashCode，然后通过执行hashCode % table_length将hashCode修剪为hashTable的大小，从而找到正确的存储桶。下面是你很可能在某处读过的两个“陈述”

1. 如果对table_length使用2的幂，查找(hashCode(key) % 2^n )就像(hashCode(key) & (2^n -1))一样简单快速。但是如果你计算给定键的hashCode的函数不好，你肯定会在几个散列桶中聚集许多键。
2. 但是如果你对table_length使用质数，hashCodes计算的可能会映射到不同的散列桶中，即使你有一个稍微愚蠢的hashCode函数。

这就是证据。

假设您的hashCode函数在{x，2x，3x，4x，5x，6x...}中产生以下hashCodes，那么所有这些都将聚集在m个bucket中，其中m= table_length/GreatestCommonFactor(table_length，x)。(验证/派生这一点很简单)。现在，您可以执行以下操作之一来避免集群

确保你不会像{x，2x，3x，4x，5x，6x...}.But那样生成太多的hashCodes，它们是另一个hashCode的倍数。如果你的hashTable有几百万个条目，这可能会有点困难。或者简单地通过使table_length (GreatestCommonFactor，x)等于1来使m等于table_length，即通过使table_length与x互质。如果x可以是任意数字，则确保table_length是质数。

发件人- http://srinvis.blogspot.com/2006/07/hash-table-lengths-and-prime-numbers.html

http://computinglife.wordpress.com/2008/11/20/why-do-hash-functions-use-prime-numbers/

非常清楚的解释，还有图片。

编辑:作为总结，使用质数是因为当将值乘以所选的质数并将它们相加时，您获得唯一值的机会最大。例如，给定一个字符串，将每个字母值与质数相乘，然后将这些值相加，就会得到它的散列值。

一个更好的问题应该是，为什么数字到底是31？