解決散列沖突的方法有哪些

A. 散列查找的處理沖突的方法

思路：從發生沖突的那個單元開始，按照一定次序，從散列表中查找出一個空閑的存儲單元，把發生沖突的待插入元素存入到該單元的一類處理沖突的方法。
在使用該方法處理沖突的散列表中，查找一個元素的過程是：先根據給定關鍵字K，利用與插入時使用的同一散列函數h(K)計算出散列地址(設下標為d),然後用K同d單元的關鍵字比較，若相等則查找成功，否則按插入時處理沖突的相同次序，依次用K同所查單元的關鍵字比較，直到查找成功或查找到一空單元(表明查找失敗)為止。
有三種常見的開放定址法
（1）線性探查法
是用開放定址法處理沖突的一種最簡單的探查方法。
從發生沖突的d單元起,依次探查下一個單元,直到碰到一個空閑單元或探查完所有單元為止探查時,當達到下標為m-1的表尾單元時,下一個探查的單元是下標為0的表首單元。
探查序列為d,d+1,d+2……，表示為(d+i)%m (0≤i≤m-1)。
例如：構取m=13,線性表為A=(18,75,60,43,54,90,46)，構造的散列表如下： 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 46 60 75 90 現向表中再插入關鍵字為31和58的兩個元素,用線性探查法解決沖突。
先插入31，h(31)=31%13=5,因H[5]被佔用，探查下一個即下標為6的單元，空閑，插入31。 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 31 46 60 75 90 再插入58，h(58)=58%13=6,因H[6]被佔用，探查下一個即下標為7的單元，因H[7]仍不空閑，再接著向下探查，當探查到下標為9的單元時，空閑，插入58。 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 31 46 60 58 75 90 利用線性探查法處理沖突易造成元素的「堆積」(聚集) 0 1 2 3 4 5 6 7 8 9 10 11 12 H 54 43 18 46 60 75 90 向散列表中插入一個元素：
int Insert (hashlist1 HT,int m,ElemType item)
{
//向長度為m的散列表HT中插入一個元素
int d=H(item.key,m); //可選一種合適的構造散列函數的方法，計算散列地址
int temp=d;
while(HT[d].key != NullTag)
{
//當d單元不空時繼續向後查找空位置
d=(d+1)%m;
if(d==temp) return 0;
}
HT[d]=item; //將新元素插入到下標為d的位置
return 1;
}
從散列表中查找一個元素：
int Search (hashlist1 HT,int m, ElemType item)
{
//從長度為m的散列表HT中查找
int d=H(item.key, m);
int temp=d;
while(HT[d].key!=NullTag)
{
//當散列地址中的關鍵字域不為空則循環
if(HT[d].key==item.key) return d;
else d=(d+1)%m;
if(d==temp) return -1;
}
return -1;
}
（2）平方探查法
探查序列為d,d+1,d+2……,表示為(d+i2)%m(0≤i≤m-1)。遞推公式為：
優點：它是一種較好的處理沖突的方法，可以較好避免堆積現象
缺點：不能探查到散列表上所有單元。
例：當d0=5,m=17時，只能探查到下標依次為5、6、9、14、4、13、7、3、1的單元。
d0=5;
d1=(5 +2*1-1)%17=6; d2=(6 +2*2-1)%17=9;
d3=(9 +2*3-1)%17=14; d4=(14 +2*4-1)%17=4;
d5=(4 +2*5-1)%17=13; d6=(13 +2*6-1)%17=7;
d7=(7 +2*7-1)%17=3; d8=(3 +2*8-1)%17=1; d9=(1 +2*9-1)%17=1;
（3）雙散列函數探查法
思路：
該方法使用兩個散列函數h1和h2，其中h1和前面的h(K)一樣，以關鍵字為自變數，產生一個0～m-1之間的數作散列地址;h2也以關鍵字為自變數，產生一個1～m-1之間的、並和m互素的數作散列地址。它的探查序列為：
利用雙散列法，按一定的距離，跳躍式地尋找「下一個」桶，減少了「堆積」的機會，最多經過m-1次探查，它會遍歷表中所有位置，回到H0 位置。
例：給出一組表項關鍵碼{22,41,53,46,30,13,01,67}。散列表為HT[0..10]，m = 11。
散列函數為：
Hash(x)=(3x) % 11
再散列函數為：
ReHash(x) = (7x) % 10 +1
Hi = ( Hi-1 + (7x) % 10 +1 ) % 11, i = 1, 2,
H0(22) = 0 H0(41) = 2 H0(53) = 5 H0(46) = 6
H0(30) = 2 沖突H1 = (2+1) = 3 ,H0(13) = 6 沖突H1 = (6+2) = 8
H0(01) = 3 沖突H1 = (3+8) = 0 ,H2 = (0+8) = 8 H3 = (8+8) = 5
H4 =(5+8)=2 H5 =(2+8)=10,H0(67)=3 沖突, H1 = (3+10) = 2 H2 = (2+10) = 1
搜索成功的平均搜索長度：
鏈接法
思路：就是把發生沖突的同義詞元素(結點)用單鏈表鏈接起來的方法。
例：假定一個線性表B為：B=(18,75,60,43,54,90,46,31,58,73,15,34)。
設採用的散列函數為h(K)=K%13,採用鏈接法處理：
在該例中，查找成功時平均查找長度為：
ASL=(8×1+3×2+1×3)/12≈1.42
若線性探查法處理沖突進行散列存儲，得到：
查找成功時平均查找長度為：
ASL=(7×1+1×2+1×4+1×4+1×2+1×6)/12≈2.1
多種方法分析
在散列表的插入和查找演算法中，平均查找長度與表的大小m無關，只與選取的散列函數、α值和處理沖突的方法有關,若假定所選取的散列函數能夠使任一關鍵字等概率地映射到散列空間的任一地址上，理論上證明：
當採用線性探查法處理沖突時，ASL=
當採用鏈地址法處理沖突時，ASL=
當採用平方探查法、雙散列函數法處理沖突時，ASL=
散列存儲優缺點
插入與查找的速度相當快根據關鍵字計算散列地址需要開銷一定計算時間佔用存儲空間較多在散列表中只能按關鍵字查找元素線性表中元素的邏輯關系無法在散列表中體現。 鏈表地址法為散列表的每個表象建立一個單鏈表，用於鏈接同義詞表，為此需要給每個表項增加一個指針域。
關於同義詞表的建立，有兩種方法。一種方法是在散列表的基本存儲區域外開辟一個新的區域用於存儲同義詞表，這種方法稱為「分離的同義詞子表法」，或稱「獨立鏈表地址法」，這個分離的同義詞子表所在的區域稱為「溢出區」。另一種方法是不建立溢出區，而是將同義詞子表存儲在散列表所在的基本存儲區域里，例如，可以再基本存儲區域里從後向前探測空閑表項，找到後就將其鏈接到同義詞子表中，這個方法稱為「結合的同義詞子表法」，或稱為「公共鏈表地址法」。
獨立鏈表地址法是查找效率最好的解決沖突的方法，速度要快於開放地址法，因為獨立鏈表地址法在進行散列查找時僅需搜索同義詞表。開放地址法要求表長時固定的，而地理鏈表法中的表項則是動態分配的，其表長僅受內存空間的限制。鏈表法的主要缺點是需要為每個表項（包括分離的同義子表的每個節點）設立一個指針域。
總之，獨立鏈表地址法的動態結構使它成為散列法中解決沖突的首選方法。

