Go 語言 map 解析之 key 的定位核心流程
1 哈希表
哈希表屬于編程中比較常見的數據結構之一，基本上所有的語言都會實現數組和哈希表這兩種結構，Hash table 的歷史是比較悠遠的，我們在編程時也是離不開的，這種數據結構的作用其實很簡單，就是我們可以根據一個 key 可以查找到對應的 value，也就是說這種數據結構存儲的是鍵值對的“列表”。
1.1 原理
首先哈希表中第一個點就是哈希函數，也就是我們需要一個函數，根據我們的 key 計算出一個值，然后根據這個值可以直接找到對應的 value。因為我們的哈希表的一個作用就是 O(1) 復雜度找到 key 對應的 value。
完美的哈希函數是可以做到將任何一個 key 值都可以計算出一個唯一且固定大小的值，不幸的是目前世界上還沒有這種完美的哈希函數。因此我們需要解決的另外一個問題就是哈希沖突的解決。
1.1.1 哈希沖突
假如我們有兩個不同的 key，通過哈希函數計算出的結果相同，那么我們是不能認為這兩個 key 在 map 中是相同的，也就是如果出現了這種情況，我們的 map 結構是可以解決這個問題的。目前解決辦法有很多，這里只說三個比較常見的解決方案：
開放地址法(Open Addressing)：
- 寫入時：假如 key Alice 與 Bob 通過哈希函數計算出結果沖突。當 map 中已經存在 key Alice，再寫入 key 為 Bob時，發現哈希結果對應位置已經存在 Alice，此時在 Alice 位置之后再尋找位置，一直找到為空的位置，將 Bob 寫入。
- 讀取時：此時 map 中已存在 key Alice、Bob，且哈希結果相同，此時想查找 Bob 對應 value 時，先計算 Bob 哈希結果，再通過哈希結果在 map 中查找位置，此時由于和 Alice 哈希結果相同，并且 Alice 先于 Bob 存入 map，所以會直接找到 Alice 的位置，發現 key 是 Alice 不是 Bob，接著在 Alice 位置后面查找，直到找到 key Bob 或者找到空。
再哈希法(Re-Hashing)：
- 設計多個哈希函數，假如 Alice 與 Bob 計算哈希結果相同，那么用另外一個哈希函數來計算 Bob 的哈希值，這種方式來解決哈希沖突。
- 鏈地址法(Separate Chaining)：
- 此方法將同一個哈希結果對應的位置想象成一個桶，如果多個 key 對應哈希結果相同，那么都放到同一個桶中，并且桶中元素使用鏈表結構存儲。
- 寫入時：Alice 于 Bob 哈希結果相同，此時 map 已經有 Alice，再寫入 Bob 時，發現對應哈希結果位置已經存在了 Alice，此時在當前桶中的 Alice 后鏈接一個 Bob，此時哈希結果對應的桶就存在了兩個元素 Alice 與 Bob。
- 讀取時：讀取 Bob key 時，發現對應哈希結果的桶中第一個元素是 Alice，此時在桶中按鏈表順序挨個查找，直到 key 相同或者空。
- 裝載因子：此方案存在一個問題，當一個桶中元素過多時，其復雜度將增加，極端情況下就變成了鏈表。所以我們會限制在一個桶中元素的個數。這樣在一個桶中元素過多時，需要生成新的桶。
- 裝載因子 = 元素總量 / 桶總個數
在 Go 語言中，map 使用的是鏈地址法。
2 Go 中 map分析
2.1 map 數據結構
map 的源碼位于 src/runtime/map.go 文件中，結構如下：
- type hmap struct {
- count int // 當前 map 中元素數量
- flags uint8
- B uint8 // 當前 buckets 數量，2^B 等于 buckets 個數
- noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
- hash0 uint32 // 哈希種子
- buckets unsafe.Pointer // buckets 數組指針
- oldbuckets unsafe.Pointer // 擴容時保存之前 buckets 數據。
- nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
- extra *mapextra // optional fields
- }
- // 每一個 bucket 的結構，即 hmap 中 buckets 指向的數據。
- type bmap struct {
- tophash [bucketCnt]uint8
- }
- // 編譯期間重構此結構
- type bmap struct {
- topbits [8]uint8
- keys [8]keytype
- values [8]valuetype
- pad uintptr
- overflow uintptr
- }
關于 hmap 的結構這里已經將很多重要的字段列出來了，其中最重要的就是 buckets 這一部分，根據上面我們說過的鏈地址法可知，對同一類 key (哈希結果相同)放入相同的桶中。此時每一個桶還有另外一個字段 overflow，也就是當前桶裝不下就會再創建新的桶。這就是 Go 中 map 的主要實現方法，更詳細的部分我們接下來一點一點聊。
2.2 源碼
map 的源碼位于 src/runtime/map.go 文件中。關于 map 的操作的具體實現在這里都可以找到：
- 創建 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)
本篇文章不會帶大家將源碼通讀一遍，但是會將其實現過程以圖或者文字形式分析出來，但是建議大家有時間可以根據本篇文章的內容再去自己讀一遍源碼，如果我這里將所有源碼都解釋一遍，估計朋友們很快就又忘記了，還不如記住實現流程。所以本文更多的是講 map 每個操作的過程圖，以及其中的部分要點，而不是將源碼一行一行的解釋出來。
3. 圖解 map
3.1 創建map
我們已經知道 map 的數據結構，其實 map 的初始化也無非就是填充各個字段而已：
- 第一個就是 hash0 字段，此處會隨機給一個種子，用在哈希函數計算時使用。關于哈希函數在運行時，Go 會檢測 cpu 是否支持 aes，支持則使用 aes hash，否則使用 memhash。位于路徑：src/runtime/alg.go 下的 alginit() 函數。
- 根據參數 hint計算需要的桶數。
- 根據桶的數量創建一個連續的空間來存儲桶的數據。
大體上就是這么一個過程，關于源碼中的一些檢查項這里就不多廢話了，并且源碼注釋也寫的很清楚了。
下面這個圖就是一個 map 的主要相關存儲結構：
map 主要結構
3.2 定位 key
一個 map 初始化后基本的結構我們已經知道了，接下來就是我們在這個結構中如何添加一個 key 對應的 value。
我們再看一遍每一個桶的結構：
- type bmap struct {
- topbits [8]uint8
- keys [8]keytype
- values [8]valuetype
- pad uintptr
- overflow uintptr
- }
這里的 keys 與 values 字段就是存儲 key 和 value 的真正內存的地方，我們可以看到這里每個都是長度為8的數組，也就是說一個桶內存了兩個數組，一個存的是 key 列表，另一個是 value 列表，并且每個數據的大小都是8。那么當有第9個元素入桶時，我們就需要創建新的桶了，也就是 overflow 字段指向一個新的 bucket(bmap 結構)。
還有一個字段就是 topbits，也是一個長度為8的數組，其實看到這里我們應該想到，這三個數組長度都相同應該有對應關系了，也就是說 topbits 數組中第一個元素是一個8位大小，我們稱之為 高8位，這是我們再回想一下哈希函數，我們的哈希函數的結果取高8位，然后存入 topbits 數組，然后其在數組的索引我們稱之為i，那么我們就可以在 keys 和 values 數組的第i個位置存儲數據了。
上面是在已知一個桶中添加或者修改元素，那么我們該如何查找這個桶呢?
我們知道在 hmap 中有 buckets 字段，其指向 []bmap 數組。那么我們就需要通過 key 找到對應的 bmap 在 []bmap 中的位置。關于此處的計算大家感興趣的可以看一下源碼，這里就不詳細說每一個運算符都是怎么運算的，只說一下大致的流程：hmap 中有一個 B 字段，根據字段 B 的值，以及 key 的 hash 值，計算出目標桶在 []bmap 中的位置(其實就是取了 key 的哈希的后幾位作為數組的下標即可)。
現在我們根據一個 key 可以在 hmap 中的 buckets 字段找到對應的 bmap 對象，同時在 bmap 中根據 key 哈希的高八位找到其在 keys 與 values 數組中的位置。這里我們還沒有說如果有 overflow 的情況。其實不說想必大家也能猜到了，在我們定位到一個 bmap 時，是不知道其一共有多少個溢出桶的：假設我們有桶 A，A 的 overflow 字段指向桶 B，B 的 overflow 指向桶 C，假設我們此時根據 key 的哈希找到了桶 A，然后 for 循環遍歷桶中的 topbits 數組，如果某個高8位的哈希與我們想找的 key 的哈希的高8位相同，就去對應位置的 keys 數組查找對應的 key1，假如 key1 與我們的目標 key 相等，那么直接返回其對應 values 數組中的 value 即可。如果key1 與我們的目標 key 不相等，接著變量桶中其他元素。假設桶中所有元素遍歷后沒有找到相同的 key，那么此時就要到 A 桶的溢出桶 B 再去遍歷，如果 B 中依然找不到再去桶 C 中查找。此時大家可以思考一下如果是你，你會如何實現這部分代碼呢?你實現的和 Go 的源碼是否一樣呢?
當我們知道了上面定位 key 的過程，對于 key 的增刪改查過程也就不多說了，因為核心的我們已經掌握了，現在大家可以去看一下源碼了，這時大家看源碼必定事半功倍。
