1 問題

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

?

?

?

2 鏈表法

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

?

?

?

3?開放定址法

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

這個規則我么可以是線性探測法、平方探測法、

1）線性探測法

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

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

?

?

?

2）平方探測法

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

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

?

?

4 兩種辦法對比總結

1) 、鏈表法

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

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

?

2) 、開放定址法

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