posts - 5, comments - 40, trackbacks - 0, articles - 0

关于哈希表——一个常见的谬误

Posted on 2008-03-04 22:13 Wang Jinbo 阅读(9267) 评论(18)  编辑 收藏 引用 所属分类: 算法与数学
Hash Table(哈希表)就是根据对象的特征进行定位的一种数据结构。一个简单的实现方法是将对象通过某种运算得到一个整数,再让这个整数除以哈希表的大小,取其余数,以此作为对象的存储位置。
很多的书上认为,哈希表的大小最好是选择一个大的质数,并且最好不要和2的整数幂接近。《算法导论》上还认为,最不好的选择是哈希表的大小恰好是2的整数幂,对此的解释是(只记得大意):因为计算机是用二进制存储的,当一个二进制数除以一个2的整数幂的时候,结果就是这个二进制数的后几位,前面的位都丢失了,也就意味着丢失了一部分信息,进而导致哈希表中的元素分布不均匀。
这个解释看似合理,但我不认同。不光是我,Java开发小组的人也不认同。Java里的HashSet类偏偏就把哈希表的大小设置成2的整数幂。可以设想一下,对于自然数集合中的任意一个数x,对于一个正整数M,难道x mod M为某些值的概率会大些吗?显然不是,因为x是在自然数集合里任选的,当选取的次数非常多时,x mod M的结果应该是平均分布在[0,M-1]中。我认为《算法导论》的错误在于先引入了二进制,其实二进制和哈希表的“碰撞”根本没有什么关系;然后说对除以2^n的余数会丢失位,丢失信息,这显然也不对,因为只要x>=M,x mod M的结果总是要“丢失一些信息的”。照《算法导论》的说法,如果计算机采用十进制,那哈希表的容量是10^n的话岂不是很糟?这种解释显然站不住脚。
我认为对于x mod M这样的哈希函数来说,好坏应该取决于x的生成方式和M的值。比如一个字符串“ABC”,如果我让x("ABC")=65*128^2+66*128+67,即把字符串当成一个128进制的整数,那么若M=128,那就很糟糕了。因为这样无论是什么字符串,最终结果只取决于最后一个字符,这才会造成分布不均匀。

以上只是我个人的见解,有不妥之处欢迎指出。

Feedback

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2008-03-04 23:15 by turingbook
吹毛求疵一下:hash应该译为散列。
哈希这个译法显然是当年初译者误以为人名了。

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2008-03-05 00:27 by helixapp
楼主理解很正确,假如10进制的话, 10^n 次方就不好,任意非素数都可以表示为 m1^n1 * m2^n2 * m3^n3 .... 所以说素数比其他的数字更加适合啊。

不过对于计算机,2^n 次方的确是很糟的hash size, 想想你对ip地址,对内存地址求hash吧...

不过MOD的hash方法的确有缺陷,linux kernel里面用的乘以一个大素数然后取高位的方法比这个好多了

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2008-03-05 00:29 by helixapp
BTW 我敢肯定java里面HashSet类没有使用单纯求余的方法来算hash

# re: 关于哈希表——一个常见的谬误[未登录]  回复  更多评论   

2008-03-05 08:46 by cppexplore
java里的hash是乘以31的:hash=hash<<5-hash+ch。
据说就英文而言,乘以33的是最优的:hash=hash<<5+hash+ch,这个也是apache stl等一大堆著名项目或库的hash方式。
特定应用而言,还是要根据特定的数据,设计最优的hash函数。

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2008-03-05 08:56 by cppexplore
上面的语句外面都是foreach(ch in str){}。
hash表的数量 应该不是影响hash的因素吧 想不出来原因。貌似一般都把hash表的桶数量设置的很大,是实际使用到的3倍多。

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2008-03-05 11:25 by abettor
同意楼主的见解。

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2008-03-05 17:11 by #Ant
说的有一些道理,感觉hash表的大小还是要根据实际情况来选取。

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2008-04-18 15:12 by 万铁
有理, 对于mod的方法,确实与素数无关。
大于mod值的所谓信息只能“丢失”,只保留小于mod值的那些“位”。

要降低这个影响,在散列函数的计算过程中,这些低位所代表的信息也要能体现输入。比如对于字符串的散列函数, 最好能够把高位的字符串折回到低位去,这样即使取余,也会保证均匀性,只不过,有一个元素对于桶的密度会增大。

能力有限, 太形式化的描述,不会。

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2008-08-18 19:46 by roofjava@163.com
关于这个,我也认为和2的幂数无关。但是这可能跟哈希函数的设计有关,怎么说呢,很多哈希函数的设计本身是根据二进制进行的,所以《算法导论》才会得出丢失信息的结论。

不过最好还是用大数据测试比较下。

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2008-10-19 18:23 by Phoenix
哎,楼主的思维还不够严谨……

“如果计算机采用十进制,那哈希表的容量是10^n的话岂不是很糟?”
给1234,容量是10,求余得4,仅由最后一位得出,前面的数直接被无视了,而对9求余就不是这样了。

