[資料結構] Hash表、Hash函數及沖突解決１.Hash表 2.哈希表的構造方法 ３.哈希表沖突解決方法

　　以資料中每個元素的關鍵字k為自變量，通過散列函數h（k）計算出函數值，以該函數值作為一塊連續存儲空間的的單元位址，将該元素存儲到函數值對應的單元中。

　　哈希表存儲的是鍵值對，其查找的時間複雜度與元素數量多少無關，哈希表在查找元素時是通過計算哈希碼值來定位元素的位置進而直接通路元素的，是以，哈希表查找的時間複雜度為o（1）。

　　取關鍵字或者關鍵字的某個線性函數值作為哈希位址,即　 

h(key)=key或者h(key)=a*key+b(a,b為整數)　 

這種散列函數也叫做自身函數.如果h(key)的哈希位址上已經有值了,那麼就往下一個位置找,直到找到h(key)的位置沒有值了就把元素放進去.　 

此法僅适合于：位址集合的大小 等于 關鍵字集合的大小

　　分析一組資料,比如一組員工的出生年月,這時我們發現出生年月的前幾位數字一般都相同,是以,出現沖突的機率就會很大,但是我們發現年月日的後幾位表示月份和具體日期的數字差别很大,如果利用後面的幾位數字來構造散列位址,則沖突的幾率則會明顯降低. 

是以數字分析法就是找出數字的規律,盡可能利用這些資料來構造沖突幾率較低的散列位址.　　 

此法适于:能預先估計出全體關鍵字的每一位上各種數字出現的頻度。

　　以關鍵字的平方值的中間幾位作為存儲位址（哈希位址）。求“關鍵字的平方值” 的目的是“擴大差别” ，同時平方值的中間各位又能受到整個關鍵字中各位的影響。　

　　此法适于:關鍵字中的每一位都有某些數字重複出現頻度很高的現象。

　　 将關鍵字分割成若幹部分，然後取它們的疊加和為哈希位址。兩種疊加處理的方法：移位疊加:将分 割後的幾部分低位對齊相加；間界疊加:從一端沿分割界來回折疊，然後對齊相加。 

此法适于：關鍵字的數字位數特别多。　

　　設定哈希函數為:h(key) = random(key)其中，random 為僞随機函數 

此法适于：對長度不等的關鍵字構造哈希函數。

　　取關鍵字被某個不大于散清單表長m的數p除後所得的餘數為散列位址.即 

哈希函數為:h(key) = key mod p ( p≤m )，其中， m為表長，p 為不大于 m 的素數。

　　哈希表處理沖突主要有開放尋址法、再散列法、鍊位址法（拉鍊法）和建立一個公共溢出區四種方法。 

通過構造性能良好的哈希函數，可以減少沖突，但一般不可能完全避免沖突，是以解決沖突是哈希法的另一個關鍵問題。 

“處理沖突” 的實際含義是：為産生沖突的關鍵字尋找下一個哈希位址。

　　 

一旦發生了沖突，就去尋找下一個空的散列位址，隻要散清單足夠大，空的散列位址總能找到，并将記錄存入。

　　沖突發生時，順序檢視表中下一單元，直到找出一個空單元或查遍全表。

　　公式： 

　　沖突發生時，在表的左右進行跳躍式探測，雙向尋找到可能的空位置。

公式：

　　在沖突時，對于位移量 di 采用随機函數計算得到，我們稱之為随機探測法。

　公式： 

　　線性探測再散列容易産生“二次聚集”，即在處理同義詞的沖突時又導緻非同義詞的沖突。 

線性探測再散列的優點是：隻要哈希表不滿，就一定能找到一個不沖突的哈希位址，而二次探測再散列和僞随機探測再散列則不一定。

　　 将所有哈希位址相同的記錄都連結在同一連結清單中。各連結清單上的結點空間是動态申請的，故它更适合于造表前無法确定表長的情況。 

處理沖突簡單，且無堆積現象，即非同義詞決不會發生沖突，是以平均查找長度較短；

這種方法是同時構造多個不同的哈希函數：

當哈希位址hi=rh1（key）發生沖突時，再計算hi=rh2（key）……，直到沖突不再産生。這種方法不易産生聚集，但增加了計算時間。

　　這種方法的基本思想是：将哈希表分為基本表和溢出表兩部分，凡是和基本表發生沖突的元素，一律填入溢出表.(注意：在這個方法裡面是把元素分開兩個表來存儲)

版權聲明：請尊重個人勞動成果，轉載注明出處，謝謝！

http://blog.csdn.net/amazing7/article/details/51364667