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

散列函數(shù)

散列函數(shù)，顧名思義，它是一個(gè)函數(shù)。如果把它定義成 hash(key) ，其中 key 表示元素的鍵值，則 hash(key) 的值表示經(jīng)過(guò)散列函數(shù)計(jì)算得到的散列值。

散列函數(shù)的特點(diǎn)：

1、確定性。如果兩個(gè)散列值是不相同的（根據(jù)同一函數(shù)），那么這兩個(gè)散列值的原始輸入也是不相同的。

2、散列碰撞（collision）。散列函數(shù)的輸入和輸出不是唯一對(duì)應(yīng)關(guān)系的，如果兩個(gè)散列值相同，兩個(gè)輸入值很可能是相同的，但也可能不同。

3、不可逆性。一個(gè)哈希值對(duì)應(yīng)無(wú)數(shù)個(gè)明文，理論上你并不知道哪個(gè)是。

“船長(zhǎng)，如果一樣?xùn)|西你知道在哪里，還算不算丟了?！?/span>

“不算?！?/span>

“好的，那您的酒壺沒(méi)有丟?！?/span>

4、混淆特性。輸入一些數(shù)據(jù)計(jì)算出散列值，然后部分改變輸入值，一個(gè)具有強(qiáng)混淆特性的散列函數(shù)會(huì)產(chǎn)生一個(gè)完全不同的散列值。

常見(jiàn)的散列函數(shù)

1. MD5

MD5 即 Message-Digest Algorithm 5（信息-摘要算法5），用于確保信息傳輸完整一致。是計(jì)算機(jī)廣泛使用的雜湊算法之一，主流編程語(yǔ)言普遍已有 MD5 實(shí)現(xiàn)。

將數(shù)據(jù)（如漢字）運(yùn)算為另一固定長(zhǎng)度值，是雜湊算法的基礎(chǔ)原理，MD5 的前身有 MD2 、MD3 和 MD4 。

MD5 是輸入不定長(zhǎng)度信息，輸出固定長(zhǎng)度 128-bits 的算法。經(jīng)過(guò)程序流程，生成四個(gè)32位數(shù)據(jù)，最后聯(lián)合起來(lái)成為一個(gè) 128-bits 散列。

基本方式為，求余、取余、調(diào)整長(zhǎng)度、與鏈接變量進(jìn)行循環(huán)運(yùn)算，得出結(jié)果。

MD5 計(jì)算廣泛應(yīng)用于錯(cuò)誤檢查。在一些 BitTorrent 下載中，軟件通過(guò)計(jì)算 MD5 來(lái)檢驗(yàn)下載到的碎片的完整性。

MD5 校驗(yàn)

2. SHA-1

SHA-1（Secure Hash Algorithm 1，中文名：安全散列算法1）是一種密碼散列函數(shù)，SHA-1可以生成一個(gè)被稱為消息摘要的160位（20字節(jié)）散列值，散列值通常的呈現(xiàn)形式為40個(gè)十六進(jìn)制數(shù)。

SHA-1 曾經(jīng)在許多安全協(xié)議中廣為使用，包括TLS和SSL、PGP、SSH、S/MIME和IPsec，曾被視為是MD5的后繼者。

散列沖突

理想中的一個(gè)散列函數(shù)，希望達(dá)到：

如果 key1 ≠ key2，那 hash(key1) ≠ hash(key2)。

這種效果，然而在真實(shí)的情況下，要想找到一個(gè)不同的 key 對(duì)應(yīng)的散列值都不一樣的散列函數(shù)，幾乎是不可能的，即使是 MD5 或者 由美國(guó)國(guó)家安全局設(shè)計(jì)的 SHA-1 算法也無(wú)法實(shí)現(xiàn)。

事實(shí)上，再好的散列函數(shù)都無(wú)法避免散列沖突。為什么呢？這涉及到數(shù)學(xué)中比較好理解的一個(gè)原理：抽屜原理。

抽屜原理：桌上有十個(gè)蘋果，要把這十個(gè)蘋果放到九個(gè)抽屜里，無(wú)論怎樣放，我們會(huì)發(fā)現(xiàn)至少會(huì)有一個(gè)抽屜里面至少放兩個(gè)蘋果。這一現(xiàn)象就是我們所說(shuō)的“抽屜原理”。

抽屜原理

對(duì)于散列表而言，無(wú)論設(shè)置的存儲(chǔ)區(qū)域（n）有多大，當(dāng)需要存儲(chǔ)的數(shù)據(jù)大于 n 時(shí)，那么必然會(huì)存在哈希值相同的情況。這就是所謂的散列沖突。

散列沖突

那應(yīng)該如何解決散列沖突問(wèn)題呢？常用的散列沖突解決方法有兩類，開(kāi)放尋址法（open addressing）和鏈表法（chaining）。

開(kāi)放尋址法

定義：將散列函數(shù)擴(kuò)展定義成探查序列，即每個(gè)關(guān)鍵字有一個(gè)探查序列h(k,0)、h(k,1)、…、h(k,m-1)，這個(gè)探查序列一定是0….m-1的一個(gè)排列（一定要包含散列表全部的下標(biāo)，不然可能會(huì)發(fā)生雖然散列表沒(méi)滿，但是元素不能插入的情況），如果給定一個(gè)關(guān)鍵字k，首先會(huì)看h(k,0)是否為空，如果為空，則插入；如果不為空，則看h(k,1)是否為空，以此類推。

