|
1)沖突是如何產(chǎn)生的？ 上文中談到，哈希函數(shù)是指如何對關(guān)鍵字進(jìn)行編址的規(guī)則，這里的關(guān)鍵字的范圍很廣，可視為無限集，如何保證無限集的原數(shù)據(jù)在編址的時候不會出現(xiàn)重復(fù)呢？規(guī)則本身無法實(shí)現(xiàn)這個目的。舉一個例子，仍然用班級同學(xué)做比喻，現(xiàn)有如下同學(xué)數(shù)據(jù) 張三，李四，王五，趙剛，吳露..... 假如我們編址規(guī)則為取姓氏中姓的開頭字母在字母表的相對位置作為地址，則會產(chǎn)生如下的哈希表
...
我們注意到，灰色背景標(biāo)示的兩行里面，關(guān)鍵字王五，吳露被編到了同一個位置，關(guān)鍵字張三，趙剛也被編到了同一個位置。老師再拿號來找張三，座位上有兩個人，"你們倆誰是張三？" 2)如何解決沖突問題 既然不能避免沖突，那么如何解決沖突呢，顯然需要附加的步驟。通過這些步驟，以制定更多的規(guī)則來管理關(guān)鍵字集合，通常的辦法有: a)開放地址法 開放地執(zhí)法有一個公式:Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1) 其中，m為哈希表的表長。di 是產(chǎn)生沖突的時候的增量序列。如果di值可能為1,2,3,...m-1，稱線性探測再散列。 如果di取1，則每次沖突之后，向后移動1個位置.如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2) 稱二次探測再散列。如果di取值可能為偽隨機(jī)數(shù)列。稱偽隨機(jī)探測再散列。仍然以學(xué)生排號作為例子， 現(xiàn)有兩名同學(xué)，李四，吳用。李四與吳用事先已排好序，現(xiàn)新來一名同學(xué)，名字叫王五，對它進(jìn)行編制
b)再哈希法 當(dāng)發(fā)生沖突時，使用第二個、第三個、哈希函數(shù)計(jì)算地址，直到無沖突時。缺點(diǎn)：計(jì)算時間增加。 比如上面第一次按照姓首字母進(jìn)行哈希，如果產(chǎn)生沖突可以按照姓字母首字母第二位進(jìn)行哈希，再沖突，第三位，直到不沖突為止 c)鏈地址法 將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。如下：  因此這種方法，可以近似的認(rèn)為是筒子里面套筒子 d.建立一個公共溢出區(qū) 假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲空間向量OverTable[0..v]用以存儲發(fā)生沖突的記錄。 經(jīng)過以上方法，基本可以解決掉hash算法沖突的問題。 注:之所以會簡單得介紹了hash，是為了更好的學(xué)習(xí)lzw算法，學(xué)習(xí)lzw算法是為了更好的研究gif文件結(jié)構(gòu) TPLINK:http://hi.baidu.com/gezhou/blog/item/74e2b034415edcb6d1a2d3e0.html |
|
|
