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

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

...

...

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

2)如何解決沖突問(wèn)題

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

a)開放地址法

開放地執(zhí)法有一個(gè)公式:Hi=(H(key)+di) MOD m i=1,2,...,k(k<=m-1)
其中，m為哈希表的表長(zhǎng)。di 是產(chǎn)生沖突的時(shí)候的增量序列。如果di值可能為1,2,3,...m-1，稱線性探測(cè)再散列。
如果di取1，則每次沖突之后，向后移動(dòng)1個(gè)位置.如果di取值可能為1,-1,2,-2,4,-4,9,-9,16,-16,...k*k,-k*k(k<=m/2)
稱二次探測(cè)再散列。如果di取值可能為偽隨機(jī)數(shù)列。稱偽隨機(jī)探測(cè)再散列。仍然以學(xué)生排號(hào)作為例子，
現(xiàn)有兩名同學(xué)，李四，吳用。李四與吳用事先已排好序，現(xiàn)新來(lái)一名同學(xué)，名字叫王五，對(duì)它進(jìn)行編制

b)再哈希法

當(dāng)發(fā)生沖突時(shí)，使用第二個(gè)、第三個(gè)、哈希函數(shù)計(jì)算地址，直到無(wú)沖突時(shí)。缺點(diǎn)：計(jì)算時(shí)間增加。
比如上面第一次按照姓首字母進(jìn)行哈希，如果產(chǎn)生沖突可以按照姓字母首字母第二位進(jìn)行哈希，再?zèng)_突，第三位，直到不沖突為止

c)鏈地址法

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

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

d)建立一個(gè)公共溢出區(qū)

假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲(chǔ)空間向量OverTable[0..v]用以存儲(chǔ)發(fā)生沖突的記錄。
經(jīng)過(guò)以上方法，基本可以解決掉hash算法沖突的問(wèn)題。

注:之所以會(huì)簡(jiǎn)單得介紹了hash，是為了更好的學(xué)習(xí)lzw算法，學(xué)習(xí)lzw算法是為了更好的研究gif文件結(jié)構(gòu)，最后，我將詳細(xì)的闡述一下gif文件是如何構(gòu)成的，如何高效操作此種類型文件。

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

最新評(píng)論