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