1)沖突是如何產(chǎn)生的？

　　上文中談到，哈希函數(shù)是指如何對關(guān)鍵字進(jìn)行編址的規(guī)則，這里的關(guān)鍵字的范圍很廣，可視為無限集，如何保證無限集的原數(shù)據(jù)在編址的時(shí)候不會出現(xiàn)重復(fù)呢？規(guī)則本身無法實(shí)現(xiàn)這個(gè)目的。舉一個(gè)例子，仍然用班級同學(xué)做比喻，現(xiàn)有如下同學(xué)數(shù)據(jù)
張三，李四，王五，趙剛，吳露.....
假如我們編址規(guī)則為取姓氏中姓的開頭字母在字母表的相對位置作為地址，則會產(chǎn)生如下的哈希表

...

...

我們注意到，灰色背景標(biāo)示的兩行里面，關(guān)鍵字王五，吳露被編到了同一個(gè)位置，關(guān)鍵字張三，趙剛也被編到了同一個(gè)位置。老師再拿號來找張三，座位上有兩個(gè)人，"你們倆誰是張三？"

2)如何解決沖突問題

既然不能避免沖突，那么如何解決沖突呢，顯然需要附加的步驟。通過這些步驟，以制定更多的規(guī)則來管理關(guān)鍵字集合，通常的辦法有:

a)開放地址法

開放地執(zhí)法有一個(gè)公式:Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中，m為哈希表的表長。di 是產(chǎn)生沖突的時(shí)候的增量序列。如果di值可能為1,2,3,...m-1，稱線性探測再散列。
如果di取1，則每次沖突之后，向后移動1個(gè)位置.如果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í)，使用第二個(gè)、第三個(gè)、哈希函數(shù)計(jì)算地址，直到無沖突時(shí)。缺點(diǎn)：計(jì)算時(shí)間增加。
比如上面第一次按照姓首字母進(jìn)行哈希，如果產(chǎn)生沖突可以按照姓字母首字母第二位進(jìn)行哈希，再沖突，第三位，直到不沖突為止

c)鏈地址法

將所有關(guān)鍵字為同義詞的記錄存儲在同一線性鏈表中。如下：

因此這種方法，可以近似的認(rèn)為是筒子里面套筒子

d)建立一個(gè)公共溢出區(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)，最后，我將詳細(xì)的闡述一下gif文件是如何構(gòu)成的，如何高效操作此種類型文件。

以上就是本文的全部內(nèi)容，希望能給大家一個(gè)參考，也希望大家多多支持腳本之家。

最新評論