logo标签列表

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

language-agnosticdata-structureshash
429
很久以前，我在特价书桌上花了1.25美元买了一本数据结构的书。在书中，一个哈希函数的解释指出，由于“数学的本质”，最终应该对质数取模。
你能从1.25美元的书中期待什么呢？
无论如何，多年来我一直在思考数学的本质，但仍然无法理解。
当桶的数量是质数时，数字的分布是否真的更均匀？
还是这只是一个老程序员传说，因为每个人都接受它？
3
完全合理的问题：为什么桶的数量应该是质数？ - Draemon
3
这个问题似乎不适合在此讨论，更适合在 [cs.se] 上进行讨论。 - Lightness Races in Orbit
4
另一篇论述充分的解释。 - Volodymyr Boiko
1
为什么在哈希函数中使用质数作为模数最好？Java中为什么使用31作为乘数生成哈希码？Rabin-Karp滚动哈希中如何选择基数和模数质数，可以参考此答案。 - bain
这里有另一个与之相关的问题的很好的解释，附带一些惊人的证据数字 - https://www.quora.com/Does-making-array-size-a-prime-number-help-in-hash-table-implementation-Why - Anjan Biswas
显示剩余2条评论
17个回答
290

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

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

如果一堆字符串的首字母都相同，那么它们的结果在模k下都是相同的，至少在整数类型溢出之前是这样的。举个例子，Java的字符串哈希码与此非常相似 - 它以k = 31的顺序反转字符。因此，在以相同方式结束的字符串之间，模31之间存在显着的关系，在除结尾附近相同的字符串之间，模2^32之间存在显着的关系。这不会严重破坏哈希表的行为。哈希表通过对哈希值取桶数的模来工作。在哈希表中不要为可能的情况产生冲突很重要，因为冲突会降低哈希表的效率。现在，假设有人将许多具有某些项目之间关系的值放入哈希表中，比如所有的值都具有相同的首字母。我认为这是一个相当可预测的使用模式，所以我们不希望它产生太多冲突。
原来，“由于数学的本质”，如果哈希中使用的常量和桶的数量是互质的话，在某些常见情况下可以最小化碰撞。如果它们不是互质，那么在一些相当简单的输入关系中，碰撞并不是最小化的。所有哈希值对公共因子取模后都相等，这意味着它们将全部落入具有该值对公共因子取模的1/n个桶中。你会得到n倍的碰撞，其中n是公共因子。由于n至少为2，我认为对于相当简单的用例，生成至少两倍于正常情况的碰撞是不可接受的。如果某个用户要将我们的分布分成桶，我们希望这只是一个偶然事件，而不是一些简单可预测的用法。
现在，哈希表实现显然无法控制放入其中的项。它们不能防止它们之间存在关联。所以要做的是确保常量和桶计数是互质的。这样你就不是仅仅依靠“最后”一个组件来确定与某个小公共因子相关的桶的模数了。据我所知，它们不必是素数才能实现这一点，只需要互质即可。
但是如果哈希函数和哈希表是独立编写的，那么哈希表就不知道哈希函数的工作原理。它可能使用一个具有较小因子的常量。如果你很幸运，它可能完全不同，并且是非线性的。如果哈希足够好，那么任何桶计数都可以。但偏执的哈希表不能假设有一个好的哈希函数，因此应该使用质数个桶。同样，偏执的哈希函数应该使用一个相对较大的质数常量，以减少某人使用与常量有公共因子的桶数的机会。
在实践中，我认为使用2的幂作为桶数是相当普遍的。这是方便的，可以节省搜索或预先选择正确数量级的质数的时间。因此，你需要确保哈希函数不要使用偶数倍增量，这通常是一个安全的假设。但是你仍然可能遇到基于上述哈希函数的偶发坏哈希行为，而质数的桶数可以进一步帮助解决这个问题。
将“所有东西都必须是质数”作为原则大概是一个足够但不是必要的条件来获得良好的哈希分布。这样可以让每个人在不需要假设其他人遵循相同规则的情况下进行互操作。
[编辑：使用质数个桶的另一个更专业的原因是，如果您使用线性探测处理冲突。然后，您从哈希码计算一个步幅，如果该步幅恰好是桶数的因子，则在回到起点之前只能执行（bucket_count / stride）次探测。当然，您最想避免的情况是stride = 0，这必须特殊处理，但为了避免特殊处理bucket_count / stride等于小整数，您可以使bucket_count成为质数，不关心步幅是什么，只要它不是0即可。]
1
仅作为一点补充说明：有关哈希码因子k的明智选择的讨论在此处：https://dev59.com/SHI-5IYBdhLWcg3weoPR。 - Hans-Peter Störr
11
这是一个很棒的答案。请你进一步解释一下：“因此，在以相同方式结尾的字符串之间，您会得到模31的显著关系，并且在除结尾处附近不同的字符串之间，您会得到模2^32的显著关系。这不会严重破坏哈希表的行为。” 我特别不理解2 ^ 32部分。这段话的意思是，当两个字符串以相同的方式结尾时，它们在模31下具有相似性；而当两个字符串在结尾附近有轻微差异时，它们在模2^32下具有相似性。这种相似性可以用于哈希函数中，以提高效率。使用这种哈希函数不会严重影响哈希表的性能。其中，2^32是指2的32次方，即4294967296。 - ordinary
4
为了让事情更清楚，需要补充说明："所有哈希在模公因数下相等"的原因是：如果你考虑哈希函数的例子hash = 第一个字符 + 第二个字符*k + ...，并且选择具有相同第一个字符的字符串，则这些字符串的hash%k将相等。如果M是散列表的大小，g是M和k的最大公约数，则(hash%k)%g等于hash%g(因为g可以整除k)，因此这些字符串的hash%g也将相等。现在考虑(hash%M)%g，这等于hash%g(因为g可以整除M)。因此，对于所有这些字符串，(hash%M)%g都是相等的。 - Quark
1
@DanielMcLaury Joshua Bloch 解释了为什么 Java 中使用该哈希函数 - 它在两本流行的书籍（K＆R，Dragon book）中被推荐，并在英语词典上具有低碰撞率。它很快（使用Horner's method）。显然，即使是 K＆R 也不记得它来自哪里。类似的函数是Rabin fingerprint，来自Rabin-Karp algorithm（1981），但 K＆R（1978）比它更早。 - bain
1
@SteveJessop，请问您能解释一下“在字符串末尾附近除外，相同字符串之间模2^32的显著关系”是什么意思吗？谢谢。 - Khanna111
显示剩余6条评论
34
插入/检索哈希表时，首先要计算给定键的hashCode，然后通过将hashCode修剪到hashTable的大小来查找正确的桶，方法是hashCode％table_length。这里有两个“语句”，你可能在某个地方读过：
  1. 如果您对table_length使用2的幂次方，则查找（hashCode（key）％2 ^ n）就像（hashCode（key）＆（2 ^ n-1））一样简单快速。但是，如果用于计算给定键的hashCode的函数不好，那么您肯定会遭受许多键聚集在少数哈希桶中的困扰。
  2. 但是，如果您对table_length使用素数，则即使您拥有稍微愚蠢的hashCode函数，也可以将计算出的hashCodes映射到不同的哈希桶中。
