很久以前,我花1.25美元在便宜货桌上买了一本数据结构的书。在这篇文章中,哈希函数的解释说,由于“数学的本质”,它最终应该被一个质数mod。
你对一本1.25美元的书有什么期待?
不管怎么说,我花了很多年思考数学的本质,但还是没弄明白。
当有质数个桶时,数字的分布真的更均匀吗?
或者这是一个老程序员的故事,每个人都接受,因为其他人都接受?
很久以前,我花1.25美元在便宜货桌上买了一本数据结构的书。在这篇文章中,哈希函数的解释说,由于“数学的本质”,它最终应该被一个质数mod。
你对一本1.25美元的书有什么期待?
不管怎么说,我花了很多年思考数学的本质,但还是没弄明白。
当有质数个桶时,数字的分布真的更均匀吗?
或者这是一个老程序员的故事,每个人都接受,因为其他人都接受?
当前回答
博士tl;
Index [hash(input)%2]将导致所有可能哈希值的一半和一段值发生冲突。Index [hash(input)%prime]导致所有可能哈希值中的<2的碰撞。将除数固定为表的大小还可以确保数字不能大于表。
其他回答
关于素数幂模的“数学的本质”是它们是有限域的一个组成部分。另外两个构建块是加法运算和乘法运算。素模的特殊性质是,它们用“常规”的加法和乘法运算形成一个有限域,只是取到模。这意味着每一个乘法都映射到一个不同的整数对质数求模,每一个加法也是如此。
质模的优势在于:
它们在二次哈希中选择次乘数时给予了最大的自由,除了0之外的所有乘数最终都将访问所有元素一次 如果所有哈希值都小于模量,则根本不会发生碰撞 随机质数比两个模的幂更好地混合,并压缩所有比特的信息,而不仅仅是一个子集
然而,它们有一个很大的缺点,它们需要整数除法,这需要很多(~ 15-40)个周期,即使在现代CPU上也是如此。用大约一半的计算就可以确保散列混合得很好。两次乘法和异移运算比一个质数模更容易混合。然后,我们可以使用任何哈希表的大小,哈希约简是最快的,对于2个表大小的幂,总共给出7个操作,对于任意大小的表,大约9个操作。
我最近研究了许多最快的哈希表实现,其中大多数都不使用质数模块。
哈希表索引的分布主要依赖于所使用的哈希函数。质数模量不能修复一个坏的哈希函数,一个好的哈希函数也不能从质数模量中受益。然而,在某些情况下,它们可能是有利的。例如,它可以修复半坏的哈希函数。
Primes are used because you have good chances of obtaining a unique value for a typical hash-function which uses polynomials modulo P. Say, you use such hash-function for strings of length <= N, and you have a collision. That means that 2 different polynomials produce the same value modulo P. The difference of those polynomials is again a polynomial of the same degree N (or less). It has no more than N roots (this is here the nature of math shows itself, since this claim is only true for a polynomial over a field => prime number). So if N is much less than P, you are likely not to have a collision. After that, experiment can probably show that 37 is big enough to avoid collisions for a hash-table of strings which have length 5-10, and is small enough to use for calculations.
我想为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.
希望能有所帮助。
我读过一个流行的wordpress网站,上面有一些流行的答案。根据我的理解,我想分享一个简单的观察。
你可以在这篇文章中找到所有的细节,但假设以下是正确的:
使用质数给我们提供了一个唯一值的“最佳机会”
一个通用的hashmap实现需要有两个东西是唯一的。
键的唯一哈希码 用于存储实际值的唯一索引
我们如何得到唯一索引?通过使内部容器的初始大小也是质数。基本上,质数的存在是因为它具有产生唯一数字的独特特性,我们最终用它来标识对象并在内部容器中查找索引。
例子:
Key = " Key "
Value = " Value " uniqueId = "k" * 31 ^ 2 + "e" * 31 ^ 1 ' + “y”
映射到唯一id
现在我们想要一个独特的位置来存放我们的价值,所以我们
uniqueId % internalContainerSize == uniqueLocationForValue,假设internalContainerSize也是质数。
我知道这是简化的,但我希望你能理解我的大意。
我想说,这个链接的第一个答案是我找到的关于这个问题的最清晰的答案。
考虑键K ={0,1,…,100}和一个哈希表,其中桶数为m = 12。因为3是12的因数,所以是3倍数的键将被散列到是3倍数的存储桶中:
键{0,12、24、36…}将被散列到bucket 0。 键{3,15日,27日,39岁,…}将被散列到桶3。 键{42 6日,18日,30日,…}将被散列到桶6。 键{9日,21日,33岁,45岁,…}将被散列到桶9。
如果K是均匀分布的(即K中的每个键出现的可能性都是相等的),那么m的选择就不是那么关键了。但是,如果K不是均匀分布的呢?想象最有可能出现的键是3的倍数。在这种情况下,所有不是3倍数的桶都很可能是空的(这在哈希表性能方面非常糟糕)。
这种情况比看起来更常见。例如,想象一下,您正在根据对象在内存中的存储位置来跟踪它们。如果您的计算机的字大小是4个字节,那么您将哈希键是4的倍数。不用说,选择m是4的倍数将是一个糟糕的选择:你将有3m/4个桶完全空了,所有的键都在剩下的m/4个桶中碰撞。
一般来说:
K中每一个与桶数m有公因数的键都将被哈希为这个因数的倍数。
因此,为了尽量减少碰撞,减少m和k的元素之间的公因数的数量是很重要的,这是如何实现的呢?通过选择m是一个因数很少的数,一个质数。
来自马里奥的回答。