1 哈希表

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

1.1 原理

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

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

1.1.1 哈希沖突

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

開放地址法(Open Addressing)：

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

再哈希法(Re-Hashing)：

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

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

2 Go 中 map分析

2.1 map 數(shù)據(jù)結(jié)構(gòu)

map 的源碼位于 src/runtime/map.go 文件中，結(jié)構(gòu)如下：

type hmap struct { 
    count     int // 當(dāng)前 map 中元素數(shù)量 
    flags     uint8 
    B         uint8  // 當(dāng)前 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 // 擴(kuò)容時保存之前 buckets 數(shù)據(jù)。 
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated) 
 
    extra *mapextra // optional fields 
} 
 
// 每一個 bucket 的結(jié)構(gòu)，即 hmap 中 buckets 指向的數(shù)據(jù)。 
type bmap struct { 
    tophash [bucketCnt]uint8 
} 
 
// 編譯期間重構(gòu)此結(jié)構(gòu) 
type bmap struct { 
    topbits  [8]uint8 
    keys     [8]keytype 
    values   [8]valuetype 
    pad      uintptr 
    overflow uintptr 
} 

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

2.2 源碼

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

• 創(chuàng)建 map：func makemap(t *maptype, hint int, h *hmap) *hmap
• 訪問某個 key：
• 返回結(jié)果只包括 value：func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
• 返回結(jié)果包括 bool 結(jié)果：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ù)本篇文章的內(nèi)容再去自己讀一遍源碼，如果我這里將所有源碼都解釋一遍，估計朋友們很快就又忘記了，還不如記住實現(xiàn)流程。所以本文更多的是講 map 每個操作的過程圖，以及其中的部分要點，而不是將源碼一行一行的解釋出來。

3. 圖解 map

3.1 創(chuàng)建map

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

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

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

下面這個圖就是一個 map 的主要相關(guān)存儲結(jié)構(gòu)：

map 主要結(jié)構(gòu)

3.2 定位 key

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

我們再看一遍每一個桶的結(jié)構(gòu)：

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

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

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

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

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

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

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