Go 數據結構和算法篇：哈希表、哈希函數、哈希衝突和哈希算法

一、哈希表

哈希表（HashTable，也叫散列表），是根據鍵名（Key）直接訪問對應內存存儲位置的數據結構。

其實現原理是通過哈希函數（也叫散列函數）將元素的鍵名映射爲數組下標（轉化後的值叫做哈希值或散列值），然後在對應下標位置存儲記錄值。當我們按照鍵名查詢元素時，可以使用同樣的哈希函數，將鍵名轉化爲數組下標，從對應的數組下標位置讀取數據：

散列表圖示

顯然，哈希表使用了數組支持按照下標隨機訪問數據的特性，所以哈希表其實就是數組的一種擴展，由數組演化而來。可以說，沒有數組，就沒有哈希表。我們知道，數組訪問元素的時間複雜度是 O(1)，所以哈希表也是一樣（不考慮哈希函數的複雜度的話），因此非常高效。

此外，我們也可以看到，哈希技術既是一種存儲方法，也是一種查找方法。不過，與之前介紹的查找算法不同的是哈希表的不同記錄之間不存在邏輯關係，因此最適合求解的問題是查找與給定值相等的記錄，而不適合做範圍查詢。

哈希表中有兩個關鍵的概念，一個是哈希函數（或者叫散列函數），一個是哈希衝突（或者叫散列衝突）。下面，我們來重點介紹這兩個概念。

二、哈希函數與哈希衝突

哈希函數用於將鍵名經過處理後轉化爲對應的哈希值。具有以下特性：

• 哈希函數計算得到的哈希值是非負整數；

• 如果 key1 == key2，則 hash(key1) == hash(key2)；

• 如果 key1 != key2，則 hash(key1) != hash(key2)。

所謂哈希衝突，簡單來說，指的是 key1 != key2 的情況下，通過哈希函數處理，hash(key1) == hash(key2)，這個時候，我們就說發生了哈希衝突。

設計再好的哈希函數也無法避免哈希衝突，根本原因是哈希值是非負整數，總量是有限的，但是現實世界中要處理的鍵名是無限的，將無限的數據映射到有限的集合，肯定避免不了衝突。

事實上，如果不考慮哈希衝突，哈希表的查找效率是非常高的，時間複雜度是 O(1)，比二分查找效率還要高，但是因爲無法避免哈希衝突，所以哈希表查找的時間複雜度取決於哈希衝突，最壞的情況可能是 O(n)，退化爲順序查找。這種情況在哈希函數設計不合理的情況下更糟。

哈希函數設計

要減少哈希衝突，提高哈希表操作效率，設計一個優秀的哈希函數至關重要，我們平時經常使用的 MD5 加密就是一個哈希函數，但是其實還有其他很多自定義的設計實現，要根據不同場景，設計不同的哈希函數來減少哈希衝突，而且哈希函數也要足夠簡單，否則執行哈希函數本身會成爲哈希表的性能瓶頸。

我們日常很少會自己去設計哈希函數，但是做一些簡單的瞭解還是有必要的。通常有以下幾種哈希函數構造方法：

• 直接定址法：即 f(key) = a*key + b，f 表示哈希函數，a、b 是常量，key 是鍵名；

• 數字分析法：即對數字做左移、右移、反轉等操作獲取哈希值；

• 除數留餘法：即 f(key) = key % p，p 表示容器數量，這種方式通常用在將數據存放到指定容器中，如何決定哪個數據放到哪個容器，比如分表後插入數據如何處理（此時 p 表示拆分後數據表的數量），分佈式 Redis 如何存放數據（此時 p 表示幾臺 Redis 服務器）；

• 隨機數法：即 f(key) = random(key)，比如負載均衡的 random 機制。

以上只是一些比較常見的哈希函數設計思路，還有很多其他的設計方法，這裏就不一一列舉了。

哈希衝突處理

我們前面說過，設計再好的哈希函數也不能完全避免哈希衝突，我們只能優化自己的實現讓哈希衝突儘可能少出現罷了，如果出現了哈希衝突，該如何處理呢？下面給出一些思路：

• 開放尋址法：該方法又可以細分爲三種 —— 線性尋址、二次探測、隨機探測。線性尋址表示出現哈希衝突之後，就去尋找下一個空的哈希地址；線性尋址步長是 1，二次探測步長是線性尋址步長的 2 次方，其它邏輯一樣；同理，隨機探測每次步長隨機。不管哪種探測方法，哈希表中空閒位置不多的時候，哈希衝突的概率就會提高，爲了保證操作效率，我們會盡可能保證哈希表中有一定比例的空閒槽位，我們用裝載因子來表示空位的多少，裝載因子 = 填入元素 / 哈希表長度，裝載因子越大，表明空閒位置越少，衝突越多，哈希表性能降低。

