================================================================================================

哈希表的概念

        哈希表(Hash Table)也叫散列表，是根據關鍵碼值（Key Value）而直接進行訪問的數據結構。它通過把關鍵碼值映射到哈希表中的一個位置來訪問記錄，以加快查找的速度。這個映射函數就做散列函數，存放記錄的數組叫做散列表。

散列存儲的基本思路

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

哈希表查找的時間復雜度

        哈希表存儲的是鍵值對，其查找的時間復雜度與元素數量多少無關，哈希表在查找元素時是通過計算哈希碼值來定位元素的位置從而直接訪問元素的，因此，哈希表查找的時間復雜度為O（1）。

哈希函數的構造方法

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

1.   直接尋址法

取關鍵字或者關鍵字的某個線性函數值作為哈希地址,即H(Key)=Key或者H(Key)=a*Key+b(a,b為整數),這種散列函數也叫做 自身函數.如果H(Key)的哈希地址上已經有值了,那么就往下一個位置找,知道找到H(Key)的位置沒有值了就把元素放進去.

2.   數字分析法

分析一組數據,比如一組員工的出生年月,這時我們發現出生年月的前幾位數字一般都相同,因此,出現沖突的概率就會很大,但是我們發現年月日的后幾位 表示月份和具體日期的數字差別很大,如果利用后面的幾位數字來構造散列地址,則沖突的幾率則會明顯降低.因此數字分析法就是找出數字的規律,盡可能利用這 些數據來構造沖突幾率較低的散列地址.

3.   平方取中法

取關鍵字平方后的中間幾位作為散列地址.

4.   折疊法

折疊法即將關鍵字分割成位數相同的幾部分,最后一部分位數可以不同,然后取這幾部分的疊加和(注意:疊加和時去除進位)作為散列地址.數位疊加可以有移位疊加和間界疊加兩種方法.移位疊加是將分割后的每一部分的最低位對齊,然后相加;間界疊加是從一端向另一端沿分割界來回折疊,然后對齊相加.

5.   隨機數法

選擇一個隨機數,去關鍵字的隨機值作為散列地址,通常用于關鍵字長度不同的場合.

6.   除留余數法

取關鍵字被某個不大于散列表表長m的數p除后所得的余數為散列地址.即H(Key)=Key MOD p,p<=m.不僅可以對關鍵字直接取模,也可在折疊、平方取中等運算之后取模。對p的選擇很重要，一般取素數或m，若p選得不好，則很容易產生沖突。

哈希表如何處理沖突

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

通過構造性能良好的哈希函數，可以減少沖突，但一般不可能完全避免沖突，因此解決沖突是哈希法的另一個關鍵問題。創建哈希表和查找哈希表都會遇到沖突，兩種情況下解決沖突的方法應該一致。下面以創建哈希表為例，說明解決沖突的方法。常用的解決沖突方法有以下四種：

1.開放定址法

這種方法也稱再散列法，其基本思想是：當關鍵字key的哈希地址p=H（key）出現沖突時，以p為基礎，產生另一個哈希地址p1，如果p1仍然沖 突，再以p為基礎，產生另一個哈希地址p2，…，直到找出一個不沖突的哈希地址pi ，將相應元素存入其中。這種方法有一個通用的再散列函數形式：Hi=(H(key)+di)%m   i=1，2，…，n,其中H（key）為哈希函數，m 為表長，di稱為增量序列。增量序列的取值方式不同，相應的再散列方式也不同。主要有以下三種：

(1) 線性探測再散列

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

這種方法的特點是：沖突發生時，順序查看表中下一單元，直到找出一個空單元或查遍全表。

(2)二次探測再散列

   di=1²，-1²，2²，-2²，…，k²，-k²    ( k<=m/2)

    這種方法的特點是：沖突發生時，在表的左右進行跳躍式探測，比較靈活。

(3)偽隨機探測再散列

    di=偽隨機數序列。

具體實現時，應建立一個偽隨機數發生器，（如i=(i+p) % m），并給定一個隨機數做起點。

例如，已知哈希表長度m=11，哈希函數為：H（key）= key  %  11，則H（47）=3，H（26）=4，H（60）=5，假設下一個關鍵字為69，則H（69）=3，與47沖突。如果用線性探測再散列處理沖突，下一 個哈希地址為H1=（3 + 1）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 + 2）% 11 = 5，還是沖突，繼續找下一個哈希地址為H3=（3 + 3）% 11 = 6，此時不再沖突，將69填入5號單元。如果用二次探測再散列處理沖突，下一個哈希地址為H1=（3 + 12）% 11 = 4，仍然沖突，再找下一個哈希地址為H2=（3 - 12）% 11 = 2，此時不再沖突，將69填入2號單元。如果用偽隨機探測再散列處理沖突，且偽隨機數序列為：2，5，9，……..，則下一個哈希地址為H1=（3 + 2）% 11 = 5，仍然沖突，再找下一個哈希地址為H2=（3 + 5）% 11 = 8，此時不再沖突，將69填入8號單元。

從上述例子可以看出，線性探測再散列容易產生“二次聚集”，即在處理同義詞的沖突時又導致非同義詞的沖突。例如，當表中i, i+1 ,i+2三個單元已滿時，下一個哈希地址為i, 或i+1 ,或i+2，或i+3的元素，都將填入i+3這同一個單元，而這四個元素并非同義詞。線性探測再散列的優點是：只要哈希表不滿，就一定能找到一個不沖突的哈希地址，而二次探測再散列和偽隨機探測再散列則不一定。

2.再哈希法

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

        H_i=RH₁（key），i=1，2,3，…,n.

        當哈希地址Hi=RH1（key）發生沖突時，再計算Hi=RH2（key）……，直到沖突不再產生。這種方法不易產生聚集，但增加了計算時間。

 3.鏈地址法

這種方法的基本思想是將所有哈希地址為i的元素構成一個稱為同義詞鏈的單鏈表，并將單鏈表的頭指針存在哈希表的第i個單元中，因而查找、插入和刪除 主要在同義詞鏈中進行。若選定的散列表長度為m，則可將散列表定義為一個由m個頭指針組成的指針數組T[0..m-1]。凡是散列地址為i的結點，均插入 到以T[i]為頭指針的單鏈表中。T中各分量的初值均應為空指針。鏈地址法適用于經常進行插入和刪除的情況。

例如，已知一組關鍵字（32，40，36，53，16，46，71，27，42，24，49，64），哈希表長度為13，哈希函數為：H（key）= key % 13，則用鏈地址法處理沖突的結果如圖8.27所示：

圖8.27 鏈地址法處理沖突時的哈希表

本例的平均查找長度 ASL=(1*7+2*4+3*1)/12=1.5

拉鏈法的優點

與開放定址法相比，拉鏈法有如下幾個優點：

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

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

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

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

拉鏈法的缺點

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

4、建立公共溢出區

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

沖突太多了怎么辦?

      當沖突太多的時候,我們一般采用的方法時拉鏈法,采用拉鏈法的原因是動態申請空間,至于優點在上面 已經闡述了.沖突太多的時候會產生堆積狀態,我們將H(key)相同的關鍵字都統一放到一個鏈里,當出現沖突的時候我們就把該元素接在鏈表后面,這樣可以 避免產生堆積現象,縮短平均查找長度.

當數據表太小,而數據太多的時候怎么辦?

        當數據表太小數據太多可以通過建立一個溢出表,專門用來存放哈希表中放不下的記錄.

================================================================================================