Java之解決散列表的沖突用開放定址法和鏈表法

1 問題

理想狀態(tài)下，散列表就是一個包含關(guān)鍵字的固定大小的數(shù)組，通過使用散列函數(shù)，將關(guān)鍵字映射到數(shù)組的不同位置，哈希函數(shù)可以將關(guān)鍵字均勻的分散到數(shù)組的不同位置，不會出現(xiàn)兩個關(guān)鍵字散列值相同（假設(shè)關(guān)鍵字數(shù)量小于數(shù)組的大?。┑那闆r。但是在實際使用中，經(jīng)常會出現(xiàn)多個關(guān)鍵字散列值相同的情況（被映射到數(shù)組的同一個位置），我們將這種情況稱為散列沖突。為了解決散列沖突，主要采用下如下兩種方式：

 
2 鏈表法

分散鏈表法使用鏈表解決沖突，將散列值相同的元素都保存到一個鏈表中。當查詢的時候，首先找到元素所在的鏈表，然后遍歷鏈表查找對應(yīng)的元素。下面是一個示意圖：

 


3 開放定址法

在散列算法得到一個存儲地址之后，如果發(fā)生沖突，不是在原處創(chuàng)建一個鏈表而是按照一定規(guī)則尋找周圍可用的地址進行插入。

這個規(guī)則我么可以是線性探測法、平方探測法、
1）線性探測法

線性探測法中，函數(shù)ff是ii的函數(shù)，記為：f(i)=i （i為尋址次數(shù)）這相當于相繼探測每個單元。例子：我們在M=10點散列表中，按順序插入下列數(shù)字{89，18，49，58，69}

按照散列方式(這里直接對數(shù)組大小取余)，在插入89和18時，直接插入到散列位置9和位置8。但是插入第三個數(shù)49時，散列位置為9，跟已有89沖突，于是開始線性探測，即按照順序?qū)ふ蚁乱粋€位置。i=1時，探測位置為散列位置M+i，即探測位置0，位置0無沖突，49存入位置0。插入第四個樹58時，散列位置M=8，但是位置8已經(jīng)存在18，發(fā)生沖突開始線性探測，i=1時，探測位置為散列位置M+i，位置9已有89存在發(fā)生沖突，i=2時，探測位置為0，位置0已有49存在，發(fā)生沖突，i=3時，探測位置1，位置1無沖突，58存入位置1。同理，69在探測到第3次后，存入位置2。

 
2）平方探測法

在線性探測法中，函數(shù)f是i的函數(shù)，記為：f(i)=i 。而在平方探測法中，我們通常使用的是f(i)=i^2 。還是上面的例子，我們利用平方探測法插入{89，18，49，58，69}

按照散列方式，在插入89和18時，直接插入到散列位置9和位置8。但是插入第三個數(shù)49時，散列位置為9，跟已有89沖突，于是開始平方探測，第一次探測i=1,f(i)=i^2=1,所以我們探測位置為位置0（位置9+1）。發(fā)現(xiàn)位置0不沖突，那么在位置0插入49。插入第四個數(shù)58時，散列位置8，跟已有18沖突，開始平方探測，第一次探測i=1,f(i)=i^2=1探測位置9（位置8+1），發(fā)生沖突,第二次探測i=2,f(i)=i^2=4，探測位置2（位置8+4），位置2不沖突，在位置2插入58

 
4 兩種辦法對比總結(jié)
1) 、鏈表法

的缺點是使用鏈表。在新單元分配地址需要時間，不同的語言需要的時間不一致，這會導致算法的速度有些減慢。鏈表法也是固定定址的一種，它處理沖突簡單，且無堆積現(xiàn)象，平均查找長度短；鏈表中的結(jié)點是動態(tài)申請的，適合構(gòu)造表不能確定長度的情況；相對而言，拉鏈法的指針域可以忽略不計，因此較開放地址法更加節(jié)省空間。插入結(jié)點應(yīng)該在鏈首，刪除結(jié)點比較方便，只需調(diào)整指針而不需要對其他沖突元素作調(diào)整。

hashmap解決沖突用的是鏈表法。

 
2) 、開放定址法

容易產(chǎn)生堆積問題；不適于大規(guī)模的數(shù)據(jù)存儲；散列函數(shù)的設(shè)計對沖突會有很大的影響；插入時可能會出現(xiàn)多次沖突的現(xiàn)象，刪除的元素是多個沖突元素中的一個，需要對后面的元素作處理，實現(xiàn)較復(fù)雜；結(jié)點規(guī)模很大時會浪費很多空間
 



 作者：chen.yu
深信服三年半工作經(jīng)驗，目前就職游戲廠商，希望能和大家交流和學習,
微信公眾號：編程入門到禿頭 或掃描下面二維碼
零基礎(chǔ)入門進階人工智能(鏈接)