很久以前,我花1.25美元在便宜货桌上买了一本数据结构的书。在这篇文章中,哈希函数的解释说,由于“数学的本质”,它最终应该被一个质数mod。
你对一本1.25美元的书有什么期待?
不管怎么说,我花了很多年思考数学的本质,但还是没弄明白。
当有质数个桶时,数字的分布真的更均匀吗?
或者这是一个老程序员的故事,每个人都接受,因为其他人都接受?
很久以前,我花1.25美元在便宜货桌上买了一本数据结构的书。在这篇文章中,哈希函数的解释说,由于“数学的本质”,它最终应该被一个质数mod。
你对一本1.25美元的书有什么期待?
不管怎么说,我花了很多年思考数学的本质,但还是没弄明白。
当有质数个桶时,数字的分布真的更均匀吗?
或者这是一个老程序员的故事,每个人都接受,因为其他人都接受?
当前回答
关于素数幂模的“数学的本质”是它们是有限域的一个组成部分。另外两个构建块是加法运算和乘法运算。素模的特殊性质是,它们用“常规”的加法和乘法运算形成一个有限域,只是取到模。这意味着每一个乘法都映射到一个不同的整数对质数求模,每一个加法也是如此。
质模的优势在于:
它们在二次哈希中选择次乘数时给予了最大的自由,除了0之外的所有乘数最终都将访问所有元素一次 如果所有哈希值都小于模量,则根本不会发生碰撞 随机质数比两个模的幂更好地混合,并压缩所有比特的信息,而不仅仅是一个子集
然而,它们有一个很大的缺点,它们需要整数除法,这需要很多(~ 15-40)个周期,即使在现代CPU上也是如此。用大约一半的计算就可以确保散列混合得很好。两次乘法和异移运算比一个质数模更容易混合。然后,我们可以使用任何哈希表的大小,哈希约简是最快的,对于2个表大小的幂,总共给出7个操作,对于任意大小的表,大约9个操作。
我最近研究了许多最快的哈希表实现,其中大多数都不使用质数模块。
哈希表索引的分布主要依赖于所使用的哈希函数。质数模量不能修复一个坏的哈希函数,一个好的哈希函数也不能从质数模量中受益。然而,在某些情况下,它们可能是有利的。例如,它可以修复半坏的哈希函数。
其他回答
博士tl;
Index [hash(input)%2]将导致所有可能哈希值的一半和一段值发生冲突。Index [hash(input)%prime]导致所有可能哈希值中的<2的碰撞。将除数固定为表的大小还可以确保数字不能大于表。
这取决于哈希函数的选择。
许多哈希函数通过将数据中的各种元素与一些因子相乘,再乘以与机器的字大小相对应的2的幂的模(这个模可以通过让计算溢出来释放)来组合数据中的各种元素。
您不希望在数据元素的乘数和哈希表的大小之间有任何公共因子,因为这样可能会发生改变数据元素不会将数据分散到整个表上的情况。如果你为表的大小选择一个质数,这样的公因数是极不可能的。
另一方面,这些因数通常由奇数质数组成,因此在哈希表中使用2的幂也应该是安全的(例如,Eclipse在生成Java hashCode()方法时使用31)。
只是把从答案中得到的一些想法写下来。
Hashing uses modulus so any value can fit into a given range We want to randomize collisions Randomize collision meaning there are no patterns as how collisions would happen, or, changing a small part in input would result a completely different hash value To randomize collision, avoid using the base (10 in decimal, 16 in hex) as modulus, because 11 % 10 -> 1, 21 % 10 -> 1, 31 % 10 -> 1, it shows a clear pattern of hash value distribution: value with same last digits will collide Avoid using powers of base (10^2, 10^3, 10^n) as modulus because it also creates a pattern: value with same last n digits matters will collide Actually, avoid using any thing that has factors other than itself and 1, because it creates a pattern: multiples of a factor will be hashed into selected values For example, 9 has 3 as factor, thus 3, 6, 9, ...999213 will always be hashed into 0, 3, 6 12 has 3 and 2 as factor, thus 2n will always be hashed into 0, 2, 4, 6, 8, 10, and 3n will always be hashed into 0, 3, 6, 9 This will be a problem if input is not evenly distributed, e.g. if many values are of 3n, then we only get 1/3 of all possible hash values and collision is high So by using a prime as a modulus, the only pattern is that multiple of the modulus will always hash into 0, otherwise hash values distributions are evenly spread
为了提供另一种观点,这里有一个网站:
http://www.codexon.com/posts/hash-functions-the-modulo-prime-myth
它认为你应该使用尽可能多的桶而不是四舍五入到质数桶。这似乎是个合理的可能性。直观地说,我当然可以看到桶的数量越多越好,但我无法对此进行数学论证。
我想为Steve Jessop的回答补充一些东西(我不能评论,因为我没有足够的声誉)。但我找到了一些有用的材料。他的回答很有帮助,但他犯了一个错误:桶的大小不应该是2的幂。我引用Thomas Cormen, Charles Leisersen等人写的《算法导论》263页
When using the division method, we usually avoid certain values of m. For example, m should not be a power of 2, since if m = 2^p, then h(k) is just the p lowest-order bits of k. Unless we know that all low-order p-bit patterns are equally likely, we are better off designing the hash function to depend on all the bits of the key. As Exercise 11.3-3 asks you to show, choosing m = 2^p-1 when k is a character string interpreted in radix 2^p may be a poor choice, because permuting the characters of k does not change its hash value.
希望能有所帮助。