B. 線性探測再散列技術是如何解決沖突的

線性探測再散列也稱雜湊技術。是一種較快的查找技術。

線性探測再散列是哈希表解決沖突的一種計算方法，Hi=(H(key)+di)%m，i=1,2,……k(k<=m-1)，H(key)哈希函數，m哈希表長，di增量序列當，di值可能為1,2,3,...m-1，稱線性探測再散列，用該方法處理沖突的方法：開放定址法、再散列法和鏈地址法（拉鏈法）。

解決沖突的方法一般有線性探測再散列法、隨機探測法、再哈希法、鏈地址法等，其中線性再散列法較簡單，其計算公式為：Hi＝（H（K）+di）MOD p式中di＝1，2，…

常用的哈希函數

1.直接定址法。僅適合於：地址集合的大小 == 關鍵字集合的大小。

2.數字分析法。對關鍵字進行分析，取關鍵字的若干位或其組合作哈希地址。僅適合於：能預先估計出全體關鍵字的每一位上各種數字出現的頻度。

3.平方取中法。以關鍵字的平方值的中間幾位作為存儲地址。

4.折疊法。將關鍵字分割成位數相同的幾部分，然後取這幾部分的疊加和(捨去進位)做哈希地址。移位疊加/間界疊加。適合於: 關鍵字的數字位數特別多，且每一位上數字分布大致均勻情況。

5.除留余數法。取關鍵字被某個不大於哈希表表長m的數p除後所得余數作哈希地址，即H(key)=key%p，p<=m。

6.隨機數法。取關鍵字的偽隨機函數值作哈希地址，即H(key)=random(key)，適於關鍵字長度不等的情況。

以上內容參考：線性探測再散列-學術網路-知網空間