哈希函数为什么要使用素数模数？

Question

很久以前，我以1.25美元的价格从讨价还价的桌子上买了一本数据结构书。其中，哈希函数的解释说，它应该最终由于“数学的性质”而被素数修改。

你对1.25美元的书有什么期望？

无论如何，我已经有数年的时间来思考数学的本质，但仍然无法弄清楚。

即使存在桶的素数，分配的数字是否真的更多？或者这是一个老的程序员的故事，每个人都接受，因为每个人都接受其他接受它？

Answer 1

一般简单的散列函数的工作原理是服用“组成部件”输入的（在一个字符串的情况下的字符），并且通过一些恒定的功率乘以它们，并且在一些整数类型一起添加。因此，例如一个字符串的典型（虽然不是特别好）哈希可能是：

(first char) + k * (second char) + k^2 * (third char) + ... 

然后，如果一串字符串的所有具有相同的第一个字符被送入，然后将结果都是相同的模k，至少直到整型溢出。

[作为一个例子，Java的字符串的hashCode是极其相似此 - 它的字符反序，其中k = 31。因此，你可以在以相同方式结束的字符串之间取模31之间的关系，并且在除了结尾以外的字符串之间以2^32之间的模数显示关系。这通过利用哈希模量超过桶的数量不认真搞砸了哈希表的行为。]

散列表的作品。

在散列表中，不要为可能的情况产生冲突很重要，因为冲突会降低散列表的效率。

现在，假如有人放了一大堆值成有项目之间的一些关系，像所有具有相同的第一个字符一个哈希表。这是一个相当可预测的使用模式，我想说，所以我们不希望它产生太多的冲突。

事实证明，“由于数学的性质”，如果哈希中使用的常量和桶的数量是coprime，那么在一些常见情况下碰撞被最小化。如果它们不是coprime，那么碰撞未被最小化的输入之间存在一些相当简单的关系。所有的哈希都等同于公共因子的模数，这意味着它们全部落入具有该公因子模值的桶的第1/n个桶中。你碰到n次碰撞的次数是n次，其中n是公因数。由于n至少是2，所以我认为用相当简单的用例来产生至少两倍于正常的碰撞是不可接受的。如果一些用户打算将我们的配置分成桶，我们希望它是一个怪胎事故，而不是一些简单的可预测的用法。

现在，散列表实现显然无法控制放入它们的项目。他们不能阻止他们相关。所以要做的是确保常量和桶计数是相互矛盾的。这样，您不依赖于“最后”组件来确定相对于某个小公因子的铲斗模数。据我所知，他们不一定要做到这一点，只是互相矛盾。

但是，如果散列函数和散列表独立编写，那么散列表不知道散列函数是如何工作的。它可能会使用一个具有小因素的常量。如果幸运的话，它可能会完全不同并且是非线性的。如果哈希足够好，那么任何存储桶计数都很好。但是一个偏执的散列表不能假定一个好的散列函数，所以应该使用一个素数的散列表。同样，一个偏执散列函数应该使用一个大的素数常量，以减少某人使用多个桶的机会，这个桶恰好与常数有一个共同的因子。

实际上，我认为使用2的幂作为桶的数量是相当正常的。这很方便，不必搜索或预先选择正确幅度的素数。所以你依靠哈希函数不要使用偶数乘法器，这通常是一个安全的假设。但是，您仍然可以根据像上面那样的哈希函数偶尔获得不良的哈希行为，并且主要存储区计数可以进一步提供帮助。

提到“一切都必须是最好的”原则就我所知足够但不是通过散列表进行良好分配的必要条件。它允许每个人进行互操作，而不需要假定其他人遵循相同的规则。

[编辑：有另一个更专业的理由使用素数桶，这是如果你处理碰撞与线性探测。然后你从哈希码计算出一个步幅，如果这个步幅是桶数的一个因素，那么你只能在你回到开始位置之前进行（bucket_count/stride）探测。你最想避免的情况是stride = 0，当然，它必须是特殊的，但为了避免特殊情况下的bucket_count/stride等于一个小整数，你可以使bucket_count成为prime，而不用关心提供的步长不为0.]

Answer 2

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

相当清楚的解释，用图片了。

编辑：作为一个总结，使用素数是因为当将数值乘以所选素数并将它们全部加起来时，您有最佳机会获得唯一值。例如给定一个字符串，将每个字母值与素数相乘，然后将这些加起来就会得到它的哈希值。

更好的问题是，为什么数字31？

Answer 3

素数是唯一的数字。他们是 独特之处在于，一个主要 与其他任何数量的产品拥有最佳的 机会是独一无二的（不是唯一 作为课程的主要本身）由于 一个主要用于 事实撰写它。该属性用于散列函数 。

给出一个字符串“塞缪尔”，你可以 生成每个乘法 的组成部分数字或字母 唯一哈希与一个素数和增加 起来。这就是使用素数的原因。

但是使用素数是旧的 技术。了解 的关键在于，只要您可以生成足够唯一的密钥，您就可以将 移动到其他哈希技术。去 这里了解更多关于这个主题有关 http://www.azillionmonkeys.com/qed/hash.html

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

Answer 4

只是提供一个备用的观点有这个网站：

http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth

哪些争辩说，你应该使用人数最多的桶可能，而不是四舍五入到大量的桶。这似乎是一个合理的可能性。直觉上，我当然可以看到更多数量的桶会更好，但我无法对此进行数学论证。

Answer 5

这取决于散列函数的选择。

许多散列函数乘以它们与一些因素模的两个对应于机器的字的大小（即弹性模量是通过仅让计算溢出免费）的功率相结合的数据的各种元素。