“不光是我,Java开发小组的人也不认同。”
你知道他们用的散列函数仅仅是求余?他们二者的思想没有矛盾,是你纠结的这个矛盾。

楼主的质疑态度还是很好的。

欢迎批评我:phoenix.0220@gmail.com

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2009-03-25 16:33 by ofan
正好看到《算法导论》中的hash table部分
我想《算法导论》中说表的大小不应为2的整数次方,应该是有针对性的,不是普遍的规律。

# re: 关于哈希表——一个常见的谬误[未登录]  回复  更多评论   

2010-08-05 14:12 by steven
一个理想的HASH函数,输出的值的每一位都“散列”的,无所谓丢失哪一部分来适应“桶”的大小

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2012-03-12 02:32 by Wallace
豁然开朗啊

# re: 关于哈希表——一个常见的谬误[未登录]  回复  更多评论   

2013-01-25 16:08 by richard
使用质数是有意义的, 虽然准确的证明我不会(我也没看到哪里有证明),
但是可以简单说明一下.

用最简单的hash函数 h(k) = k mod m来说明.
对于任意的k1, k2,
假设事件A为k1 mod m == k2 mod m, 即k1, k2产生冲突的概率为p(A).
事件B_i为k1 mod m取得某个余数i, p(B_i) = 1/m,
事件C_j为k2 mod m取得某个余数j, p(C_j) = 1/m,

1. 如果m为质数:
由于k1, k2是任意选取的, 所以事件B_i和C_j是相互独立的,
p(A) = p(B_x) * p(C_x) = 1/(m^2)

2. 如果m不为质数:
这时m可以写成m = a * b, (a, b不等于1或m)
假设事件D为k1和k2具有公因数a(或b), 概率为p(D),
(用~D表示D不发生, 即k1,k2互质)
* 这里p(D)我不会求, 不好意思, 不过概率论里面有, 结果是6/(pi^2) *
1) 那么, 如果在D不发生的情况下, 概率和1是一样的,
即p(A|~D) = 1/(m^2)
2) 如果D发生, 假设k1 = c1 * a, k2 = c2 * a,
事件A可转化为c1 mod b == c2 mod b,
即p(A|D) = 1/(b^2)
于是, 我们得到了p(A) = p(A|~D) + p(A|D)
= (1-p(D)) * 1/(m^2) + p(D) * 1/(b^2)
= 1/(m^2) + p(D) * (1/(b^2) - 1/(m^2))
显然p(D) >= 0, 1/(b^2) - 1/(m^2) > 0,
于是, p(A) = 1/(m^2) + p(D) * (1/(b^2) - 1/(m^2)) > 1/(m^2)

综上所述, 当m为质数时, 事件A即产生碰撞的概率比m不为质数时要小.
推广到任意选取多个数的情况下也是成立的.

有些人可能会觉得对于任意的m, k mod m都能取到[0, m-1]的数的概率是
一样的, 这确实没错. 但我们关注的问题是如何减少碰撞.

# re: 关于哈希表——一个常见的谬误[未登录]  回复  更多评论   

2013-01-25 16:54 by richard
不好意思, 上面关于p(D)的说明不太正确,改为

假设事件D为k1, k2, m具有公因数(a或b, 假设为a), 概率为p(D), (用~D表示D不发生)
* 这里p(D)我不会求, 不好意思, 不过两个数互质的概率是6/(pi^2) *

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2013-03-02 01:13 by Aule
上面的证明我觉得有问题,

2) 如果D发生, 假设k1 = c1 * a, k2 = c2 * a,
事件A可转化为c1 mod b == c2 mod b,

这一步隐含的内容是:
(c1*a) mod (a*b) = c1 mod b
但是同余并不具有可除性 这个等式是不成立的 因此这一步我认为是错了

例如k1=2*7=14,k2=5*7=35
即 c1=2,c2=5,b=u7
c1,c2在模b环境下并不同余

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2014-02-23 23:11 by rookieaca
没看过算法导论,不过我的理解是否均匀,要看 x 的特征,以及选取的算法。
对于,实际应用中, 基于内存地址来做HASH的话,可以标志内存的某一块数据(OOP可以是堆中分配的对象的地址)。在这种情况下由于很多实际的机器实现的地址的对齐方式,分配的内存地址都是2的倍数。在这种情况下hash(address) = (address)MOD M,
你想想如果M=2*x的话, 分布情况会是怎么样?

# re: 关于哈希表——一个常见的谬误  回复  更多评论   

2014-03-25 16:13 by jaub
算法导论说的是正确的!
楼主说“,因为x是在自然数集合里任选的,当选取的次数非常多时,x mod M的结果应该是平均分布在[0,M-1]中”。那么如果存在这样一个集合,它的元素的低位严重偏斜到某几个值,x对M=2^n取余后,剩下的低位值决定元素在哈希表中的位置,而低位会聚集在某些值上,导致哈希表严重冲突。

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理