開(kāi)放尋址法是一種解決碰撞的方法，對(duì)于開(kāi)放尋址沖突解決方法，比較經(jīng)典的有線性探測(cè)方法（Linear Probing）、二次探測(cè)（Quadratic probing）和 雙重散列（Double hashing）等方法。

線性探測(cè)方法

開(kāi)放尋址法之線性探測(cè)方法

當(dāng)我們往散列表中插入數(shù)據(jù)時(shí)，如果某個(gè)數(shù)據(jù)經(jīng)過(guò)散列函數(shù)散列之后，存儲(chǔ)位置已經(jīng)被占用了，我們就從當(dāng)前位置開(kāi)始，依次往后查找，看是否有空閑位置，直到找到為止。

以上圖為例，散列表的大小為 8 ，黃色區(qū)域表示空閑位置，橙色區(qū)域表示已經(jīng)存儲(chǔ)了數(shù)據(jù)。目前散列表中已經(jīng)存儲(chǔ)了 4 個(gè)元素。此時(shí)元素 7777777  經(jīng)過(guò) Hash 算法之后，被散列到位置下標(biāo)為 7 的位置，但是這個(gè)位置已經(jīng)有數(shù)據(jù)了，所以就產(chǎn)生了沖突。

于是按順序地往后一個(gè)一個(gè)找，看有沒(méi)有空閑的位置，此時(shí)，運(yùn)氣很好正巧在下一個(gè)位置就有空閑位置，將其插入，完成了數(shù)據(jù)存儲(chǔ)。

線性探測(cè)法一個(gè)很大的弊端就是當(dāng)散列表中插入的數(shù)據(jù)越來(lái)越多時(shí)，散列沖突發(fā)生的可能性就會(huì)越來(lái)越大，空閑位置會(huì)越來(lái)越少，線性探測(cè)的時(shí)間就會(huì)越來(lái)越久。極端情況下，需要從頭到尾探測(cè)整個(gè)散列表，所以最壞情況下的時(shí)間復(fù)雜度為 O(n)。

開(kāi)放尋址法之線性探測(cè)方法的弊端

二次探測(cè)方法

二次探測(cè)是二次方探測(cè)法的簡(jiǎn)稱。顧名思義，使用二次探測(cè)進(jìn)行探測(cè)的步長(zhǎng)變成了原來(lái)的“二次方”，也就是說(shuō)，它探測(cè)的下標(biāo)序列為 hash(key)+0，hash(key)+1^2或[hash(key)-1^2]，hash(key)+2^2或[hash(key)-2^2]。

二次探測(cè)方法

以上圖為例，散列表的大小為 8 ，黃色區(qū)域表示空閑位置，橙色區(qū)域表示已經(jīng)存儲(chǔ)了數(shù)據(jù)。目前散列表中已經(jīng)存儲(chǔ)了 7 個(gè)元素。此時(shí)元素 7777777  經(jīng)過(guò) Hash 算法之后，被散列到位置下標(biāo)為 7 的位置，但是這個(gè)位置已經(jīng)有數(shù)據(jù)了，所以就產(chǎn)生了沖突。

按照二次探測(cè)方法的操作，有沖突就先 + 1^2，8 這個(gè)位置有值，沖突；變?yōu)?- 1^2，6 這個(gè)位置有值，還是有沖突；于是 - 2^2， 3 這個(gè)位置是空閑的，插入。

雙重散列方法

所謂雙重散列，意思就是不僅要使用一個(gè)散列函數(shù)，而是使用一組散列函數(shù) hash1(key)，hash2(key)，hash3(key)。。。。。。先用第一個(gè)散列函數(shù)，如果計(jì)算得到的存儲(chǔ)位置已經(jīng)被占用，再用第二個(gè)散列函數(shù)，依次類推，直到找到空閑的存儲(chǔ)位置。

雙重散列方法

以上圖為例，散列表的大小為 8 ，黃色區(qū)域表示空閑位置，橙色區(qū)域表示已經(jīng)存儲(chǔ)了數(shù)據(jù)。目前散列表中已經(jīng)存儲(chǔ)了 7 個(gè)元素。此時(shí)元素 7777777  經(jīng)過(guò) Hash 算法之后，被散列到位置下標(biāo)為 7 的位置，但是這個(gè)位置已經(jīng)有數(shù)據(jù)了，所以就產(chǎn)生了沖突。

此時(shí)，再將數(shù)據(jù)進(jìn)行一次哈希算法處理，經(jīng)過(guò)另外的 Hash 算法之后，被散列到位置下標(biāo)為 3 的位置，完成操作。

事實(shí)上，不管采用哪種探測(cè)方法，只要當(dāng)散列表中空閑位置不多的時(shí)候，散列沖突的概率就會(huì)大大提高。為了盡可能保證散列表的操作效率，一般情況下，需要盡可能保證散列表中有一定比例的空閑槽位。

一般使用加載因子（load factor）來(lái)表示空位的多少。

加載因子是表示 Hsah 表中元素的填滿的程度，若加載因子越大，則填滿的元素越多,這樣的好處是：空間利用率高了,但沖突的機(jī)會(huì)加大了。反之,加載因子越小,填滿的元素越少,好處是沖突的機(jī)會(huì)減小了，但空間浪費(fèi)多了。

鏈表法

鏈表法是一種更加常用的散列沖突解決辦法，相比開(kāi)放尋址法，它要簡(jiǎn)單很多。如下動(dòng)圖所示，在散列表中，每個(gè)位置對(duì)應(yīng)一條鏈表，所有散列值相同的元素都放到相同位置對(duì)應(yīng)的鏈表中。

鏈表法