解決Hash碰撞沖突方法總結(jié)

Hash碰撞沖突

我們知道，對(duì)象Hash的前提是實(shí)現(xiàn)equals()和hashCode()兩個(gè)方法，那么HashCode()的作用就是保證對(duì)象返回唯一hash值，但當(dāng)兩個(gè)對(duì)象計(jì)算值一樣時(shí)，這就發(fā)生了碰撞沖突。如下將介紹如何處理沖突，當(dāng)然其前提是一致性hash。

1.開(kāi)放地址法

開(kāi)放地執(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è)再散列。

2.再哈希法

當(dāng)發(fā)生沖突時(shí)，使用第二個(gè)、第三個(gè)、哈希函數(shù)計(jì)算地址，直到無(wú)沖突時(shí)。缺點(diǎn)：計(jì)算時(shí)間增加。

比如上面第一次按照姓首字母進(jìn)行哈希，如果產(chǎn)生沖突可以按照姓字母首字母第二位進(jìn)行哈希，再?zèng)_突，第三位，直到不沖突為止。

3.鏈地址法（拉鏈法）

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

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

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

假設(shè)哈希函數(shù)的值域?yàn)閇0,m-1],則設(shè)向量HashTable[0..m-1]為基本表，另外設(shè)立存儲(chǔ)空間向量OverTable[0..v]用以存儲(chǔ)發(fā)生沖突的記錄。

拉鏈法的優(yōu)缺點(diǎn)：

優(yōu)點(diǎn)：

①拉鏈法處理沖突簡(jiǎn)單，且無(wú)堆積現(xiàn)象，即非同義詞決不會(huì)發(fā)生沖突，因此平均查找長(zhǎng)度較短；

②由于拉鏈法中各鏈表上的結(jié)點(diǎn)空間是動(dòng)態(tài)申請(qǐng)的，故它更適合于造表前無(wú)法確定表長(zhǎng)的情況；

③開(kāi)放定址法為減少?zèng)_突，要求裝填因子α較小，故當(dāng)結(jié)點(diǎn)規(guī)模較大時(shí)會(huì)浪費(fèi)很多空間。而拉鏈法中可取α≥1，且結(jié)點(diǎn)較大時(shí)，拉鏈法中增加的指針域可忽略不計(jì)，因此節(jié)省空間；

④在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點(diǎn)的操作易于實(shí)現(xiàn)。只要簡(jiǎn)單地刪去鏈表上相應(yīng)的結(jié)點(diǎn)即可。而對(duì)開(kāi)放地址法構(gòu)造的散列表，刪除結(jié)點(diǎn)不能簡(jiǎn)單地將被刪結(jié) 點(diǎn)的空間置為空，否則將截?cái)嘣谒筇钊松⒘斜淼耐x詞結(jié)點(diǎn)的查找路徑。這是因?yàn)楦鞣N開(kāi)放地址法中，空地址單元(即開(kāi)放地址)都是查找失敗的條件。因此在 用開(kāi)放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點(diǎn)上做刪除標(biāo)記，而不能真正刪除結(jié)點(diǎn)。

缺點(diǎn)：

指針需要額外的空間，故當(dāng)結(jié)點(diǎn)規(guī)模較小時(shí)，開(kāi)放定址法較為節(jié)省空間，而若將節(jié)省的指針空間用來(lái)擴(kuò)大散列表的規(guī)模，可使裝填因子變小，這又減少了開(kāi)放定址法中的沖突，從而提高平均查找速度。

出處：blog.csdn.net/zeb_perfect/article/details/52574915

關(guān)注GitHub今日熱榜，專注挖掘好用的開(kāi)發(fā)工具，致力于分享優(yōu)質(zhì)高效的工具、資源、插件等，助力開(kāi)發(fā)者成長(zhǎng)！

點(diǎn)個(gè)在看 你最好看