为什么哈希函数应使用质数模数？

#1 楼

通常，一个简单的哈希函数通过获取输入的“组成部分”（在字符串的情况下为字符），然后将它们乘以某个常数的幂，然后将它们加在一起以某种整数类型来工作。因此，例如，一个字符串的典型（虽然不是特别好）的哈希可能是：

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

然后，如果将一堆都具有相同第一个字符的字符串送入， ，那么结果将都是相同的模k，至少直到整数类型溢出为止。

[例如，Java的字符串hashCode与此极为相似-它以相反的顺序处理字符k = 31。因此，在以相同方式结尾的字符串之间会得到31的模数关系，而在末端附近的相同字符串之间会以2 ^ 32的模数关系。这不会严重破坏哈希表的行为。]

哈希表的工作原理是将哈希的模数乘以存储桶数。由于冲突会降低哈希表的效率，因此在可能的情况下会产生冲突。字符。我想说，这是一个相当可预测的使用模式，所以我们不希望它产生太多的冲突。

事实证明，“由于数学的性质”，如果哈希中使用的常量和存储区的数量是互质的，那么在某些常见情况下，冲突会最小化。如果它们不是互质的，那么在输入之间存在一些相当简单的关系，不会使冲突最小化。所有散列都以公因数取模相等，这意味着它们将全部落入具有该值以公因数取模的存储桶的1 / n。您得到的碰撞次数是n倍，其中n是公因子。由于n至少为2，我想说一个相当简单的用例产生的碰撞至少是正常情况的两倍是不可接受的。如果某些用户打算将我们的分布分解为多个存储桶，我们希望这是一次异常事故，而不是一些简单的可预测用法。

现在，哈希表实现显然无法控制放入其中的项目。他们无法阻止他们之间的联系。因此，要做的是确保常数和存储区数互质。这样一来，您就不会仅依靠“最后一个”组件来确定铲斗相对于一些小的公因子的模数。据我所知，它们并不一定要达到最佳效果，只需coprime。

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

实际上，我认为使用2的幂作为存储桶数量是很正常的。这很方便，省去了搜索或预先选择合适大小的质数的麻烦。因此，您依赖哈希函数不使用偶数乘法器，这通常是一个安全的假设。但是您仍然会偶尔遇到基于上述哈希函数的不良哈希行为，并且素数存储桶计数可以进一步提供帮助。我知道在哈希表上进行良好分布的充分但非必要条件。它允许每个人进行互操作，而无需假设其他人遵循相同的规则。线性探测。然后，您可以从哈希码中计算出一个跨度，如果该跨度成为存储桶计数的一个因素，那么您只能在返回起点之前进行（bucket_count /跨度）探测。当然，您最想避免的情况是stride = 0，这必须是特殊情况，但是要避免还使用特殊情况的bucket_count / stride等于一个小整数，您可以使bucket_count为素数，而不必关心跨度（不为0）。]

#2 楼

从哈希表插入/检索哈希表时，您要做的第一件事是计算给定键的hashCode，然后通过执行hashCode％table_length将hashCode修剪为hashTable的大小来找到正确的存储桶。这是您最有可能在某处阅读的2个“语句”


如果对table_length使用2的幂，则查找（hashCode（key）％2 ^ n）非常简单并且快于（hashCode（key）＆（2 ^ n -1））。但是，如果您计算给定键的hashCode的功能不好，则肯定会在几个哈希存储桶中聚集许多键。即使您有一个稍微愚蠢的hashCode函数，也可以使用不同的哈希桶。

这就是证明。 2x，3x，4x，5x，6x ...}，那么所有这些都将被聚集在m个存储桶中，其中m = table_length / GreatestCommonFactor（table_length，x）。 （验证/得出这一点很简单）。现在，您可以执行以下操作之一以避免聚类

请确保您不会生成过多的哈希码，这些哈希码是另一个哈希码的倍数，例如{x，2x，3x，4x，5x，6x ...}。但是，如果您的hashTable应该具有数百万个条目，这可能有点困难。
或者通过将GreatestCommonFactor（table_length，x）等于1，即通过使table_length与x互质。如果x可以是任意数，请确保table_length是质数。

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

#3 楼

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

解释也很清楚，还有图片。

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

#4 楼

tl; dr

index[hash(input)%2]将导致所有可能的哈希值和值范围的一半发生冲突。 index[hash(input)%prime]导致所有可能的哈希值<2的冲突。将除数固定为表格大小还可以确保该数字不能大于表格。

#5 楼

使用质数是因为您很有可能获得典型的哈希函数的唯一值，该哈希函数使用以P为模的多项式。 。这意味着2个不同的多项式产生相同的模P值。这些多项式的差再次是相同次数N（或更小）的多项式。它的根数不超过N（这是数学的本性，这是因为它仅对域=>质数上的多项式成立，这是正确的）。因此，如果N远小于P，则很可能不会发生碰撞。之后，实验可能会显示37足够大，可以避免长度为5-10的字符串的哈希表发生冲突，并且足够小，可以用于计算。

#6 楼

为了提供其他观点，请访问以下站点：

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