这就是证明。
假设您的hashCode函数产生以下hashCodes之一{x，2x，3x，4x，5x，6x ...}，那么所有这些都将聚集在仅m个桶中，其中m = table_length / GreatestCommonFactor(table_length，x)。（很容易验证/推导出这一点）。现在，您可以执行以下操作以避免聚类。
请确保不要生成太多的哈希码，这些哈希码是另一个哈希码的倍数，例如{x, 2x, 3x, 4x, 5x, 6x...}。但是，如果您的哈希表应该有数百万个条目，则可能有点困难。 或者，通过使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

20

总结一下从答案中得出的一些想法。

  • 哈希使用取模运算，因此任何值都可以适应给定范围
  • 我们希望随机碰撞
  • 随机碰撞意味着没有规律来描述碰撞如何发生，或者更改输入的一小部分将导致完全不同的哈希值
  • 为了随机碰撞，避免使用基数（十进制中的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，3n将总是散列到0、3、6和9
  • 如果输入不均匀分布，则会出现问题，例如如果许多值为3n，那么我们只得到了所有可能哈希值的1/3，冲突率很高
  • 因此，通过使用质数作为模数，唯一的模式是模数的倍数总是散列为0，否则哈希值分布均匀
    • 2
    我非常理解你的解释。 - Hamzah
    15

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

    这篇文章给出了清晰的解释，还配有图片。

    编辑：简单来说，使用质数是因为选择一个质数作为乘数后，将值相乘并全部加起来可以得到最佳的唯一值。例如，对于一个给定的字符串，将每个字母的值乘以质数再将它们相加，可以得到该字符串的哈希值。

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

    6
    尽管我认为提供摘要会有帮助，以防该网站不再存在，但在此处保存其内容的残余对于SO来说也是有价值的。 - Thomas Owens
    4
    这篇文章没有解释原因，但提到“研究人员发现使用31作为质数可以更好地分配密钥，并减少冲突的数量。没有人知道为什么......”有趣的是，实际上问了和我一样的问题。 - theschmitzer
    一个更好的问题是，为什么恰好是数字31？如果你的意思是为什么使用数字31，那么你指向的文章告诉你原因，即因为它很快可以乘以和cos测试表明它是最好的。我见过的另一个流行的乘数是33，这证实了速度问题（至少最初）是一个重要因素的理论。如果你的意思是，31有什么特别之处使它在测试中更好，那么恐怕我不知道。 - sgmoore
    6
    在计算机中，CPU可以将数字31优化为(x*32)-1的运算。其中*32是一个简单的位移操作，甚至更好的做法是使用立即地址比例因子（例如，在x86/x64上使用lea eax, eax*8; leax, eax,eax*4）。因此，*31是质数乘法的一个很好的选择。几年前这基本上是正确的——现在最新的CPU架构具有近乎瞬时的乘法，但除法始终较慢... - Arnaud Bouchez
    如果是这样的话，他们也可以使用15，因为它的因数（除了本身和1）是3和5，都是质数。许多其他数字也是如此：10（2和5），14（2和7），21（3、7）等。 - afaolek
    显示剩余3条评论
    11

    使用质数是因为您有很好的机会获得一个典型哈希函数的唯一值，该哈希函数使用模P的多项式。假设您将这样的哈希函数用于长度小于或等于N的字符串，并且发生冲突。这意味着两个不同的多项式产生了相同的模P的值。这些多项式的差异又是同一次数N（或更少）的多项式。它最多只有N个根（这里体现了数学的本质，因为这个声明只适用于一个素数域上的多项式 => 素数）。因此，如果N远小于P，则可能不会发生冲突。之后，实验可能会表明37足以避免在链表中出现碰撞，而且对于长度为5-10的字符串的哈希表来说，它也足够小以进行计算。

    1
    虽然现在解释似乎很明显，但我是在读完A.Shen的《编程：定理与问题》（俄语版）这本书之后才理解的，可以参考一下关于Rabin算法的讨论。不确定是否存在英文译版。 - TT_ stands with Russia
    10

    简述

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

    12
    2是一个质数。 - Ganesh Chowdhary Sadanala
    2
    即使我们将这个答案解释为 _index[hash(input)%prime] 导致小于所有可能哈希的2个碰撞，其中 prime > 2_，它仍然没有意义，因为该条件对于任何大于2的数字都成立。 - alelom
    5

    提供一种替代观点，这里有一个网站：

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

    该网站认为，您应该使用尽可能多的存储桶，而不是将其舍入为质数。这似乎是一个合理的可能性。直觉上，我肯定能看出更多的存储桶会更好，但我无法做出数学论证。

    更多的桶意味着更少的碰撞：请参考鸽笼原理。 - Unknown
    12
    @Unknown: 我不相信那是真的。如果我错了，请纠正我，但我认为将抽屉原理应用于哈希表只能让你断言如果有更多的元素比箱子，就会发生冲突，并不能得出任何有关冲突数量或密度的结论。尽管如此，我仍然相信增加箱子数量是正确的做法。 - Falaina
    如果你假设碰撞在实际上是随机的，那么根据生日悖论，更大的空间（桶）将减少碰撞发生的概率。 - Unknown
    2
    @Unknown 你忽略了冲突也取决于哈希函数本身。因此，如果哈希函数非常糟糕，那么无论你增加多大的尺寸，仍然可能会有相当数量的冲突。 - Suraj Chandran
    原始文章似乎已经消失了，但这里有一些富有洞见的评论，包括与原作者的讨论。https://news.ycombinator.com/item?id=650487 - Adrian McCarthy
    @AdrianMcCarthy：但要小心：有人说“如果n是质数，那么2^n-1也是质数”，这是颠倒的。有些人指出，如果你编写一个允许用户提供哈希函数的库，它可能会偏爱某些模N余数，这可以通过使用与N互质的表大小来抵消。而且听起来很有道理，稍小一点的表格成本（Δ#buckets）可能比使用所有桶（#buckets/x）的好处更少。 - PJTraill
    4
    我认为这只是因为计算机以二进制工作的原因。想想看十进制数如何运作：
    • 8 % 10 = 8
    • 18 % 10 = 8
    • 87865378 % 10 = 8
    无论数字是什么都没关系，只要以8结尾，其对10取模的结果就是8。 选择一个足够大而不是2的幂次方的数字将确保哈希函数确实是所有输入位的函数，而不仅仅是它们的子集。请参考我在https://dev59.com/wW025IYBdhLWcg3wkG17#43126969中的回答，了解更多细节和示例。
    这很棒，即使它可能不完整。我不知道其他人在说什么。 - dz902
    4
    关于素数幂模数的"数学本质"是它们是有限域的一个构建块。另外两个构建块是加法和乘法运算。素数模数的特殊属性是它们形成了一个带有“常规”加法和乘法运算的有限域，只需取模即可。这意味着每个乘法映射到不同的模素数整数，每个加法也是如此。
    素数模数的优点是:
    • 在选择辅助哈希中的次要乘数时，它们提供了最大的自由度，除了0以外的所有乘数都会访问每个元素一次
    • 如果所有哈希都小于模数，则根本不会发生碰撞
    • 随机质数比二次幂模数更好地混合并压缩所有位的信息，而不仅仅是子集
    然而，它们有一个巨大的缺点，需要进行整数除法，即使在现代CPU上也需要很多（约为15-40）个周期。只需约一半的计算即可确保哈希混合得非常好。两个乘法和Xorshift操作会比质数模数更好地混合。然后我们可以使用任何最快的哈希表大小和哈希缩减，对于2的幂表大小总共需要7个操作，对于任意大小约需要9个操作。
    我最近查看了许多最快的哈希表实现，其中大部分不使用质数模数。
    哈希表索引的分布主要取决于所使用的哈希函数。质数模数无法修复糟糕的哈希函数，良好的哈希函数也不会从质数模数中受益。然而，在某些情况下，它们可能是有利的。例如，它可以修补半糟糕的哈希函数。
    为什么说质数模数需要整数除法？我猜人们谈论的是那种只需要加法和乘法的常见实现方式： hash = 模数 * hash + 字段1; hash = 模数 * hash + 字段2; ... - Hans-Peter Störr
    @Hans-PeterStörr 计算机计算模数的方式是通过整数除法：n%m = n - floor(n/d)。你所提到的不是质数模数，而似乎是线性探测（field1，field2 ...）与一个名为模数的乘数矛盾地结合。但是，如何确保您的哈希是小于表大小的数字？您需要将其缩小，通常使用取模来完成。 - Wolfgang Brehm
    4

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

    许多哈希函数将数据中的各个元素与一些因子相乘，模数是机器字长对应的二次幂（只需让计算溢出即可使模数自由）。

    你不希望在数据元素的乘法器和哈希表大小之间有任何共同因子，因为这样可能会导致改变数据元素时数据未能分散到整个表中。如果你选择质数作为表的大小，则这种共同因子的可能性非常小。

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

    网页内容由stack overflow 提供, 点击上面的
    可以查看英文原文，
    原文链接