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

1、特點(diǎn)

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

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

2、哈希沖突

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

3、解決哈希沖突的方法

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

而我們這里主要介紹開(kāi)放地址法和拉鏈法。

3.1、拉鏈法

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

3.2、開(kāi)放地址法

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

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

開(kāi)放定址法的缺點(diǎn)在于刪除元素的時(shí)候不能真的刪除，否則會(huì)引起查找錯(cuò)誤，只能做一個(gè)特殊標(biāo)記。只到有下個(gè)元素插入才能真正刪除該元素。

3.2.1、線性探測(cè)法

線性探查法是開(kāi)放定址法中最簡(jiǎn)單的沖突處理方法，它從發(fā)生沖突的單元起，依次判斷下一個(gè)單元是否為空，當(dāng)達(dá)到最后一個(gè)單元時(shí)，再?gòu)谋硎滓来闻袛唷Ｖ钡脚龅娇臻e的單元或者探查完全部單元為止。

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

線性探測(cè)法可以表示為：

• 如果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ù)取余法）對(duì)一組元素[50,700,76,85,92,73,101]進(jìn)行映射。

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

3.2.2、平方探測(cè)法

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

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

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

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

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

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

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

4、小結(jié)

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

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

開(kāi)放地址法

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

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

鏈地址法

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

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

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

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