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

很久以前，我花1.25美元在便宜货桌上买了一本数据结构的书。其中，哈希函数的解释说，由于“数学的性质”，它最终应该被一个质数mod。

你对一本1.25美元的书有什么期待?

不管怎么说，我花了很多年思考数学的本质，但还是没弄明白。

当有质数个桶时，数字的分布真的更均匀吗?

或者这是一个每个人都接受的老程序员的故事，因为每个人其他的都接受它?

124773 次浏览
小开

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

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

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

一个更好的问题是，为什么是数字31?

小开

质数是唯一的数字。他们是 独特之处在于，质数的乘积 任何其他数字都是最好的 唯一的机会(不是唯一的 当然是质数本身)由于 质数是用来 组成。此属性用于 哈希函数。< / p >

给定一个字符串“Samuel”，你可以 通过乘法生成唯一的哈希 每一个组成数字或 带有素数和加法的字母 它们。这就是为什么使用质数的原因

然而，使用质数是一个旧的 技术。这是理解的关键 只要你能生成一个 足够唯一的键可以移动 也适用于其他哈希技术。去 这里有关于这个主题的更多信息 http://www.azillionmonkeys.com/qed/hash.html < / p >

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

小开

为了提供另一种观点，这里有一个网站:

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

它认为你应该使用尽可能多的桶而不是四舍五入到质数桶。这似乎是个合理的可能性。直观地说，我当然可以看到桶的数量越多越好，但我无法对此进行数学论证。

小开

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

许多哈希函数通过将数据中的各种元素与一些因子相乘，再乘以与机器的字大小相对应的2的幂的模(这个模可以通过让计算溢出来释放)来组合数据中的各种元素。

您不希望在数据元素的乘数和哈希表的大小之间有任何公共因子，因为这样可能会发生改变数据元素不会将数据分散到整个表上的情况。如果你为表的大小选择一个质数，这样的公因数是极不可能的。

另一方面，这些因数通常由奇数质数组成，因此在哈希表中使用2的幂也应该是安全的(例如，Eclipse在生成Java hashCode()方法时使用31)。

小开
最佳答案

通常，一个简单的哈希函数的工作原理是，取输入的“组成部分”(在字符串的情况下是字符)，将它们乘以某个常数的幂，然后以某种整数类型将它们相加。例如，一个字符串的典型哈希值(虽然不是特别好)可能是:

