哈希表，又稱散列表(Hash table)，是根據(jù)鍵(key)而直接訪問在內(nèi)存儲存位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算出一個鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中的一個位置讓人訪問，這加快了查找速度。這個映射函數(shù)稱為散列函數(shù)，存放記錄的數(shù)組稱作散列表。

1、特點

一個優(yōu)秀的哈希函數(shù)應(yīng)該包含以下特性：

• 均勻性：一個好的哈希函數(shù)應(yīng)該在其輸出范圍內(nèi)盡可能均勻地映射，也就是說，應(yīng)以大致相同的概率生成輸出范圍內(nèi)的每個哈希值。
• 高效率：哈希效率要高，即使很長的輸入?yún)?shù)也能快速計算出哈希值。
• 單向性：哈希過程必須是確定性的，這意味著對于給定的輸入值，它必須始終生成相同的哈希值。
• 雪崩效應(yīng)：微小的輸入值變化也會讓輸出值發(fā)生巨大的變化。
• 不可逆：從哈希函數(shù)的輸出值不可反向推導出原始的數(shù)據(jù)。

2、哈希沖突

由于哈希算法被計算的數(shù)據(jù)是無限的，而計算后的結(jié)果范圍有限，因此總會存在不同的數(shù)據(jù)經(jīng)過計算后得到的值相同，這就是哈希沖突。

3、解決哈希沖突的方法

解決哈希沖突的方法一般有：開放定址法、鏈地址法（拉鏈法）、再哈希法、建立公共溢出區(qū)等方法。

而我們這里主要介紹開放地址法和拉鏈法。

3.1、拉鏈法

鏈接地址法的思路是將哈希值相同的元素構(gòu)成一個同義詞的單鏈表，并將單鏈表的頭指針存放在哈希表的第i個單元中，查找、插入和刪除主要在同義詞鏈表中進行。鏈表法適用于經(jīng)常進行插入和刪除的情況。

3.2、開放地址法

從發(fā)生沖突的那個單元起，按照一定的次序，從哈希表中找到一個空閑的單元。然后把發(fā)生沖突的元素存入到該單元的一種方法。開放定址法需要的表長度要大于等于所需要存放的元素。

在開放尋址法中解決沖突的方法有：線性探測法、平方探測法、雙散列函數(shù)探測法。

開放定址法的缺點在于刪除元素的時候不能真的刪除，否則會引起查找錯誤，只能做一個特殊標記。只到有下個元素插入才能真正刪除該元素。

3.2.1、線性探測法

線性探查法是開放定址法中最簡單的沖突處理方法，它從發(fā)生沖突的單元起，依次判斷下一個單元是否為空，當達到最后一個單元時，再從表首依次判斷。直到碰到空閑的單元或者探查完全部單元為止。

設(shè)Hash(key)表示關(guān)鍵字key的哈希值，表示哈希表的槽位數(shù)（哈希表的大?。?/p>

線性探測法可以表示為：

• 如果Hash(x)%M已經(jīng)有數(shù)據(jù)，則嘗試(Hash(x)+1)%M
• 如果(Hash(x)+1)%M有數(shù)據(jù)，則嘗試(Hash(x)+2)%M
• 如果(Hash(x)+2)%M有數(shù)據(jù)，則嘗試(Hash(x)+3)%M
• …

同樣以哈希函數(shù)H(key)=key MOD 7（除數(shù)取余法）對一組元素[50,700,76,85,92,73,101]進行映射。

其中，empty代表槽位為空，occupied代表槽位已被占（后續(xù)映射到該槽，則需要線性向下繼續(xù)探測)，而lazy delete則代表將槽位里面的數(shù)據(jù)清除，并不釋放存儲空間。

3.2.2、平方探測法

平方探查法即是發(fā)生沖突時，用發(fā)生沖突的單元d[i], 加上 1²、 2²等。即d[i] + 1²，d[i] + 2², d[i] + 3²…直到找到空閑單元。 在實際操作中，平方探查法不能探查到全部剩余的單元。不過在實際應(yīng)用中，能探查到一半單元也就可以了。若探查到一半單元仍找不到一個空閑單元，表明此散列表太滿，應(yīng)該重新建立。

3.2.3、雙散列函數(shù)探測法

這種方法使用兩個散列函數(shù)hl和h2。

其中hl和前面的h一樣，以關(guān)鍵字為自變量，產(chǎn)生一個0至m-l之間的數(shù)作為散列地址；

h2也以關(guān)鍵字為自變量，產(chǎn)生一個l至m-1之間的、并和m互素的數(shù)(即m不能被該數(shù)整除)作為探查序列的地址增量(即步長)，探查序列的步長值是固定值l.

對于平方探查法，探查序列的步長值是探查次數(shù)i的兩倍減l；

對于雙散列函數(shù)探查法，其探查序列的步長值是同一關(guān)鍵字的另一散列函數(shù)的值。

4、小結(jié)

哈希桶：所有哈希值組成哈?？臻g

裝載因子：表示哈希表中元素的填滿程度。計算方式：裝載因子=填入哈希表中的元素個數(shù)/哈希表的長度。裝載因子越大，填入的元素越多，空間利用率越高，發(fā)生哈希沖突的幾率變大。裝載因子越小，填入的元素越少，空間利用率越低，但空間浪費多，而且會提高擴容操作的次數(shù)。

開放地址法

只用數(shù)組一種數(shù)據(jù)結(jié)構(gòu)就可完成存儲，繼承了數(shù)組的優(yōu)點，對CPU緩存友好，易于序列化操作。

但是它對內(nèi)存的利用率不如鏈地址法，且發(fā)生沖突時代價更高。當數(shù)據(jù)量明確、裝載因子小，適合采用開放尋址法。

鏈地址法

1、處理沖突簡單，且無堆積現(xiàn)象

2、由于拉鏈法中各鏈表上的節(jié)點空間在需要時創(chuàng)建，不必像開放地址法事先申請好足夠的內(nèi)存，因此對內(nèi)存使用率較高，適合造表前無法確定表長的情況

3、對裝載因子的容忍度較高，適合存儲大對象、大數(shù)據(jù)量的哈希表

4、刪除結(jié)點的操作易于實現(xiàn)，只要簡單地刪去鏈表上相應(yīng)的結(jié)點即可。