散列函数为什么要使用素数模数？

Question

很久以前,我以1.25美元的价格从交易台上买了一本数据结构书.在其中,哈希函数的解释说,由于"数学的本质",它最终应该由质数修改.

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

无论如何,我有多年的时间来思考数学的本质,但仍然无法弄明白.

当存在大量的桶时,数字的分布是否真的更均匀？或者这是一个老程序员的故事,每个人都接受,因为其他人都接受它？

Answer 1

通常,简单的散列函数通过获取输入的"组成部分"(在字符串的情况下为字符),并将它们乘以某个常量的幂,并将它们以某种整数类型加在一起来工作.因此,例如字符串的典型(尽管不是特别好)散列可能是:

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

然后,如果输入一堆具有相同第一个字符的字符串,那么结果将全部是相同的模k,至少直到整数类型溢出.

[例如,Java的字符串hashCode与此类似 - 它的字符顺序相反,k = 31.因此,在以相同方式结束的字符串之间获得以模数31为模型的醒目关系,以及在除了接近结尾之外相同的字符串之间以2 ^ 32为模数的醒目关系.这并不会严重扰乱哈希表行为.]

散列表通过将散列的模数与桶的数量相乘来工作.

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

现在,假设有人将一大堆值放入哈希表中,这些哈希表在项之间具有某种关系,就像所有具有相同的第一个字符一样.我会说,这是一种相当可预测的使用模式,因此我们不希望它产生太多的冲突.

事实证明,"由于数学的性质",如果散列中使用的常量和桶的数量是互质的,那么在一些常见情况下碰撞会被最小化.如果它们不是互质的,那么在输入之间存在一些相互简单的关系,其中碰撞没有被最小化.所有的哈希值都与公共因子相等,这意味着它们都将落入具有以公共因子为模的值的桶的第1个中.你得到n次碰撞,其中n是公因子.因为n至少为2,所以我认为一个相当简单的用例产生至少两倍于正常情况的冲突是不可接受的.如果某个用户打算将我们的分发分解成桶,我们希望它是一个奇怪的事故,而不是一些简单的可预测用法.

现在,散列表实现显然无法控制放入它们的项目.他们不能阻止他们相关.所以要做的是确保常量和桶数是互质的.这样,您不仅仅依靠"最后"组件来确定铲斗的模数与一些小的公因数.据我所知,他们没有必要成为实现这一点的首要任务,只需互质.

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

在实践中,我认为使用2的幂作为桶的数量是相当正常的.这是方便的,并且节省了必须搜索或预先选择正确幅度的素数.因此,您依赖哈希函数不使用偶数乘数,这通常是一个安全的假设.但是你仍然可以根据上面的哈希函数偶尔得到糟糕的哈希散列行为,而主要的桶数可能会有所帮助.

关于"一切都必须是素数"的原则,就我所知,在哈希表上进行良好分配是一个充分但不是必要的条件.它允许每个人进行互操作,而无需假设其他人遵循相同的规则.

[编辑:有另一个更专业的理由使用素数桶,如果你处理线性探测的碰撞.然后你从哈希码计算一个步幅,如果那个步幅是桶数的一个因子,那么你只能在你回到起点之前做(bucket_count/stride)探测.你最想避免的情况是stride = 0,当然,这必须是特殊的,但是为了避免特殊套管bucket_count/stride等于一个小整数,你可以只做一个bucket_count prime而不关心什么提供的步幅不是0.]

Answer 2

从哈希表插入/ retreiving时,首先要做的是计算给定键的hashCode,然后通过hashCode%table_length将hashCode修剪为hashTable的大小来找到正确的桶.以下是您最有可能在某处阅读的2个"陈述"

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 ......}那样生成太多另一个hashCode的hashCodes.但是如果你的hashTable应该有这个可能有点困难数百万条目.或者通过使GreatestCommonFactor(table_length,x)等于1来简单地使m等于table_length,即通过使table_length与x进行互操作.如果x可以是任何数字,那么请确保table_length是素数.

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

Answer 3

只是为了写下从答案中收集到的一些想法。

• 散列使​​用模数，因此任何值都可以适合给定范围
• 我们想要随机化碰撞
• 随机化碰撞意味着不存在碰撞如何发生的模式，或者，更改输入中的一小部分将导致完全不同的哈希值
• 要随机化碰撞，请避免使用基数（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，否则散列值分布均匀分布

Answer 4

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

非常明确的解释,也有图片.

编辑:作为总结,使用素数是因为当您将值乘以所选的素数并将它们全部加起来时,您最有可能获得唯一值.例如,给定一个字符串,将每个字母值与素数相乘,然后将它们全部添加将为您提供其哈希值.

一个更好的问题是,为什么31号呢？

Answer 5

TL;博士

index[hash(input)%2]会导致所有可能的哈希值和一系列值的一半发生碰撞. index[hash(input)%prime]导致所有可能的哈希值<2的碰撞.将除数固定为表大小也可确保数字不能大于表.

Answer 6

使用Primes是因为您很有可能获得使用模数P的多项式的典型散列函数的唯一值.比如,对长度<= N的字符串使用此类散列函数,并且您发生了碰撞.这意味着2个不同的多项式产生相同的模P值.这些多项式的差异也是相同度数N(或更小)的多项式.它只有N个根(这里是数学本质所表现出来的,因为这个说法只适用于场上的多项式=>素数).因此,如果N远小于P,则可能不会发生碰撞.之后,实验可能会显示37大到足以避免长度为5-10的字符串哈希表的冲突,并且足够小以用于计算.

Answer 7

只是为了提供另一个观点,就是这个网站:

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

哪种情况认为你应该使用最大数量的存储桶,而不是向下舍入到主数量的存储桶.这似乎是一种合理的可能性.直觉上,我当然可以看到更多的桶会更好,但我无法对此进行数学论证.

Answer 8

复制我的其他答案/sf/answers/3018887861/。有关更多详细信息和示例，请参阅它。

我相信这与计算机以 2 为基数工作这一事实有关。想想同样的事情如何适用于 10 基数：

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

数字是什么并不重要：只要它以 8 结尾，它模 10 就是 8。

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