(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，我认为对于一个相当简单的用例来说，产生至少两倍于正常情况的碰撞是不可接受的。如果某些用户打算将我们的发行版分成多个桶，我们希望它是一个反常的意外，而不是一些简单的可预测的使用。

现在，哈希表实现显然无法控制放入其中的项。他们不能阻止他们之间的联系。所以要做的就是确保常量和桶数都是互质。这样你就不需要单独依靠“最后一个”分量来确定桶的模数相对于某个小的公共因子。据我所知，它们不一定是质数，只要是质素就可以了。

但如果哈希函数和哈希表是独立编写的，那么哈希表就不知道哈希函数是如何工作的。它可能是用一个因数很小的常数。如果你幸运的话，它可能会完全不同，是非线性的。如果哈希值足够好，那么任何桶数都可以。但是一个偏执的哈希表不能假设一个好的哈希函数，所以应该使用素数桶。类似地，一个偏执的哈希函数应该使用一个较大的素数常数，以减少某人使用一些碰巧与常数有公因数的桶的机会。

在实践中，我认为使用2的幂作为桶的数量是相当正常的。这很方便，并且省去了四处搜索或预先选择正确大小的质数的麻烦。所以你依赖于哈希函数而不是使用偶数乘数，这通常是一个安全的假设。但是，基于上面的哈希函数，您仍然会偶尔遇到糟糕的哈希行为，而素数桶计数可能会有进一步的帮助。

就我所知，提出“所有东西都必须是质数”的原则是在哈希表上进行良好分布的充分条件，而不是必要条件。它允许每个人进行互操作，而不需要假设其他人遵循相同的规则。

[编辑:使用质数桶还有另一个更专业的原因，那就是如果你用线性探测处理冲突。然后从hashcode计算一个stride，如果该stride是bucket count的一个因子，那么只能在回到起点之前进行(bucket_count / stride)探测。当然，你最希望避免的情况是stride = 0，这必须是特殊情况，但为了避免也特殊情况bucket_count / stride等于一个小整数，你可以只使bucket_count为素数，而不关心stride是什么，只要它不是0。

小开

对于一个哈希函数来说，重要的不仅仅是尽量减少冲突，而且是不可能在改变几个字节的同时保持相同的哈希。

假设你有一个方程: (x + y*z) % key = x与0<x<key和0<z<key。 如果key是一个质数n*y=key对于n中的每一个n为真，对于每一个其他数字为假

key不是质数的例子: X =1, z=2, key=8 因为key/z=4仍然是一个自然数，4成为我们方程的一个解，在这种情况下(n/2)*y = key对n中的每一个n都成立。方程的解的数量实际上翻了一番，因为8不是质数

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

小开

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

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

这就是证明。

如果假设你的hashCode函数的结果是以下hashCode {x, 2x, 3x, 4x, 5x, 6x…}，那么所有这些都将聚集在m个桶中，其中m = table_length/GreatestCommonFactor(table_length, x)。(验证/推导这个很简单)。现在可以执行以下操作之一来避免集群

确保你不会生成太多的hashCode，这些hashCode是其他hashCode的倍数，比如{x, 2x, 3x, 4x, 5x, 6x…}。但如果你的hashTable应该有数百万个条目，这可能有点困难。 或者通过使GreatestCommonFactor(table_length, x)等于1使m等于table_length，即使table_length与x为coprime。如果x可以是任何数字，则确保table_length是质数

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

小开

博士tl;

index[hash(input)%2]将导致所有可能哈希值的一半和一段值的碰撞。index[hash(input)%prime]导致所有可能哈希值中的<2的碰撞。将除数固定为表的大小还可以确保数字不能大于表。

小开
使用质数是因为对于使用多项式对p模的典型哈希函数，您有很好的机会获得唯一的值。 比如说，你对长度为<= N的字符串使用这样的哈希函数，就会发生碰撞。这意味着2个不同的多项式对p模产生相同的值，这些多项式的差值又是一个相同N次(或更小)的多项式。它的根不超过N个(这就是数学的本质，因为这个声明只适用于一个多项式在一个域上=>素数)。所以如果N比P小很多，就不太可能发生碰撞。在此之后，实验可能表明37足够大，可以避免长度为5-10的字符串哈希表的碰撞，并且足够小，可以用于计算。< / p >
小开

我想为Steve Jessop的回答补充一些东西(我不能评论，因为我没有足够的声誉)。但我找到了一些有用的材料。他的回答很有帮助，但他犯了一个错误:桶的大小不应该是2的幂。我引用Thomas Cormen, Charles Leisersen等人写的《算法导论》263页

当使用除法时，我们通常避免m的某些值。例如，m不应该是2的幂，因为如果m = 2^p，那么h(k)只是k的p个最低阶位。除非我们知道所有低阶p位模式都是等可能的，否则我们最好将哈希函数设计为依赖于键的所有位。正如练习11.3-3要求你展示的，当k是一个以基数2^p解释的字符串时，选择m = 2^p-1可能是一个糟糕的选择，因为排列k的字符不会改变它的哈希值。

希望能有所帮助。

小开

假设表的大小(或模数)是T = (B*C)。如果你输入的散列是(N*A*B) N可以是任何整数，那么你的输出就不会很好地分布。因为每次n变成C、2C、3C等，你的输出就会开始重复。也就是说，你的输出只会分布在C位。注意这里的C是(T / HCF(表大小，哈希))。

这个问题可以通过制造hcf1来消除。质数是很好的选择。

另一个有趣的现象是当T = 2^N时。这些将给出与所有输入哈希的低N位完全相同的输出。由于每个数都可以表示为2的幂，当我们对任意数取T的模时，我们将减去所有2的幂形式的数，即>= N，因此总能得到特定模式的数，取决于输入。这也是一个糟糕的选择。

类似地，T作为10^N也是不好的，因为类似的原因(模式是十进制数而不是二进制数)。

因此，质数往往会给出更好的分布结果，因此是表大小的好选择。

小开

从我的另一个答案https://stackoverflow.com/a/43126969/917428复制。有关更多细节和示例，请参阅它。

我相信这和电脑在2进制下工作有关。想想以10为基数的情况:

  • 8% 10 = 8
  • 18% 10 = 8
  • 87865378% 10 = 8

不管这个数是多少只要它以8结尾，它对10的模就是8。

选择一个足够大的、非2的幂的数字将确保哈希函数实际上是所有输入位的函数，而不是它们的子集。

小开

我读过一个流行的wordpress网站，上面有一些流行的答案。根据我的理解，我想分享一个简单的观察。

你可以在文章在这里中找到所有的细节，但假设以下是正确的:

  • 使用质数为我们提供独特的价值的“最佳机会”

一个通用的hashmap实现需要有两个东西是唯一的。

  • 独特的的哈希码
  • 独特的索引来存储实际的价值

如何我们得到唯一的索引吗?通过使内部容器的初始大小也是质数。基本上，质数的存在是因为它具有产生唯一数字的独特特性，我们最终用它来标识对象并在内部容器中查找索引。

例子:

Key = " Key "

value = "value" uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1 ' + “y” < /代码> < / p >

映射到惟一的id

现在我们想要一个独特的地理位置作为我们的值-所以我们

uniqueId % internalContainerSize == uniqueLocationForValue，假设internalContainerSize也是质数。

我知道这是简化的，但我希望你能理解我的大意。

小开

“数学的本质”;关于素数功率模的一个特点是，它们是有限域的一个构建块。另外两个构建块是加法运算和乘法运算。素模的特殊性质是它们形成了一个有限域，具有“正则”;加法和乘法运算，就得到了模数。这意味着每一个乘法都映射到一个不同的整数对质数求模，每一个加法也是如此。

质模的优势在于:

  • 它们在二次哈希中选择次乘数时给予了最大的自由，除了0之外的所有乘数最终都将访问所有元素一次
  • 如果所有哈希值都小于模量，则根本不会发生碰撞
  • 随机质数比两个模的幂更好地混合，并压缩所有比特的信息，而不仅仅是一个子集

然而，它们有一个很大的缺点，它们需要整数除法，这需要很多(~ 15-40)个周期，即使在现代CPU上也是如此。用大约一半的计算就可以确保散列混合得很好。两次乘法和异移运算比一个质数模更容易混合。然后，我们可以使用任何哈希表的大小，哈希约简是最快的，对于2个表大小的幂，总共给出7个操作，对于任意大小的表，大约9个操作。

我最近看了很多最快的哈希表实现，其中大多数不使用质数模。

哈希表索引的分布主要依赖于所使用的哈希函数。然而，在某些情况下，它们可能是有利的。例如，它可以修复半坏的哈希函数。

小开
这个问题与更合适的问题合并了，为什么哈希表应该使用素数大小的数组，而不是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的幂，而安全哈希表使用质数。

为什么如此?

在这种情况下，安全性是通过对冲突解决策略的攻击来定义的，大多数哈希表只是在冲突链表中进行线性搜索。或者用更快的开放寻址表直接在表中进行线性搜索。因此，有了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)。

使用随机种子也是一个不错的选择，人们首先使用随机种子，但是有了足够的表信息，即使是随机种子也没有多大帮助，而动态语言通常使通过其他方法获取种子变得很简单，因为它存储在已知的内存位置中。

小开

我会说这个链接的第一个答案是我找到的关于这个问题的最清晰的答案。

考虑一组K ={0,1，…，100}键和一个哈希表，其中桶的数量是M = 12。由于3.是12的一个因子，因此3.的倍数的键将被散列到3.的倍数的bucket中:

  • key {0, 12、24、36…}将被散列到bucket 0。
  • {3, 15日,27日,39岁的…}键将被散列到桶3。
  • {6, 18日,30日,42岁的…}键将被散列到桶6。
  • {9日,21日,33岁,45岁…}键将被散列到桶9。

如果<强> K < / >强是均匀分布的(也就是说，<强> K < / >强中的每个键都有同样可能出现)，那么m的选择就不是那么关键。但是，如果<强> K < / >强不是均匀分布的呢?假设最有可能出现的键是3.的倍数。在这种情况下，所有不是3.倍数的存储桶都很可能是空的(这在哈希表性能方面非常糟糕)。

这种情况比看起来更常见。例如，想象一下，您正在根据对象在内存中的存储位置来跟踪它们。如果您的计算机的字大小是4字节，那么您将哈希键是4的倍数。不用说，选择m是4的倍数将是一个糟糕的选择:你将有3米/ 4桶完全空，所有的键都在剩余的米/ 4桶中碰撞。

一般来说:

K中每一个与桶数m有公因数的键都将被哈希为这个因数的倍数。

因此，为了尽量减少碰撞，减少m和<强> K < / >强的元素之间的公因数的数量是很重要的。如何实现这一目标?通过选择m是一个因数很少的数:a 质数. c。

FROM THE ANSWER BY 马里奥。

小开

只是把从答案中得到的一些想法写下来。

  • 哈希使用模量，因此任何值都可以适合给定的范围
  • 我们想随机化碰撞
  • 随机碰撞意味着没有碰撞发生的模式，或者，改变输入中的一小部分将导致完全不同的哈希值
  • 为了随机碰撞，避免使用基数(十进制中的10，十六进制中的16)作为模量，因为11 % 10 -> 1， 21 % 10 -> 1， 31 % 10 -> 1，它显示了一个清晰的哈希值分布模式:值具有相同的最后一位将碰撞
  • 避免使用底数的幂(10^2， 10^3， 10^n)作为模数，因为它也会创建一个模式:值的最后一个n数字会发生冲突
  • 实际上，要避免使用任何除自身和1之外有因子的东西，因为它创建了一个模式:因子的倍数将被散列为选定的值
  • 例如，9有3作为因子，因此3， 6， 9，…999213将始终被哈希为0， 3， 6
  • 12有3和2作为因子，因此2n将始终被哈希为0， 2， 4， 6， 8， 10，而30将始终被哈希为0， 3， 6， 34
  • 这将是一个问题，如果输入不是均匀分布的，例如，如果许多值都是3n，那么我们只能得到所有可能哈希值的1/3，并且碰撞是高的
  • 因此，使用质数作为模数，唯一的模式是模数的倍数总是哈希到0，否则哈希值分布是均匀分布的

提交答案