你不想为一个数据元素和哈希表大小的乘数之间的共同因素，因为那可能发生变化的数据元素不超过整个表传播数据。如果您选择表中的素数，那么这样一个公共因素是不太可能的。另一方面，这些因素通常由奇素数组成，因此您应该也可以安全地使用散列表的两个幂（例如，Eclipse在生成Java hashCode（）方法时使用31）。

Answer 6

对于散列函数，它不仅非常重要，以尽量减少colisions，但使chan几个字节时不可能保持相同的散列。

假设你有一个方程： (x + y*z) % key = x与0<x<key和0<z<key。 如果密钥是素数n * y =密钥对于N中的每个n都是对的，对于其他每个数都是false。因为key/z = 4仍然是一个自然数，所以4成为我们方程的解，在这个例子中，对于N中的每个n，情况（n/2）* y =关键是成立的。由于8不是素数，所以方程的解的数量已经成倍增加。

如果我们的攻击者已经知道8是可能的解决方案，他可以将文件从生成8更改为4，仍然获得相同的散列。

Answer 7

从哈希表插入/返回时，您要做的第一件事就是计算给定键的hashCode，然后通过执行hashCode％table_length将hashCode修剪为hashTable的大小来查找正确的桶。下面是你，如果你对table_length使用2的幂，找到最有可能已经在某处读到

1. 2“的语句”（的hashCode（键）％2^n）是一样简单和快捷（的hashCode（关键）&（2^n-1））。但是如果你的函数为一个给定的密钥计算hashCode并不好，你肯定会遭受来自几个哈希桶中许多密钥的聚集。
2. 但是，如果你使用素数的table_length，hashCodes计算可以映射到不同的哈希桶，即使你有一个愚蠢的hashCode函数。

这里是证明。

如果假设您的hashCode函数产生了其他{x，2x，3x，4x，5x，6x ...}中的以下哈希代码，那么所有这些将仅聚集在m个桶中，其中m = table_length/GreatestCommonFactor（table_length，x）。 （这是微不足道的验证/派生这个）。现在，您可以执行以下操作之一以避免群集

请确保您不会生成太多的hashCode，它们是{x，2x，3x，4x，5x，6x ...}中另一个hashCode的倍数但如果你的hashTable应该有数以百万计的条目，这可能会有点困难。 或者通过使GreatestCommonFactor（table_length，x）等于1，即通过使table_length与x互质来简单地使m等于table_length。如果x可以是任何数字，那么请确保table_length是一个素数。

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

Answer 8

TL;博士

index[hash(input)%2]会导致所有可能的哈希值的一半和值范围的冲突。 index[hash(input)%prime]导致所有可能的哈希碰撞。将除数修正为表格大小还可确保该数字不能大于表格。

Answer 9

使用素数是因为您有很好的机会获得使用多项式模P的典型散列函数的唯一值。假设您对长度为< = N的字符串使用这种散列函数，并且您拥有碰撞。这意味着2个不同的多项式产生相同的P值模。这些多项式的差异又是一个相同度N（或更小）的多项式。它不超过N根（这是数学演示本身的本质，因为这种说法只适用于一个场上的多项式=>素数）。所以如果N比P小得多，你很可能不会碰撞。之后，实验可能会显示37足够大以避免碰撞长度为5-10的字符串散列表，并且足够小以用于计算。

Answer 10

我想为Steve Jessop的回答添加一些内容（由于我没有足够的声望，我无法评论它）。但是我找到了一些有用的材料。他的回答是非常有帮助的，但他犯了一个错误：桶大小不应该是2的幂。我将引用Thomas Cormen，Charles Leisersen等人的书籍“Introduction to Algorithm”第263页：

当使用除法时，我们通常会避免m的某些值。例如，m不应该是2的幂，因为如果m = 2^p，那么h（k）就是k的p个最低位。除非我们知道所有低阶p位模式具有相同的可能性，否则我们最好设计散列函数以取决于密钥的所有位。当练习11.3-3要求你展示时，当k是以2×p解释的字符串时，选择m = 2^p-1可能是一个糟糕的选择，因为置换k的字符不会改变它的散列值。

希望它有帮助。

Answer 11

假设你的表大小（或模数）是T =（B * C）。现在如果你的输入的散列是（N * A * B），其中N可以是任何整数，那么你的输出将不会很好地分布。因为每当n变成C，2C，3C等时，你的输出将开始重复。即您的输出将仅分布在C位置。请注意，这里的C是（T/HCF（表大小，散列））。

这个问题可以通过使HCF 1消除。素数是非常好的。

另一个有趣的事情是当T是2^N时。这些将输出与输入散列的所有较低N位完全相同。由于每个数字都可以表示为2的幂，所以当我们用T对任意数字进行模数化时，我们将减去2个数字形式的所有幂数，这是≥= N，因此总是根据输入给出特定模式的数字。这也是一个不好的选择。

类似地，由于类似的原因，T为10^N也不好，因为类似的原因（用十进制表示而不是二进制数字）。

所以，素数往往会给出更好的分布式结果，因此是表大小的不错选择。

Answer 12

复制从我的其他答案https://stackoverflow.com/a/43126969/917428。查看更多细节和示例。

我认为它只是一个事实，即计算机与基地2试想在同样的事情是如何工作的基地10个工作要做：

• 8％10 = 8
• 18％10 = 8
• 87865378％10 = 8

不要紧数目是什么：只要它具有8个端部，其模10将8.

选择一个足够大的非幂次数字将确保散列函数真的是所有输入位的函数，而不是它们的子集。