Golang Map 內部實現

【導讀】golang 的 map 類型非常易用，它的實現你瞭解過嗎？本文結合了 map 源碼，幫你理解 map 底層實現。

類型

golang 中的 map 是一個指針。當執行語句 make(map[string]string) 的時候，其實是調用了 makemap 函數：

// file: runtime/hashmap.go:L222
func makemap(t *maptype, hint64, h *hmap, bucket unsafe.Pointer) *hmap

顯然，makemap 返回的是指針。

數據結構

hashmap

// hash map
type hmap struct {
    // 元素的個數 == len()返回的值，必須放在第一個位置因爲 len函數需要使用
    count     int

    // map標記:
    // 1. key和value是否包指針
    // 2. 是否正在擴容
    // 3. 是否是同樣大小的擴容
    // 4. 是否正在 `range`方式訪問當前的buckets
    // 5. 是否有 `range`方式訪問舊的bucket
    flags     uint8
    B         uint8  // log_2(B) == bucket數量
    noverflow uint16 // overflow bucket的數量，是個近似值
    hash0     uint32 // hash種子

    buckets    unsafe.Pointer // bucket slice指針，如果count == 0，這裏的值爲 nil
    oldbuckets unsafe.Pointer // bucket slice指針，僅當在擴容的時候不爲nil
    nevacuate  uintptr        // 擴容時已經移到新的map中的bucket數量

    // 當key和value的類型不包含指針的時候，key和value就會做inline處理(怎麼處理的)
    // 保證overflow的bucket活着，不被gc回收
    overflow *[2]*[]*bmap
}

bucket

每個bucket固定包含 8 個 key 和 value。實現上面是一個固定的大小連續內存塊，分成四部分：

每個條目的狀態
8 個 key 值
8 個 value 值
指向下個 bucket 的指針

數據結構定義如下：

// bucket
type bmap struct {
        // 每個條目的狀態，tophash[0]表示當前bucket中的條目是否已經完全移到新的bucket中去了
        tophash [bucketCnt]uint8
        // keys
        // values
        // Followed by an overflow pointer.
}

條目狀態

0 空，可以被使用
1 空，bucket 中的內容已經被移到了新的 bucket 中
2 該條目已經被移到了新的 bucket，該 bucket 的位置在處在前半部分
3 該條目已經被移到了新的 bucket，該 bucket 的位置在處在後半部分
其他大於等於 4 的值，來自 key 的 hash 值的最高 8 位，如果高 8 位值小於 4，則加 4

第一個條目狀態

bucket 的第一個條目tophash[0]用來標識 bucket 中的條目是否已經全部被移到了新的 bucket 中去了， 1-3 表示已經移動完。

內存佈局

   ----+-----------------+ -.
   ^   |     bucket0     |  |------> +------------+
   |   +-----------------+ -'        | tophash0-7 |
2^h.B  |     .......     |           +------------+
   |   +-----------------+           |   key0-7   |
   v   | bucket2^h.B - 1 |           +------------+
   ----+-----------------+           |  value0-7  |
                                     +------------+ -.
                                     |overflow_ptr|  |-----> new bucket address
                                     +------------+ -'

選擇這樣的佈局的好處：由於對齊的原因，key0/value0/key1/value1 … 這樣的形式可能需要更多的補齊空間，比如 map[int64]int8 ，1 字節的 value 後面需要補齊 7 個字節才能保證下一個 key 是 int64 對齊的。

裝載因子

裝載因子決定 map 的資源使用率以及性能高低，在實現 map 時，考慮四個方面：

%overflow：擁有 overflow 的 bucket 的百分比
bytes/entry: 每個 key/value 的額外開銷
hitprobe: 查找存在的 key 時需要檢查的條目數量
missprobe: 查找不存在的 key 是需要檢查的條目數量

其測試數據如下：

裝載因子 %overflow bytes/entry hitprobe missprobe
6.5 20.90 10.79 4.25 6.5

hash 函數

map 中的 key 對應着一個 hash 函數，用於定位 bucket。在 golang 的 hash 函數是固定的，用戶無法修改。golang 中的預定義基本類型，像 int32/int64/string/interface 等等都有一個 hash 函數與之對應，代碼在 runtime/alg.go 中。對於 struct / 數組 / slice，如果它每個字段或者元素都是有 hash 函數，那麼該類型就有 hash 函數，hash 值由每個字段的 hash 值來定義，代碼在reflect/type.go函數StructOf中。

注：map 是不能作爲 key 的。

擴容

當進行添加元素的操作時，如果超過裝載因子，或者 overflow 的 bucket 數量超出閾值，就會觸發擴容的操作。如果是因爲 overflow 的 bucket 數量過多引起的，map 的容量不會擴大，不然就擴大爲原來的大小的兩倍。

在實現擴容的時候，會先爲需要的 bucket 分配新內存，然後把舊的 bucket 保存起來，再把舊的內容移到新的 bucket 中去。

線程安全

map 是線程不安全的。但是在實現中有很多關於併發訪問的代碼，比如

在迭代的時候會做是否正在擴容

添加數據的時候是否有其他數據正在寫，有的話會 panic

既然不是線程安全，爲啥要做這樣的檢查，不檢查的話可以簡化代碼提高性能。檢查的好處就是告知提醒用戶併發訪問了 map，但是這個檢查也不是百分之一百的檢測到所有的併發訪問。

鍵值 NaN

NaN 的 hash 值是隨機 (原因)，也就是說每次計算 hash 值都有可能是不一樣的。這個跟 python/java 等其他語言有比較大的差別。

正是因爲這樣有了以下幾個有趣的事情：

當 NaN 作爲 key 的時候，爲了保持 hash 值的不變性，利用 tophash 的最低位來判斷是放在擴容以後 bucket 的上半部分還是下半部分用 NaN 做 key 取數據時永遠也取不到，用 for 迭代 map 是唯一一種訪問 key 爲NaN 的內容的方式

迭代

for 語句迭代 map，在會調用函數 mapiterinit 做初始化工作：

隨機挑選一個起始位置開始迭代：a. bucket隨機選一個，b. bucket中的起始條目也是隨機的初始化 overflow，目的是爲了防止那些內聯的數據被 gc，導致迭代失敗

每次獲取一個元素的時候調用函數mapiternext

轉自：zjykzk

zjykzk.github.io/post/cs/golang/map/

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

類型