簡介

本文主要通過探究在golang 中map的數(shù)據(jù)結構及源碼實現(xiàn)來學習和了解map的特性，共包含map的模型探究、存取、擴容等內(nèi)容。歡迎大家共同討論。

Map 的底層內(nèi)存模型

在 golang 的源碼中表示 map 的底層 struct 是 hmap，其是 hashmap 的縮寫

type hmap struct {   // map中存入元素的個數(shù)， golang中調(diào)用len(map)的時候直接返回該字段   count     int   // 狀態(tài)標記位，通過與定義的枚舉值進行&操作可以判斷當前是否處于這種狀態(tài)   flags     uint8   B         uint8  // 2^B 表示bucket的數(shù)量， B 表示取hash后多少位來做bucket的分組   noverflow uint16 // overflow bucket 的數(shù)量的近似數(shù)   hash0     uint32 // hash seed （hash 種子） 一般是一個素數(shù)   buckets    unsafe.Pointer // 共有2^B個 bucket ，但是如果沒有元素存入，這個字段可能為nil   oldbuckets unsafe.Pointer // 在擴容期間，將舊的bucket數(shù)組放在這里， 新buckets會是這個的兩倍大   nevacuate  uintptr        // 表示已經(jīng)完成擴容遷移的bucket的指針， 地址小于當前指針的bucket已經(jīng)遷移完成   extra *mapextra // optional fields}

B 是 buckets 數(shù)組的長度的對數(shù)， 即 bucket 數(shù)組的長度是 2^B。bucket 的本質(zhì)上是一個指針，指向了一片內(nèi)存空間，其指向的 struct 如下所示：

// A bucket for a Go map.type bmap struct {   tophash [bucketCnt]uint8}

但這只是表面(src/runtime/hashmap.go)的結構，編譯期間會給它加料，動態(tài)地創(chuàng)建一個新的結構：

type bmap struct {    topbits  [8]uint8    keys     [8]keytype    values   [8]valuetype    pad      uintptr        // 內(nèi)存對齊使用，可能不需要    overflow uintptr        // 當bucket 的8個key 存滿了之后}

bmap 就是我們常說的“桶”的底層數(shù)據(jù)結構， 一個桶中可以存放最多 8 個 key/value, map 使用 hash 函數(shù) 得到 hash 值決定分配到哪個桶， 然后又會根據(jù) hash 值的高 8 位來尋找放在桶的哪個位置 具體的 map 的組成結構如下圖所示：

Map 的存與取

在 map 中存與取本質(zhì)上都是在進行一個工作， 那就是:

1. 查詢當前 k/v 應該存儲的位置。
2. 賦值/取值， 所以我們理解了 map 中 key 的定位我們就理解了存取。

底層代碼

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {    // map 為空，或者元素數(shù)為 0，直接返回未找到    if h == nil || h.count == 0 {        return unsafe.Pointer(&zeroVal[0]), false    }    // 不支持并發(fā)讀寫    if h.flags&hashWriting != 0 {        throw("concurrent map read and map write")    }    // 根據(jù)hash 函數(shù)算出hash值，注意key的類型不同可能使用的hash函數(shù)也不同    hash := t.hasher(key, uintptr(h.hash0))    // 如果 B = 5，那么結果用二進制表示就是 11111 ， 返回的是B位全1的值    m := bucketMask(h.B)    // 根據(jù)hash的后B位，定位在bucket數(shù)組中的位置    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))    // 當 h.oldbuckets 非空時，說明 map 發(fā)生了擴容    // 這時候，新的 buckets 里可能還沒有老的內(nèi)容    // 所以一定要在老的里面找，否則有可能發(fā)生“消失”的詭異現(xiàn)象    if c := h.oldbuckets; c != nil {        if !h.sameSizeGrow() {            // 說明之前只有一半的 bucket，需要除 2            m >>= 1        }        oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))        if !evacuated(oldb) {            b = oldb        }    }    // tophash 取其高 8bit 的值    top := tophash(hash)    // 一個 bucket 在存儲滿 8 個元素后，就再也放不下了，這時候會創(chuàng)建新的 bucket，掛在原來的 bucket 的 overflow 指針成員上    // 遍歷當前bucket的所有鏈式bucket    for ; b != nil; b = b.overflow(t) {        // 在bucket的8個位置上查詢        for i := uintptr(0); i < bucketCnt; i++ {            // 如果找到了相等的 tophash，那說明就是這個 bucket 了            if b.tophash[i] != top {                continue            }            // 根據(jù)內(nèi)存結構定位key的位置            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))            if t.indirectkey {                k = *((*unsafe.Pointer)(k))            }            // 校驗找到的key是否匹配            if t.key.equal(key, k) {                // 定位v的位置                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))                if t.indirectvalue {                    v = *((*unsafe.Pointer)(v))                }                return v, true            }        }    }    // 所有 bucket 都沒有找到，返回零值和 false    return unsafe.Pointer(&zeroVal[0]), false}

尋址過程

Map 的擴容

在 golang 中 map 和 slice 一樣都是在初始化時首先申請較小的內(nèi)存空間，在 map 的不斷存入的過程中，動態(tài)的進行擴容。擴容共有兩種，增量擴容與等量擴容（重新排列并分配內(nèi)存）。下面我們來了解一下擴容的觸發(fā)方式：

1. 負載因子超過閾值，源碼里定義的閾值是 6.5。(觸發(fā)增量擴容)
2. overflow 的 bucket 數(shù)量過多：當 B 小于 15，也就是 bucket 總數(shù) 2^B 小于 2^15 時，如果 overflow 的 bucket 數(shù)量超過 2^B；當 B >= 15，也就是 bucket 總數(shù) 2^B 大于等于 2^15，如果 overflow 的 bucket 數(shù)量超過 2^15。（觸發(fā)等量擴容）

第一種情況

第二種情況

Map 的有序性

先說結論，在 golang 中 map 是無序的，準確的說是無法嚴格保證順序的， 從上面的源碼中我們可以知道，golang 中 map 在擴容后，可能會將部分 key 移至新內(nèi)存，由于在擴容搬移數(shù)據(jù)過程中，并未記錄原數(shù)據(jù)位置， 并且在 golang 的數(shù)據(jù)結構中也并未保存數(shù)據(jù)的順序，所以那么這一部分在擴容后實際上就已經(jīng)是無序的了。

遍歷的過程，其實就是按順序遍歷內(nèi)存地址，同時按順序遍歷內(nèi)存地址中的 key。但這時已經(jīng)是無序的了。但是如果我就一個 map，我保證不會對 map 進行修改刪除等操作，那么按理說沒有擴容就不會發(fā)生改變。但也是因為這樣，GO 才在源碼中 但是有一個有趣的現(xiàn)象，就算不對 map 進行插入刪除等操作致使其擴容，其在遍歷過程中仍是無序的。

objMap := make(map[string]int)for i := 0; i < 5; i++ {   objMap[strconv.Itoa(i)] = i}for i := 0 ; i < 5; i ++ {   var valStr1, valStr2 string   for k, v := range objMap {      fmt.Println(k)      fmt.Println(v)      valStr1 += k   }   for k, v := range objMap {      fmt.Println(k)      fmt.Println(v)      valStr2 += k   }   fmt.Println(valStr1 == valStr2)   if valStr1 != valStr2 {      fmt.Println("not equal")   }}fmt.Println("end")

?以上的運行結果是

不難看出，即使不對 map 進行擴容，在多次遍歷時也是無序的，這是因為 golang 官方在設計時故意加上隨機的元素，將遍歷 map 的順序隨機化，用來防止使用者用來順序遍歷。

依賴 map 的順序進行遍歷，這是有風險的代碼，在 GO 的嚴格語法規(guī)則下，是堅決不提倡的。所以我們在使用 map 時一定要記得其是無序的，不要依賴其順序。

Map 的并發(fā)

首先我們大家都知道，在 golang 中 map 并不是一個并發(fā)安全的數(shù)據(jù)結構，當幾個 goruotine 同時對一個 map 進行讀寫操作時，就會出現(xiàn)并發(fā)寫問題：fatal error: concurrent map writes。但是為什么 map 是不支持并發(fā)安全的呢， 主要是因為成本與效益。

官方答復原因如下：

• 典型使用場景：map 的典型使用場景是不需要從多個 goroutine 中進行安全訪問。
• 非典型場景（需要原子操作）：map 可能是一些更大的數(shù)據(jù)結構或已經(jīng)同步的計算的一部分。

性能場景考慮：若是只是為少數(shù)程序增加安全性，導致 map 所有的操作都要處理 mutex，將會降低大多數(shù)程序的性能。同時 golang 提供了并發(fā)安全的 sync map。

， // 不支持并發(fā)讀寫    if h.flags&hashWriting != 0 {        throw("concurrent map read and map write")    }

但是我們又有疑問了，為什么 golang map 并發(fā)沖突了不拋一個 error 出來，或者 panic 掉，而是要讓程序 panic，選擇讓程序 crash 崩潰掉。這里是 golang 官方出于權衡風險和 map 使用復雜度場景考慮的，首先 map 在官方中就明確表示不支持并發(fā)讀寫， 所以并發(fā)對 map 進行讀寫操作本身就是不正確的。

場景假設一：如果 map 選擇在寫入或者讀取時增加 error 返回值，會導致程序在使用 map 時就無法像現(xiàn)在一樣，需要額外的捕獲并判斷 err。

場景假設二：如果 map 選擇 panic（可被 recover），此時如果出現(xiàn)并發(fā)寫入數(shù)據(jù)的場景，就會導致走進 recover 中，如果沒有對這種場景進行特殊處理，就會導致 map 中存在臟數(shù)據(jù)，此時程序在使用 map 時就會引發(fā)不可預知的錯誤，此時排查起來也是很難找到問題的根因的。

所以 golang 在考慮了這些場景后，選擇明確的拋出 crash 崩潰異常，使得風險被提前暴露。可以明確的定位到問題點。綜上所述我們在使用 map 時，已經(jīng)要嚴格保障其是在單線程內(nèi)使用的，如果有多線程場景，建議使用 sync map 。