五分鐘速讀：什麼是散列表（哈希表）？
- 2019 年 10 月 6 日
- 筆記
作者 | 守望先生
來源 | 編程珠璣
前言
假設你們班級100個同學每個人的學號是由院系-年級-班級和編號組成，例如學號為01100168表示是1系，10級1班的68號。為了快速查找到68號的成績資訊，可以建立一張表，但是不能用學號作為下標，學號的數值實在太大。因此將學號除以1100100取余，即得到編號作為該表的下標，那麼，要查找學號為01100168的成績的時候，只要直接訪問表下標為68的數據即可。這就能夠在O（1）時間複雜度內完成成績查找。
實際上這裡就用到了散列的思想。本文重在介紹散列的思想以及散列需要考慮的問題。
散列表（哈希表）
理想散列表（哈希表）是一個包含關鍵字的具有固定大小的數組，它能夠以常數時間執行插入，刪除和查找操作。
- 每個關鍵字被映射到0到數組大小N-1範圍，並且放到合適的位置，這個映射規則就叫散列函數
- 理想情況下，兩個不同的關鍵字映射到不同的單元，然而由於數組單元有限，關鍵字範圍可能遠超數組單元，因此就會出現兩個關鍵字散列到同一個值得時候，這就是散列衝突
實例演示
通過前面的描述，我們已經了解了一些基本概念，現在來看一個實例。 假設有一個大小為7的表，現在，要將13,18,19，50，20散列到表中。
- 選擇散列函數，例如使用hash(x)=x%7作為散列函數
- 計算數據散列值，並放到合適的位置
計算13 % 7得到6，因此將13放到下標為6的位置：
0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
13 |
計算18 % 7得到4，因此將18放到下標為4的位置：
0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
18 | 13 |
計算19 % 7得到5，因此將19放到下標為5的位置：
0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
18 | 19 | 13 |
計算50 % 7得到1，因此將50放到下標為1的位置：
0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
50 | 18 | 19 | 13 |
計算20 % 7得到6，因此將20放到下標為6的位置，但是此時6的位置已經被佔用了，因此就產生了散列衝突，關於散列衝突的解決，我們後面再介紹。
將數據散列之後，如何從表中查找呢？例如，查找數值為50的數據位置，只需要計算50 % 7，得到下標1，訪問下標1的位置即可。但是如果考慮散列衝突，就沒有那麼簡單了。
通過這個實例，了解了以下幾個概念：
- 散列函數，散列函數的選擇非常重要
- 散列衝突，涉及散列表時，因盡量避免散列衝突，對於衝突也要有好的解決方案
- 快速從散列表中查找數據
衝突解決
解決散列衝突通常有以下幾種方法：
- 拉鏈法
- 開放定址法
- 再散列
- …
拉鏈法
分離鏈接法的做法是將同一個值的關鍵字保存在同一個表中。例如，對於前面：
0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
50 | 18 | 19 | 13 |
如果再要插入元素20，則在下標為6的位置存儲表頭，而表的內容是13和20。
這種方法的特點是需要另外分配新的單元來存儲散列到同一個位置的數據。
查找的時候，除了根據計算出來的散列值找到對應位置外，還需要在鏈表上進行搜索。而在單鏈表上的查找速度是很慢的。另外散列函數如果設計得好，衝突的概率其實也會很小。
開放定址法
而開放定址法的思想是，如果衝突發生，就選擇另外一個可用的位置。
而開放定址法中也有常見的幾種策略。
- 線性探測法
還是以前面的為例：
0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
50 | 18 | 19 | 13 |
如果此時再要插入20，則20 % 7 = 6，但是6的位置已有元素，因此探測下一個位置（6+1）%7，在這裡就是下標為0的位置。因此20的存儲位置如下：
0 | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
20 | 50 | 18 | 19 | 13 |
但這種方式的一個問題是，可能造成一次聚集，因為一旦衝突發生，為了處理衝突就會佔用下一個位置，而如果衝突較多時，就會出現數據都聚集在一塊區域。這樣就會導致任何關鍵字都需要多次嘗試才可能解決衝突。
- 平方探測法
顧名思義，如果說前面的探測函數是F（i）= i % 7，那麼平方探測法就是F（i）= (i^2 )% 7。 但是這也同樣會產生二次聚集問題。
- 雙散列
為了避免聚集，在探測時選擇跳躍式的探測，即再使用一個散列函數，用來計算探測的位置。假設前面的散列函數為hash1(X)，用於探測的散列函數為hash2(X)，那麼一種流行的選擇是F(i) = i * hash2(X)，即第一次衝突時探測hash1(X)+hash2(X)的位置，第二次探測 hash1(X)+2hash2(X)的位置。
可以看到，無論是哪種開放定址法，它都要求表足夠大。
再散列
我們前面也說到，散列表可以認為是具有固定大小的數組，那麼如果插入新的數據時散列表已滿，或者散列表所剩容量不多該怎麼辦？這個時候就需要再散列，常見做法是，建立一個是原來兩倍大小的散列表，將原來表中的關鍵字重新散列到新表中。
散列表的應用
散列表應用很廣泛。例如做文件校驗或數字簽名。當然還有快速查詢功能的實現。例如，redis中的字典結構就使用了散列表，使用MurmurHash演算法來計算字元串的hash值，並採用拉鏈法處理衝突，，當散列表的裝載因子（關鍵字個數與散列表大小的比）接近某個大小時，進行再散列。
總結
一個設計良好的散列表能夠幾乎在O（1）時間複雜度內完成插入，刪除和查找，但前提是散列函數設計得足夠優雅，以及有著合適散列衝突解決方案。常見衝突解決方案有：
- 拉鏈法
- 開放地址檢測法
其中拉鏈法在實際中是很常見的一種解決方案。另外本文重點說明什麼是散列表（哈希表），因此沒有涉及具體的程式碼，後面將會通過實例來看散列表的實際應用。