哪个主张您应使用尽可能多的存储桶，而不是四舍五入为最基本的存储桶。这似乎是合理的可能性。凭直觉，我当然可以看到更多的存储桶会更好，但是我无法对此进行数学论证。

#7 楼

这取决于哈希函数的选择。

许多哈希函数通过将数据中的各个元素与一些乘​​积系数相乘来组合数据中的各个元素（与机器字长相对应的两个幂）只需让计算溢出就可以释放它。）

您不希望数据元素的乘数与哈希表的大小之间存在任何公因数，因为那样的话，改变数据元素可能会发生不会将数据分散到整个表中。如果您为表的大小选择素数，那么这样的公因数就不太可能。哈希表中的两个（例如，Eclipse生成Java hashCode（）方法时使用31）。

#8 楼

质数是唯一的数字。它们是
独特的，素数
与任何其他数字的乘积具有最大的
独一无二的机会（不像课程素数本身那样独特）由于
使用素数组成
的事实。在
哈希函数中使用此属性。

给定字符串“ Samuel”，您可以
通过乘以
每个组成位数或<带有素数的br字母，然后将它们加起来
。这就是为什么要使用质数的原因。
但是，使用质数是一种古老的
技术。此处要理解的键
，只要您可以生成
足够唯一的键，就可以将
也移至其他哈希技术。在此处转到
，以获取有关此主题的更多信息
http://www.azillionmonkeys.com/qed/hash.html


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

评论

---

哈哈哈....实际上，两个素数的乘积不是比素数和任何其他数的乘积具有更好的“唯一性”机会吗？

–HasaniH
09年7月17日在20:14

---

@Beska在这里，“唯一性”是递归定义的，所以我认为“非唯一性”应该以相同的方式定义：)

– TT_
16年11月16日在17:56

---

#9 楼

假设您的表大小（或模数）为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 as 10 ^ N也很糟糕。因此，质数倾向于提供更好的分布式结果，因此是表大小的不错选择。

#10 楼

从其他答案中复制https://stackoverflow.com/a/43126969/917428。有关更多详细信息和示例，请参见它。 ：


8％10 = 8
18％10 = 8

没关系该数字是：只要以8结尾，其模10就是8。

选取足够大的非2的幂可以确保哈希函数确实是一个函数所有输入位，而不是它们的子集。

#11 楼

我想为史蒂夫·杰索普（Steve Jessop）的答案添加一些内容（因为我没有足够的声誉，所以我无法对此发表评论）。但是我发现了一些有用的材料。他的回答很有帮助，但他犯了一个错误：存储桶大小不应该是2的幂。我只引用第263页的Thomas Cormen，Charles Leisersen等人的“算法简介”这本书： >

使用除法时，通常避免使用某些m值。例如，m不应该是2的幂，因为如果m = 2 ^ p，则h（k）只是k的p个最低位。除非我们知道所有低阶p位模式均等可能，否则最好将散列函数设计为依赖于密钥的所有位。正如练习11.3-3所要求的那样，当k为以基数2 ^ p解释的字符串时选择m = 2 ^ p-1可能不是一个好选择，因为对k的字符进行置换不会更改其哈希值。 br />

希望有帮助。

#12 楼

关于素数幂模的“数学性质”是它们是有限域的一个基本组成部分。其他两个构造块是加法和乘法运算。质数模的特殊性质是，它们与“常规”加法和乘法运算一起形成了一个有限域，刚好考虑了模数。这意味着每个乘法都以质数为模，映射到不同的整数，每个加法也是如此。除0以外的所有乘数最终将只访问一次所有元素
如果所有散列均小于模数，则根本不会发生碰撞
随机质数的混合效果好于两个模的幂，并压缩所有信息这些位不只是一个子集

但是它们有很大的缺点，它们需要整数除法，即使在现代CPU上也需要很多（〜15-40）个周期。通过大约一半的计算，可以确保哈希混合得很好。两次乘法和异或移位运算将比主要模数混合得更好。然后，我们可以使用任何最快的哈希表大小和哈希减少方法，总共可以进行7次操作来获得2种表大小的能力，对于任意大小可以进行大约9次操作。它们中的大多数不使用素数模数。
哈希表索引的分布主要取决于使用的哈希函数。质数模量不能解决错误的哈希函数，而好的散列函数不能受益于质数模量。但是在某些情况下它们可能是有利的。例如，它可以修补一个坏的哈希函数。

#13 楼

对于散列函数，不仅通常要使细菌减少到最低限度，而且要在改变几个字节的同时避免保持相同的散列，这很重要。

假设您有一个等式：和(x + y*z) % key = x。
如果key是素数，则n * y = key对于N中的每个n为true，对于其他每个数字为false。
x = 1，z = 2和key = 8
因为key / z = 4仍然是自然数，所以4成为方程的解，在这种情况下（n / 2）* y = N中的每n个键都为true。方程式的解数量实际上增加了一倍，因为8不是素数。

如果我们的攻击者已经知道方程的8种可能解，他可以将文件从产生8更改为4并仍然获得相同的哈希值。

#14 楼

