哈希表原理

在瞭解 golang 的 map 之前，我們需要了解哈希這個概念。

哈希表，又稱散列表 (Hash table)，是根據鍵(key) 而直接訪問在內存儲存位置的數據結構。也就是說，它通過計算出一個鍵值的函數，將所需查詢的數據映射到表中的一個位置讓人訪問，這加快了查找速度。這個映射函數稱爲散列函數，存放記錄的數組稱作散列表。

1、特點

一個優秀的哈希函數應該包含以下特性：

2、哈希衝突

由於哈希算法被計算的數據是無限的，而計算後的結果範圍有限，因此總會存在不同的數據經過計算後得到的值相同，這就是哈希衝突。

3、解決哈希衝突的方法

解決哈希衝突的方法一般有：開放定址法、鏈地址法（拉鍊法）、再哈希法、建立公共溢出區等方法。

而我們這裏主要介紹開放地址法和拉鍊法。

3.1、拉鍊法

鏈接地址法的思路是將哈希值相同的元素構成一個同義詞的單鏈表，並將單鏈表的頭指針存放在哈希表的第 i 個單元中，查找、插入和刪除主要在同義詞鏈表中進行。鏈表法適用於經常進行插入和刪除的情況。

3.2、開放地址法

從發生衝突的那個單元起，按照一定的次序，從哈希表中找到一個空閒的單元。然後把發生衝突的元素存入到該單元的一種方法。開放定址法需要的表長度要大於等於所需要存放的元素。

在開放尋址法中解決衝突的方法有：線性探測法、平方探測法、雙散列函數探測法。

開放定址法的缺點在於刪除元素的時候不能真的刪除，否則會引起查找錯誤，只能做一個特殊標記。只到有下個元素插入才能真正刪除該元素。

3.2.1、線性探測法

線性探查法是開放定址法中最簡單的衝突處理方法，它從發生衝突的單元起，依次判斷下一個單元是否爲空，當達到最後一個單元時，再從表首依次判斷。直到碰到空閒的單元或者探查完全部單元爲止。

設 Hash(key) 表示關鍵字 key 的哈希值，表示哈希表的槽位數（哈希表的大小）。

線性探測法可以表示爲：

同樣以哈希函數 H(key)=key MOD 7（除數取餘法）對一組元素 [50,700,76,85,92,73,101] 進行映射。

其中，empty 代表槽位爲空，occupied 代表槽位已被佔（後續映射到該槽，則需要線性向下繼續探測)，而 lazy delete 則代表將槽位裏面的數據清除，並不釋放存儲空間。

3.2.2、平方探測法

平方探查法即是發生衝突時，用發生衝突的單元 d[i], 加上 1²、 2² 等。即 d[i] + 1²，d[i] + 2², d[i] + 3²… 直到找到空閒單元。在實際操作中，平方探查法不能探查到全部剩餘的單元。不過在實際應用中，能探查到一半單元也就可以了。若探查到一半單元仍找不到一個空閒單元，表明此散列表太滿，應該重新建立。

3.2.3、雙散列函數探測法

這種方法使用兩個散列函數 hl 和 h2。

其中 hl 和前面的 h 一樣，以關鍵字爲自變量，產生一個 0 至 m-l 之間的數作爲散列地址；

h2 也以關鍵字爲自變量，產生一個 l 至 m-1 之間的、並和 m 互素的數 (即 m 不能被該數整除) 作爲探查序列的地址增量(即步長)，探查序列的步長值是固定值 l.

對於平方探查法，探查序列的步長值是探查次數 i 的兩倍減 l；

對於雙散列函數探查法，其探查序列的步長值是同一關鍵字的另一散列函數的值。

4、小結

哈希桶：所有哈希值組成哈希空間

裝載因子：表示哈希表中元素的填滿程度。
計算方式：裝載因子 = 填入哈希表中的元素個數 / 哈希表的長度。
裝載因子越大，填入的元素越多，空間利用率越高，發生哈希衝突的幾率變大。
裝載因子越小，填入的元素越少，空間利用率越低，但空間浪費多，而且會提高擴容操作的次數。

開放地址法

只用數組一種數據結構就可完成存儲，繼承了數組的優點，對 CPU 緩存友好，易於序列化操作。

但是它對內存的利用率不如鏈地址法，且發生衝突時代價更高。當數據量明確、裝載因子小，適合採用開放尋址法。

鏈地址法

1、處理衝突簡單，且無堆積現象

2、由於拉鍊法中各鏈表上的節點空間在需要時創建，不必像開放地址法事先申請好足夠的內存，因此對內存使用率較高，適合造表前無法確定表長的情況

3、對裝載因子的容忍度較高，適合存儲大對象、大數據量的哈希表

4、刪除結點的操作易於實現，只要簡單地刪去鏈表上相應的結點即可。

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

猜你喜歡