深藍(lán)色的空間

Hash Table（哈希表）就是根據(jù)對(duì)象的特征進(jìn)行定位的一種數(shù)據(jù)結(jié)構(gòu)。一個(gè)簡(jiǎn)單的實(shí)現(xiàn)方法是將對(duì)象通過(guò)某種運(yùn)算得到一個(gè)整數(shù)，再讓這個(gè)整數(shù)除以哈希表的大小，取其余數(shù)，以此作為對(duì)象的存儲(chǔ)位置。
很多的書上認(rèn)為，哈希表的大小最好是選擇一個(gè)大的質(zhì)數(shù)，并且最好不要和2的整數(shù)冪接近。《算法導(dǎo)論》上還認(rèn)為，最不好的選擇是哈希表的大小恰好是2的整數(shù)冪，對(duì)此的解釋是（只記得大意）：因?yàn)橛?jì)算機(jī)是用二進(jìn)制存儲(chǔ)的，當(dāng)一個(gè)二進(jìn)制數(shù)除以一個(gè)2的整數(shù)冪的時(shí)候，結(jié)果就是這個(gè)二進(jìn)制數(shù)的后幾位，前面的位都丟失了，也就意味著丟失了一部分信息，進(jìn)而導(dǎo)致哈希表中的元素分布不均勻。
這個(gè)解釋看似合理，但我不認(rèn)同。不光是我，Java開發(fā)小組的人也不認(rèn)同。Java里的HashSet類偏偏就把哈希表的大小設(shè)置成2的整數(shù)冪。可以設(shè)想一下，對(duì)于自然數(shù)集合中的任意一個(gè)數(shù)x，對(duì)于一個(gè)正整數(shù)M，難道x mod M為某些值的概率會(huì)大些嗎？顯然不是，因?yàn)閤是在自然數(shù)集合里任選的，當(dāng)選取的次數(shù)非常多時(shí)，x mod M的結(jié)果應(yīng)該是平均分布在[0,M-1]中。我認(rèn)為《算法導(dǎo)論》的錯(cuò)誤在于先引入了二進(jìn)制，其實(shí)二進(jìn)制和哈希表的“碰撞”根本沒(méi)有什么關(guān)系；然后說(shuō)對(duì)除以2^n的余數(shù)會(huì)丟失位，丟失信息，這顯然也不對(duì)，因?yàn)橹灰獂>=M，x mod M的結(jié)果總是要“丟失一些信息的”。照《算法導(dǎo)論》的說(shuō)法，如果計(jì)算機(jī)采用十進(jìn)制，那哈希表的容量是10^n的話豈不是很糟？這種解釋顯然站不住腳。
我認(rèn)為對(duì)于x mod M這樣的哈希函數(shù)來(lái)說(shuō)，好壞應(yīng)該取決于x的生成方式和M的值。比如一個(gè)字符串“ABC”，如果我讓x("ABC")=65*128^2+66*128+67，即把字符串當(dāng)成一個(gè)128進(jìn)制的整數(shù)，那么若M=128，那就很糟糕了。因?yàn)檫@樣無(wú)論是什么字符串，最終結(jié)果只取決于最后一個(gè)字符，這才會(huì)造成分布不均勻。

以上只是我個(gè)人的見(jiàn)解，有不妥之處歡迎指出。