我已阅读了流行的wordpress网站，这些网站在顶部列出了一些上述流行的答案。根据我的理解，我想分享一个简单的观察。

您可以在此处找到本文中的所有详细信息，但假定以下情况成立：


使用质数可以为我们提供唯一值的“最佳机会”。


一般的散列图实现要求2项唯一。



键的唯一哈希码

存储实际值的唯一索引


如何获得唯一索引？通过使内部容器的初始尺寸也成为质数。因此，基本上涉及质数，因为质数具有产生唯一数字的独特特征，最终我们将其用于ID对象并在内部容器中查找索引。

示例：

键=“键”

值=“值”
uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1` + "y"

映射到唯一ID
现在我们想要一个唯一的位置我们的价值-因此，假设uniqueId % internalContainerSize == uniqueLocationForValue也是素数，我们

internalContainerSize。

我知道这是简化的方法，但我希望能通过一般思路。
/>

#15 楼

这个问题与一个更合适的问题合并，为什么哈希表应该使用素数数组，而不是2的幂。至关重要的哈希表（如glibc）使用素数数组，但还没有。有昂贵的h % n => h & bitmask，其中可以通过大小为n的clz（“计数前导零”）来计算位掩码。模函数需要进行整数除法，这比逻辑and慢约50倍。有一些技巧可以避免取模，例如使用Lemire的https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/，但是通常快速哈希表使用强大的功能

为什么这样？

为什么安全？这种情况下的安全性是通过对冲突解决策略的攻击来定义的，大多数哈希表仅线性搜索碰撞的链接列表中。或者使用更快的开放式地址表直接在表中进行线性搜索。因此，拥有2张桌子的力量和桌子的一些内部知识，例如由某些JSON接口提供的键的大小或列表的顺序，您将获得使用的正确位数。位掩码上的1的数量。通常低于10位。对于5到10位，即使使用最强大和最慢的哈希函数，对于暴力冲突也是微不足道的。您再也无法获得32位或64位哈希函数的完全安全性。关键是要使用快速的小型哈希函数，而不要使用诸如杂音甚至siphash之类的怪物。

因此，如果您为哈希表提供外部接口，例如DNS解析器，编程语言等。 ..您想关心那些喜欢使用DOS这样的服务的人。对于这类人来说，通常更容易用更简单的方法来关闭您的公共服务，但是确实发生了。所以人们确实在乎。

因此，防止此类冲突攻击的最佳选择是

1）使用质数表，因为这样



所有32位或64位都与查找相关桶，而不仅仅是几个。
哈希表调整大小功能比仅使用double更为自然。最好的增长函数是斐波那契数列，素数比加倍数更接近。

2）对实际攻击使用更好的措施，同时具有2种大小的快速幂。 >
计算碰撞次数，并在检测到的攻击后中止或睡眠，这是发生碰撞的次数，概率小于1％。像100个带有32位哈希表的表。这就是例如djb的dns解析程序会执行此操作。
在检测到冲突攻击时，使用O（log n）搜索而不是O（n）将冲突的链接列表转换为树的冲突列表。这就是例如Java确实如此。仅低位是没有安全性的。这仅适用于素数大小的表，但这将结合使用两种最慢的方法，即慢速散列和慢速素数模。

散列表的散列函数主要需要很小（速度快）。安全只能来自防止冲突中的线性搜索。而且不要使用琐碎的哈希函数，例如对某些值不敏感的哈希函数（例如在使用乘法时为\ 0）。

使用随机种子也是一个不错的选择，人们首先开始使用该函数，但要足够表的信息甚至是随机种子也无济于事，动态语言通常不容易通过其他方法来获取种子，因为它存储在已知的内存位置。

#16 楼

我想说这个链接的第一个答案是我找到的关于这个问题的最清晰答案。
考虑一下键集K = {0,1，...，100}和一个哈希表（其中存储桶数）是m =12。由于3是12的因数，所以3的倍数的键将被哈希到3的倍数的存储桶中。

键{0,12,24,36 ,. ..}将被散列到存储区0。
键{3,15,27,39，...}将被散列到存储区3。
键{6,18,30,42 ,. ..}将被散列到存储桶6。
键{9,21,33,45，...}将被散列到存储桶9。

如果K是均匀分布的（即，则K中的每个键都同样可能出现），那么m的选择并不是那么关键。但是，如果K不均匀分布会怎样？想象一下，最有可能发生的键是3的倍数。在这种情况下，所有不是3的倍数的存储桶都将很可能为空（这在哈希表性能方面确实很差）。 br />这种情况似乎更普遍。例如，想象一下，您正在根据对象在内存中的存储位置来跟踪它们。如果您计算机的字长为4个字节，那么您将使用4的倍数作为哈希键。不用说，将m选为4的倍数将是一个糟糕的选择：您将有3m / 4个存储桶完全为空，并且您所有的键都与其余的m / 4个存储桶相撞。
一般来说：

K中与存储桶数共享一个公因数的每个密钥都将散列到是该因子的倍数。

因此，为了最大程度地减少冲突，减少m与K元素之间的公因子数量很重要。如何实现？通过选择m为一个几乎没有因素的数字：质数。