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