• 再哈希函數法：發生哈希衝突後，換一個哈希函數計算哈希值

• 鏈地址法：發生哈希衝突後，將對應數據鏈接到該哈希值映射的上一個值之後，即將哈希值相同的元素放到相同槽位對應的鏈表中。鏈地址法即使在哈希衝突很多的情況下，也可以保證將所有數據存儲到哈希表中，但是也引入了遍歷單鏈錶帶來性能損耗。

介紹完以上內容之後，想必你對如何打造工業級哈希表已經心中有數。主要考慮因素包含以下幾個方面：

• 哈希函數設置合理，不能太過複雜，成爲性能瓶頸；

• 設置裝載因子閾值，支持動態擴容，裝載因子閾值設置要充分權衡時間、空間複雜度；

• 如果一次性擴容耗時長，可採取分批擴容的策略，達到閾值後只申請空間，不搬移數據，以後每插入一條數據，搬移一箇舊數據，最後逐步完成搬移，期間爲了兼容新老哈希表查詢，可以先查新表，再查老表；

• 哈希衝突解決辦法：開放尋址法在數據量較小、裝載因子小的時候（小於 1）選用；鏈表法可以容忍裝載因子大於 1，適合存儲大對象、大數據量的哈希表，且更加靈活，支持更多優化策略。

補充一張鏈地址法處理哈希衝突的圖示：

鏈地址法解決哈希衝突圖示

三、哈希算法

我們前面分享了哈希表、哈希函數和哈希衝突，哈希算法簡單理解就是實現前面提到的哈希函數的算法，用於將任意長度的二進制值串映射爲固定長度的二進制值串，映射之後得到的二進制值就是哈希值。

我們日常開發中最常見的哈希算法應用就是通過 MD5 對數據進行加密了：

package main

import (
    "crypto/md5"
    "fmt"
)

func main() {
    data := []byte("Hello, World!")
    hash := md5.Sum(data)
    fmt.Printf("原始值: %s\n", data)
    fmt.Printf("MD5值: %x\n", hash)
}

這裏的 md5.Sum 就是一個哈希函數。執行上述代碼，打印結果如下：

哈希算法的一般特性如下：

• 從哈希值不能反向推導出原始數據（所以哈希算法也叫單向算法，不可逆）；

• 對輸入數據非常敏感，哪怕原始數據只修改了一個比特，最後得到的哈希值也大不相同；

• 哈希衝突的概率要很小，對於不同的原始數據，哈希值相同的概率非常小；

• 哈希算法的執行效率要儘量高效，針對較長的文本，也能快速地計算出哈希值。

四、哈希算法的應用

1、場景一：安全加密

我們日常用戶密碼加密通常使用的都是 md5、sha 等哈希函數，因爲不可逆，而且微小的區別加密之後的結果差距很大，所以安全性更好。

2、場景二：唯一標識

比如我們的 URL 字段或者圖片字段要求不能重複，這個時候就可以通過對相應字段值做 md5 處理，將數據統一爲 32 位長度從數據庫索引構建和查詢角度效果更好，此外，還可以對文件之類的二進制數據做 md5 處理，作爲唯一標識，這樣判定重複文件的時候更快捷。

3、場景三：數據校驗

比如我們從網上下載的很多文件（尤其是 P2P 站點資源），都會包含一個 MD5 值，用於校驗下載數據的完整性，避免數據在中途被劫持篡改。

4、場景五：哈希函數

前面我們已經提到，PHP 中的 md5、sha1、hash 等函數都是基於哈希算法計算哈希值。

5、場景五：負載均衡

對於同一個客戶端上的請求，尤其是已登錄用戶的請求，我們需要將其會話請求都路由到同一臺機器，以保證數據的一致性，這可以藉助哈希算法來實現，通過用戶 ID 尾號對總機器數取模（取多少位可以根據機器數定），將結果值作爲機器編號。

6、場景六：分佈式緩存

分佈式緩存和其他機器或數據庫的分佈式不一樣，因爲每臺機器存放的緩存數據不一致，每當緩存機器擴容時，需要對緩存存放機器進行重新索引（或者部分重新索引），這裏應用到的也是哈希算法的思想。後面我們介紹 Redis 系列的時候會系統闡述這一塊。

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/It1Rtci_A3dwZp1l3ZT90w