Go 數(shù)據(jù)結(jié)構(gòu)和算法篇（十四）：哈希表、哈希函數(shù)、哈希沖突和哈希算法

一、哈希表

哈希表（HashTable，也叫散列表），是根據(jù)鍵名（Key）直接訪問對應(yīng)內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。

其實現(xiàn)原理是通過哈希函數(shù)（也叫散列函數(shù)）將元素的鍵名映射為數(shù)組下標(biāo)（轉(zhuǎn)化后的值叫做哈希值或散列值），然后在對應(yīng)下標(biāo)位置存儲記錄值。當(dāng)我們按照鍵名查詢元素時，可以使用同樣的哈希函數(shù)，將鍵名轉(zhuǎn)化為數(shù)組下標(biāo)，從對應(yīng)的數(shù)組下標(biāo)位置讀取數(shù)據(jù)：

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

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

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

二、哈希函數(shù)與哈希沖突

哈希函數(shù)用于將鍵名經(jīng)過處理后轉(zhuǎn)化為對應(yīng)的哈希值。具有以下特性：

• 哈希函數(shù)計算得到的哈希值是非負(fù)整數(shù)；

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

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

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

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

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

哈希函數(shù)設(shè)計

要減少哈希沖突，提高哈希表操作效率，設(shè)計一個優(yōu)秀的哈希函數(shù)至關(guān)重要，我們平時經(jīng)常使用的 MD5 加密就是一個哈希函數(shù)，但是其實還有其他很多自定義的設(shè)計實現(xiàn)，要根據(jù)不同場景，設(shè)計不同的哈希函數(shù)來減少哈希沖突，而且哈希函數(shù)也要足夠簡單，否則執(zhí)行哈希函數(shù)本身會成為哈希表的性能瓶頸。

我們?nèi)粘：苌贂约喝ピO(shè)計哈希函數(shù)，但是做一些簡單的了解還是有必要的。通常有以下幾種哈希函數(shù)構(gòu)造方法：

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

• 數(shù)字分析法：即對數(shù)字做左移、右移、反轉(zhuǎn)等操作獲取哈希值；

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

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

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

哈希沖突處理

我們前面說過，設(shè)計再好的哈希函數(shù)也不能完全避免哈希沖突，我們只能優(yōu)化自己的實現(xiàn)讓哈希沖突盡可能少出現(xiàn)罷了，如果出現(xiàn)了哈希沖突，該如何處理呢？下面給出一些思路：

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

• 再哈希函數(shù)法：發(fā)生哈希沖突后，換一個哈希函數(shù)計算哈希值

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

介紹完以上內(nèi)容之后，想必你對如何打造工業(yè)級哈希表已經(jīng)心中有數(shù)。主要考慮因素包含以下幾個方面：

• 哈希函數(shù)設(shè)置合理，不能太過復(fù)雜，成為性能瓶頸；

• 設(shè)置裝載因子閾值，支持動態(tài)擴容，裝載因子閾值設(shè)置要充分權(quán)衡時間、空間復(fù)雜度；

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

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

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

三、哈希算法

我們前面分享了哈希表、哈希函數(shù)和哈希沖突，哈希算法簡單理解就是實現(xiàn)前面提到的哈希函數(shù)的算法，用于將任意長度的二進制值串映射為固定長度的二進制值串，映射之后得到的二進制值就是哈希值。

我們?nèi)粘ｉ_發(fā)中最常見的哈希算法應(yīng)用就是通過 MD5 對數(shù)據(jù)進行加密了：

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 就是一個哈希函數(shù)。執(zhí)行上述代碼，打印結(jié)果如下：

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

• 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈希算法也叫單向算法，不可逆）；

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

• 哈希沖突的概率要很小，對于不同的原始數(shù)據(jù)，哈希值相同的概率非常小；

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

四、哈希算法的應(yīng)用

1、場景一：安全加密

我們?nèi)粘Ｓ脩裘艽a加密通常使用的都是 md5、sha 等哈希函數(shù)，因為不可逆，而且微小的區(qū)別加密之后的結(jié)果差距很大，所以安全性更好。

2、場景二：唯一標(biāo)識

比如我們的 URL 字段或者圖片字段要求不能重復(fù)，這個時候就可以通過對相應(yīng)字段值做 md5 處理，將數(shù)據(jù)統(tǒng)一為 32 位長度從數(shù)據(jù)庫索引構(gòu)建和查詢角度效果更好，此外，還可以對文件之類的二進制數(shù)據(jù)做 md5 處理，作為唯一標(biāo)識，這樣判定重復(fù)文件的時候更快捷。

3、場景三：數(shù)據(jù)校驗

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

4、場景五：哈希函數(shù)

前面我們已經(jīng)提到，PHP 中的 md5、sha1、hash 等函數(shù)都是基于哈希算法計算哈希值。

5、場景五：負(fù)載均衡

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

6、場景六：分布式緩存

分布式緩存和其他機器或數(shù)據(jù)庫的分布式不一樣，因為每臺機器存放的緩存數(shù)據(jù)不一致，每當(dāng)緩存機器擴容時，需要對緩存存放機器進行重新索引（或者部分重新索引），這里應(yīng)用到的也是哈希算法的思想。后面我們介紹 Redis 系列的時候會系統(tǒng)闡述這一塊。