一、什么是hash沖突？

假設(shè)hash表的大小為9（即有9個槽），現(xiàn)在要把一串?dāng)?shù)據(jù)存到表里：5,28,19,15,20,33,12,17,10

簡單計算一下：hash(5)=5, 所以數(shù)據(jù)5應(yīng)該放在hash表的第5個槽里；hash(28)=1，所以數(shù)據(jù)28應(yīng)該放在hash表的第1個槽里；hash(19)=1，也就是說，數(shù)據(jù)19也應(yīng)該放在hash表的第1個槽里——于是就造成了碰撞（也稱為沖突，collision）。

二、Hash沖突解決方法：

1.開放定址法(再散列法)：?

基本思想：當(dāng)關(guān)鍵字key的哈希地址p=H（key）出現(xiàn)沖突時，以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p1，如果p1仍然沖突，再以p為基礎(chǔ)，產(chǎn)生另一個哈希地址p2，…， ? ? ? ? ? ? ? ? ? ? ? ? ? ?直到找出一個不沖突的哈希地址pi ，將相應(yīng)元素存入其中。

這種方法有一個通用的再散列函數(shù)形式：

Hi=（H（key）+di）% m ? i=1，2，…，n

其中H（key）為哈希函數(shù)，m 為表長，di稱為增量序列。增量序列的取值方式不同，相應(yīng)的再散列方式也不同。

(1).線性探測再散列：

dii=1，2，3，…，m-1

沖突發(fā)生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。

(2).二次探測再散列：?

di=12，-12，22，-22，…，k2，-k2 ? ?( k<=m/2 )

沖突發(fā)生時，在表的左右進行跳躍式探測，比較靈活。

(3).偽隨機探測再散列：?

di=偽隨機數(shù)序列。

具體實現(xiàn)時，應(yīng)建立一個偽隨機數(shù)發(fā)生器，（如i=(i+p) % m），并給定一個隨機數(shù)做起點。

4.? 示例：

?已知哈希表長度m=11，哈希函數(shù)為：H（key）= key ?% ?11，則H（47）=3，H（26）=4，H（60）=5，假設(shè)下一個關(guān)鍵字為69，則H（69）=3，與47沖突。

a):?如果用線性探測再散列處理沖突，下一個哈希地址為H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 + 2）% 11 = 5，還是沖突，

? ? ? ? ? ? ? ?繼續(xù)找下一個哈希地址為H3=（3 + 3）% 11 = 6，此時不再沖突，將69填入5號單元。

0 ? ? 1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? ? 7 ? ? 8 ? ? 9 ? ? 10

47 ? 26 ? 60 ? 69

b):?如果用二次探測再散列處理沖突，下一個哈希地址為H1=（3 + 12）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 - 12）% 11 = 2，此時不再沖突，

? ? ? ? ? ? ? ?將69填入2號單元。

0 ? ? 1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? ? 7 ? ? 8 ? ? 9 ? ? 10

69?? 47 ? 26 ?60

c):?如果用偽隨機探測再散列處理沖突，且偽隨機數(shù)序列為：2，5，9，……..，則下一個哈希地址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希地址

? ? ? ? ? ? ? ?為H2=（3 + 5）% 11 = 8，此時不再沖突，將69填入8號單元。

0 ? ? 1 ? ? 2 ? ? 3 ? ? 4 ? ? 5 ? ? 6 ? ? 7 ? ? 8 ? ? 9 ? ? 10

47 ? 26 ?60 ? ? ? ? ? ? ? ? ?69

2.再哈希法

這種方法是同時構(gòu)造多個不同的哈希函數(shù)：

Hi=RH1（key） i=1，2，…，k

當(dāng)哈希地址Hi=RH1（key）發(fā)生沖突時，再計算Hi=RH2（key）……，直到?jīng)_突不再產(chǎn)生。這種方法不易產(chǎn)生聚集，但增加了計算時間。

3.鏈地址法 (HashMap的沖突處理方式)

這種方法的基本思想是將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除主要在同義詞鏈中進行。鏈地址法適用于經(jīng)常進行插入和刪除的情況。

4.建立公共溢出區(qū)

這種方法的基本思想是：將哈希表分為基本表和溢出表兩部分，凡是和基本表發(fā)生沖突的元素，一律填入溢出表。

三、拉鏈法與開放地址法相比的缺點：

拉鏈法優(yōu)點：

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

②由于拉鏈法中各鏈表上的結(jié)點空間是動態(tài)申請的，故它更適合于造表前無法確定表長的情況；

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

④在用拉鏈法構(gòu)造的散列表中，刪除結(jié)點的操作易于實現(xiàn)。只要簡單地刪去鏈表上相應(yīng)的結(jié)點即可。而對開放地址法構(gòu)造的散列表，刪除結(jié)點不能簡單地將被刪結(jié) 點的空間置為空，否則將截斷在它之后填人散列表的同義詞結(jié)點的查找路徑。這是因為各種開放地址法中，空地址單元(即開放地址)都是查找失敗的條件。因此在 用開放地址法處理沖突的散列表上執(zhí)行刪除操作，只能在被刪結(jié)點上做刪除標記，而不能真正刪除結(jié)點。

拉鏈法缺點：

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

四、不同處理沖突的平均查找長度

例：

假設(shè)散列表的長度是13，三列函數(shù)為H(K) = k % 13，給定的關(guān)鍵字序列為{32， 14， 23， 01， 42， 20， 45， 27， 55， 24， 10， 53}。分別畫出用線性探測法和拉鏈法解決沖突時構(gòu)造的哈希表，并求出在等概率情況下，這兩種方法的查找成功和查找不成功的平均查找長度。

（1）線性探測法：

查找成功時的查找次數(shù)等于插入元素時的比較次數(shù),查找成功的平均查找長度為：

ASL =?（1+2+1+4+3+1+1+3+9+1+1+3)/12 = 2.5

查找成功時的查找次數(shù)：第n個位置不成功時的比較次數(shù)為，第n個位置到第1個沒有數(shù)據(jù)位置的距離：如第0個位置取值為1，第1個位置取值為2.

查找不成功的平均查找次數(shù)為：

ASL =?（1+2+3+4+5+6+7+8+9+10+11+12）/ 13 = 91/13

（2）鏈地址法

查找成功時的平均查找長度：

ASL = (1*6+2*4+3*1+4*1)/12 = 7/4

查找不成功時的平均查找長度：

ASL = (4+2+2+1+2+1)/13

注意：查找成功時，分母為哈希表元素個數(shù)，查找不成功時，分母為哈希表長度。

https://blog.csdn.net/u011080472/article/details/51177412