Golang map實現原理深入分析

簡介

本文主要通過探究在golang 中map的數據結構及源碼實現來學習和瞭解map的特性,共包含map的模型探究、存取、擴容等內容。歡迎大傢共同討論。

Map 的底層內存模型

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

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

B 是 buckets 數組的長度的對數, 即 bucket 數組的長度是 2^B。bucket 的本質上是一個指針,指向瞭一片內存空間,其指向的 struct 如下所示:

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

但這隻是表面(src/runtime/hashmap.go)的結構,編譯期間會給它加料,動態地創建一個新的結構:

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr        // 內存對齊使用,可能不需要
    overflow uintptr        // 當bucket 的8個key 存滿瞭之後
}

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

Map 的存與取

在 map 中存與取本質上都是在進行一個工作, 那就是:

查詢當前 k/v 應該存儲的位置。

賦值/取值, 所以我們理解瞭 map 中 key 的定位我們就理解瞭存取。

底層代碼

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // map 為空,或者元素數為 0,直接返回未找到
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0]), false
    }
    // 不支持並發讀寫
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    // 根據hash 函數算出hash值,註意key的類型不同可能使用的hash函數也不同
    hash := t.hasher(key, uintptr(h.hash0))
    // 如果 B = 5,那麼結果用二進制表示就是 11111 , 返回的是B位全1的值
    m := bucketMask(h.B)
    // 根據hash的後B位,定位在bucket數組中的位置
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
    // 當 h.oldbuckets 非空時,說明 map 發生瞭擴容
    // 這時候,新的 buckets 裡可能還沒有老的內容
    // 所以一定要在老的裡面找,否則有可能發生“消失”的詭異現象
    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 個元素後,就再也放不下瞭,這時候會創建新的 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
            }
            // 根據內存結構定位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 一樣都是在初始化時首先申請較小的內存空間,在 map 的不斷存入的過程中,動態的進行擴容。擴容共有兩種,增量擴容與等量擴容(重新排列並分配內存)。下面我們來瞭解一下擴容的觸發方式:

負載因子超過閾值,源碼裡定義的閾值是 6.5。(觸發增量擴容)

overflow 的 bucket 數量過多:當 B 小於 15,也就是 bucket 總數 2^B 小於 2^15 時,如果 overflow 的 bucket 數量超過 2^B;當 B >= 15,也就是 bucket 總數 2^B 大於等於 2^15,如果 overflow 的 bucket 數量超過 2^15。(觸發等量擴容)

第一種情況

第二種情況

Map的有序性

先說結論,在 golang 中 map 是無序的,準確的說是無法嚴格保證順序的, 從上面的源碼中我們可以知道,golang 中 map 在擴容後,可能會將部分 key 移至新內存,由於在擴容搬移數據過程中,並未記錄原數據位置, 並且在 golang 的數據結構中也並未保存數據的順序,所以那麼這一部分在擴容後實際上就已經是無序的瞭。

遍歷的過程,其實就是按順序遍歷內存地址,同時按順序遍歷內存地址中的 key。但這時已經是無序的瞭。但是如果我就一個 map,我保證不會對 map 進行修改刪除等操作,那麼按理說沒有擴容就不會發生改變。但也是因為這樣,GO 才在源碼中 但是有一個有趣的現象,就算不對 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 的順序隨機化,用來防止使用者用來順序遍歷。

而這是有風險的代碼,在 GO 的嚴格語法規則下,是堅決不提倡的。所以我們在使用 map 時一定要記得其是無序的,不要依賴其順序。

Map 的並發

首先我們大傢都知道,在 golang 中 map 並不是一個並發安全的數據結構,當幾個 goruotine 同時對一個 map 進行讀寫操作時,就會出現並發寫問題:fatal error: concurrent map writes。但是為什麼 map 是不支持並發安全的呢, 主要是因為成本與效益。

官方答復原因如下:

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

性能場景考慮:若是隻是為少數程序增加安全性,導致 map 所有的操作都要處理 mutex,將會降低大多數程序的性能。同時 golang 提供瞭並發安全的 sync map。

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

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

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

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

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

到此這篇關於Golang map實現原理深入分析的文章就介紹到這瞭,更多相關Golang map內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!

推薦閱讀: