1 哈希表

哈希表屬于編程中比較常見的數(shù)據(jù)結構之一，基本上所有的語言都會實現(xiàn)數(shù)組和哈希表這兩種結構，Hash table 的歷史是比較悠遠的，我們在編程時也是離不開的，這種數(shù)據(jù)結構的作用其實很簡單，就是我們可以根據(jù)一個 key 可以查找到對應的 value，也就是說這種數(shù)據(jù)結構存儲的是鍵值對的“列表”。

1.1 原理

首先哈希表中第一個點就是哈希函數(shù)，也就是我們需要一個函數(shù)，根據(jù)我們的 key 計算出一個值，然后根據(jù)這個值可以直接找到對應的 value。因為我們的哈希表的一個作用就是 O(1) 復雜度找到 key 對應的 value。

完美的哈希函數(shù)是可以做到將任何一個 key 值都可以計算出一個唯一且固定大小的值，不幸的是目前世界上還沒有這種完美的哈希函數(shù)。因此我們需要解決的另外一個問題就是哈希沖突的解決。

1.1.1 哈希沖突

假如我們有兩個不同的 key，通過哈希函數(shù)計算出的結果相同，那么我們是不能認為這兩個 key 在 map 中是相同的，也就是如果出現(xiàn)了這種情況，我們的 map 結構是可以解決這個問題的。目前解決辦法有很多，這里只說三個比較常見的解決方案：

開放地址法(Open Addressing)：

• 寫入時：假如 key Alice 與 Bob 通過哈希函數(shù)計算出結果沖突。當 map 中已經(jīng)存在 key Alice，再寫入 key 為 Bob時，發(fā)現(xiàn)哈希結果對應位置已經(jīng)存在 Alice，此時在 Alice 位置之后再尋找位置，一直找到為空的位置，將 Bob 寫入。
• 讀取時：此時 map 中已存在 key Alice、Bob，且哈希結果相同，此時想查找 Bob 對應 value 時，先計算 Bob 哈希結果，再通過哈希結果在 map 中查找位置，此時由于和 Alice 哈希結果相同，并且 Alice 先于 Bob 存入 map，所以會直接找到 Alice 的位置，發(fā)現(xiàn) key 是 Alice 不是 Bob，接著在 Alice 位置后面查找，直到找到 key Bob 或者找到空。

再哈希法(Re-Hashing)：

• 設計多個哈希函數(shù)，假如 Alice 與 Bob 計算哈希結果相同，那么用另外一個哈希函數(shù)來計算 Bob 的哈希值，這種方式來解決哈希沖突。
• 鏈地址法(Separate Chaining)：
• 此方法將同一個哈希結果對應的位置想象成一個桶，如果多個 key 對應哈希結果相同，那么都放到同一個桶中，并且桶中元素使用鏈表結構存儲。
• 寫入時：Alice 于 Bob 哈希結果相同，此時 map 已經(jīng)有 Alice，再寫入 Bob 時，發(fā)現(xiàn)對應哈希結果位置已經(jīng)存在了 Alice，此時在當前桶中的 Alice 后鏈接一個 Bob，此時哈希結果對應的桶就存在了兩個元素 Alice 與 Bob。
• 讀取時：讀取 Bob key 時，發(fā)現(xiàn)對應哈希結果的桶中第一個元素是 Alice，此時在桶中按鏈表順序挨個查找，直到 key 相同或者空。
• 裝載因子：此方案存在一個問題，當一個桶中元素過多時，其復雜度將增加，極端情況下就變成了鏈表。所以我們會限制在一個桶中元素的個數(shù)。這樣在一個桶中元素過多時，需要生成新的桶。
• 裝載因子 = 元素總量 / 桶總個數(shù)

在 Go 語言中，map 使用的是鏈地址法。

2 Go 中 map分析

2.1 map 數(shù)據(jù)結構

map 的源碼位于 src/runtime/map.go 文件中，結構如下：

type hmap struct { 
    count     int // 當前 map 中元素數(shù)量 
    flags     uint8 
    B         uint8  // 當前 buckets 數(shù)量，2^B 等于 buckets 個數(shù) 
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details 
    hash0     uint32 // 哈希種子 
 
    buckets    unsafe.Pointer // buckets 數(shù)組指針 
    oldbuckets unsafe.Pointer // 擴容時保存之前 buckets 數(shù)據(jù)。 
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated) 
 
    extra *mapextra // optional fields 
} 
 
// 每一個 bucket 的結構，即 hmap 中 buckets 指向的數(shù)據(jù)。 
type bmap struct { 
    tophash [bucketCnt]uint8 
} 
 
// 編譯期間重構此結構 
type bmap struct { 
    topbits  [8]uint8 
    keys     [8]keytype 
    values   [8]valuetype 
    pad      uintptr 
    overflow uintptr 
} 

關于 hmap 的結構這里已經(jīng)將很多重要的字段列出來了，其中最重要的就是 buckets 這一部分，根據(jù)上面我們說過的鏈地址法可知，對同一類 key (哈希結果相同)放入相同的桶中。此時每一個桶還有另外一個字段 overflow，也就是當前桶裝不下就會再創(chuàng)建新的桶。這就是 Go 中 map 的主要實現(xiàn)方法，更詳細的部分我們接下來一點一點聊。

2.2 源碼

map 的源碼位于 src/runtime/map.go 文件中。關于 map 的操作的具體實現(xiàn)在這里都可以找到：

• 創(chuàng)建 map：func makemap(t *maptype, hint int, h *hmap) *hmap
• 訪問某個 key：
• 返回結果只包括 value：func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
• 返回結果包括 bool 結果：func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
• 存入 key：func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
• 刪除 key：func mapdelete(t *maptype, h *hmap, key unsafe.Pointer)

本篇文章不會帶大家將源碼通讀一遍，但是會將其實現(xiàn)過程以圖或者文字形式分析出來，但是建議大家有時間可以根據(jù)本篇文章的內容再去自己讀一遍源碼，如果我這里將所有源碼都解釋一遍，估計朋友們很快就又忘記了，還不如記住實現(xiàn)流程。所以本文更多的是講 map 每個操作的過程圖，以及其中的部分要點，而不是將源碼一行一行的解釋出來。

3. 圖解 map

3.1 創(chuàng)建map

我們已經(jīng)知道 map 的數(shù)據(jù)結構，其實 map 的初始化也無非就是填充各個字段而已：

• 第一個就是 hash0 字段，此處會隨機給一個種子，用在哈希函數(shù)計算時使用。關于哈希函數(shù)在運行時，Go 會檢測 cpu 是否支持 aes，支持則使用 aes hash，否則使用 memhash。位于路徑：src/runtime/alg.go 下的 alginit() 函數(shù)。
• 根據(jù)參數(shù) hint計算需要的桶數(shù)。
• 根據(jù)桶的數(shù)量創(chuàng)建一個連續(xù)的空間來存儲桶的數(shù)據(jù)。

大體上就是這么一個過程，關于源碼中的一些檢查項這里就不多廢話了，并且源碼注釋也寫的很清楚了。

下面這個圖就是一個 map 的主要相關存儲結構：

map 主要結構

3.2 定位 key

一個 map 初始化后基本的結構我們已經(jīng)知道了，接下來就是我們在這個結構中如何添加一個 key 對應的 value。

我們再看一遍每一個桶的結構：

type bmap struct { 
    topbits  [8]uint8 
    keys     [8]keytype 
    values   [8]valuetype 
    pad      uintptr 
    overflow uintptr 
} 

這里的 keys 與 values 字段就是存儲 key 和 value 的真正內存的地方，我們可以看到這里每個都是長度為8的數(shù)組，也就是說一個桶內存了兩個數(shù)組，一個存的是 key 列表，另一個是 value 列表，并且每個數(shù)據(jù)的大小都是8。那么當有第9個元素入桶時，我們就需要創(chuàng)建新的桶了，也就是 overflow 字段指向一個新的 bucket(bmap 結構)。

還有一個字段就是 topbits，也是一個長度為8的數(shù)組，其實看到這里我們應該想到，這三個數(shù)組長度都相同應該有對應關系了，也就是說 topbits 數(shù)組中第一個元素是一個8位大小，我們稱之為 高8位，這是我們再回想一下哈希函數(shù)，我們的哈希函數(shù)的結果取高8位，然后存入 topbits 數(shù)組，然后其在數(shù)組的索引我們稱之為i，那么我們就可以在 keys 和 values 數(shù)組的第i個位置存儲數(shù)據(jù)了。

上面是在已知一個桶中添加或者修改元素，那么我們該如何查找這個桶呢?

我們知道在 hmap 中有 buckets 字段，其指向 []bmap 數(shù)組。那么我們就需要通過 key 找到對應的 bmap 在 []bmap 中的位置。關于此處的計算大家感興趣的可以看一下源碼，這里就不詳細說每一個運算符都是怎么運算的，只說一下大致的流程：hmap 中有一個 B 字段，根據(jù)字段 B 的值，以及 key 的 hash 值，計算出目標桶在 []bmap 中的位置(其實就是取了 key 的哈希的后幾位作為數(shù)組的下標即可)。

現(xiàn)在我們根據(jù)一個 key 可以在 hmap 中的 buckets 字段找到對應的 bmap 對象，同時在 bmap 中根據(jù) key 哈希的高八位找到其在 keys 與 values 數(shù)組中的位置。這里我們還沒有說如果有 overflow 的情況。其實不說想必大家也能猜到了，在我們定位到一個 bmap 時，是不知道其一共有多少個溢出桶的：假設我們有桶 A，A 的 overflow 字段指向桶 B，B 的 overflow 指向桶 C，假設我們此時根據(jù) key 的哈希找到了桶 A，然后 for 循環(huán)遍歷桶中的 topbits 數(shù)組，如果某個高8位的哈希與我們想找的 key 的哈希的高8位相同，就去對應位置的 keys 數(shù)組查找對應的 key1，假如 key1 與我們的目標 key 相等，那么直接返回其對應 values 數(shù)組中的 value 即可。如果key1 與我們的目標 key 不相等，接著變量桶中其他元素。假設桶中所有元素遍歷后沒有找到相同的 key，那么此時就要到 A 桶的溢出桶 B 再去遍歷，如果 B 中依然找不到再去桶 C 中查找。此時大家可以思考一下如果是你，你會如何實現(xiàn)這部分代碼呢?你實現(xiàn)的和 Go 的源碼是否一樣呢?

當我們知道了上面定位 key 的過程，對于 key 的增刪改查過程也就不多說了，因為核心的我們已經(jīng)掌握了，現(xiàn)在大家可以去看一下源碼了，這時大家看源碼必定事半功倍。