# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2008-03-04 23:15 by
吹毛求疵一下：hash應(yīng)該譯為散列。
哈希這個譯法顯然是當(dāng)年初譯者誤以為人名了。
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2008-03-05 00:27 by
樓主理解很正確，假如10進(jìn)制的話, 10^n 次方就不好，任意非素數(shù)都可以表示為 m1^n1 * m2^n2 * m3^n3 .... 所以說素數(shù)比其他的數(shù)字更加適合啊。
不過對于計算機(jī)，2^n 次方的確是很糟的hash size, 想想你對ip地址，對內(nèi)存地址求hash吧...
不過MOD的hash方法的確有缺陷，linux kernel里面用的乘以一個大素數(shù)然后取高位的方法比這個好多了
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2008-03-05 00:29 by
BTW 我敢肯定java里面HashSet類沒有使用單純求余的方法來算hash
# re: 關(guān)于哈希表——一個常見的謬誤[未登錄] 回復(fù) 更多評論
2008-03-05 08:46 by
java里的hash是乘以31的：hash=hash<<5-hash+ch。
據(jù)說就英文而言，乘以33的是最優(yōu)的：hash=hash<<5＋hash+ch，這個也是apache stl等一大堆著名項目或庫的hash方式。
特定應(yīng)用而言，還是要根據(jù)特定的數(shù)據(jù)，設(shè)計最優(yōu)的hash函數(shù)。
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2008-03-05 08:56 by
上面的語句外面都是foreach(ch in str){}。
hash表的數(shù)量 應(yīng)該不是影響hash的因素吧 想不出來原因。貌似一般都把hash表的桶數(shù)量設(shè)置的很大，是實際使用到的3倍多。
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2008-03-05 17:11 by
說的有一些道理，感覺hash表的大小還是要根據(jù)實際情況來選取。
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2008-04-18 15:12 by
有理， 對于mod的方法，確實與素數(shù)無關(guān)。
大于mod值的所謂信息只能“丟失”，只保留小于mod值的那些“位”。
要降低這個影響，在散列函數(shù)的計算過程中，這些低位所代表的信息也要能體現(xiàn)輸入。比如對于字符串的散列函數(shù)， 最好能夠把高位的字符串折回到低位去，這樣即使取余，也會保證均勻性，只不過，有一個元素對于桶的密度會增大。
能力有限， 太形式化的描述，不會。
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2008-08-18 19:46 by
關(guān)于這個，我也認(rèn)為和2的冪數(shù)無關(guān)。但是這可能跟哈希函數(shù)的設(shè)計有關(guān)，怎么說呢，很多哈希函數(shù)的設(shè)計本身是根據(jù)二進(jìn)制進(jìn)行的，所以《算法導(dǎo)論》才會得出丟失信息的結(jié)論。
不過最好還是用大數(shù)據(jù)測試比較下。
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2008-10-19 18:23 by
哎，樓主的思維還不夠嚴(yán)謹(jǐn)……
“如果計算機(jī)采用十進(jìn)制，那哈希表的容量是10^n的話豈不是很糟？”
給1234，容量是10，求余得4，僅由最后一位得出，前面的數(shù)直接被無視了，而對9求余就不是這樣了。
“不光是我，Java開發(fā)小組的人也不認(rèn)同。”
你知道他們用的散列函數(shù)僅僅是求余？他們二者的思想沒有矛盾，是你糾結(jié)的這個矛盾。
樓主的質(zhì)疑態(tài)度還是很好的。
歡迎批評我：phoenix.0220@gmail.com
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2009-03-25 16:33 by
正好看到《算法導(dǎo)論》中的hash table部分
我想《算法導(dǎo)論》中說表的大小不應(yīng)為2的整數(shù)次方，應(yīng)該是有針對性的，不是普遍的規(guī)律。
# re: 關(guān)于哈希表——一個常見的謬誤[未登錄] 回復(fù) 更多評論
2010-08-05 14:12 by
一個理想的HASH函數(shù)，輸出的值的每一位都“散列”的，無所謂丟失哪一部分來適應(yīng)“桶”的大小
# re: 關(guān)于哈希表——一個常見的謬誤[未登錄] 回復(fù) 更多評論
2013-01-25 16:08 by
使用質(zhì)數(shù)是有意義的, 雖然準(zhǔn)確的證明我不會(我也沒看到哪里有證明),
但是可以簡單說明一下.
用最簡單的hash函數(shù) h(k) = k mod m來說明.
對于任意的k1, k2,
假設(shè)事件A為k1 mod m == k2 mod m, 即k1, k2產(chǎn)生沖突的概率為p(A).
事件B_i為k1 mod m取得某個余數(shù)i, p(B_i) = 1/m,
事件C_j為k2 mod m取得某個余數(shù)j, p(C_j) = 1/m,
1. 如果m為質(zhì)數(shù):
由于k1, k2是任意選取的, 所以事件B_i和C_j是相互獨立的,
p(A) = p(B_x) * p(C_x) = 1/(m^2)
2. 如果m不為質(zhì)數(shù):
這時m可以寫成m = a * b, (a, b不等于1或m)
假設(shè)事件D為k1和k2具有公因數(shù)a(或b), 概率為p(D),
(用~D表示D不發(fā)生, 即k1,k2互質(zhì))
* 這里p(D)我不會求, 不好意思, 不過概率論里面有, 結(jié)果是6/(pi^2) *
1) 那么, 如果在D不發(fā)生的情況下, 概率和1是一樣的,
即p(A|~D) = 1/(m^2)
2) 如果D發(fā)生, 假設(shè)k1 = c1 * a, k2 = c2 * a,
事件A可轉(zhuǎn)化為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)
綜上所述, 當(dāng)m為質(zhì)數(shù)時, 事件A即產(chǎn)生碰撞的概率比m不為質(zhì)數(shù)時要小.
推廣到任意選取多個數(shù)的情況下也是成立的.
有些人可能會覺得對于任意的m, k mod m都能取到[0, m-1]的數(shù)的概率是
一樣的, 這確實沒錯. 但我們關(guān)注的問題是如何減少碰撞.
# re: 關(guān)于哈希表——一個常見的謬誤[未登錄] 回復(fù) 更多評論
2013-01-25 16:54 by
不好意思， 上面關(guān)于p(D)的說明不太正確，改為
“
假設(shè)事件D為k1, k2, m具有公因數(shù)(a或b, 假設(shè)為a), 概率為p(D), (用~D表示D不發(fā)生)
* 這里p(D)我不會求, 不好意思, 不過兩個數(shù)互質(zhì)的概率是6/(pi^2) *
”
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2013-03-02 01:13 by
上面的證明我覺得有問題，
2) 如果D發(fā)生, 假設(shè)k1 = c1 * a, k2 = c2 * a,
事件A可轉(zhuǎn)化為c1 mod b == c2 mod b,
這一步隱含的內(nèi)容是：
(c1*a) mod (a*b) = c1 mod b
但是同余并不具有可除性 這個等式是不成立的 因此這一步我認(rèn)為是錯了
例如k1=2*7=14,k2=5*7=35
即 c1=2,c2=5,b=u7
c1,c2在模b環(huán)境下并不同余
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2014-02-23 23:11 by
沒看過算法導(dǎo)論，不過我的理解是否均勻，要看 x 的特征，以及選取的算法。
對于,實際應(yīng)用中, 基于內(nèi)存地址來做HASH的話，可以標(biāo)志內(nèi)存的某一塊數(shù)據(jù)（OOP可以是堆中分配的對象的地址)。在這種情況下由于很多實際的機(jī)器實現(xiàn)的地址的對齊方式,分配的內(nèi)存地址都是2的倍數(shù)。在這種情況下hash(address) = (address)MOD M,
你想想如果M=2*x的話， 分布情況會是怎么樣？
# re: 關(guān)于哈希表——一個常見的謬誤 回復(fù) 更多評論
2014-03-25 16:13 by
算法導(dǎo)論說的是正確的！
樓主說“，因為x是在自然數(shù)集合里任選的，當(dāng)選取的次數(shù)非常多時，x mod M的結(jié)果應(yīng)該是平均分布在[0,M-1]中”。那么如果存在這樣一個集合，它的元素的低位嚴(yán)重偏斜到某幾個值，x對M=2^n取余后，剩下的低位值決定元素在哈希表中的位置，而低位會聚集在某些值上，導(dǎo)致哈希表嚴(yán)重沖突。