map底層原理刨析

Go 語言內置了 map 數(shù)據(jù)結構, map 的底層便是一個 HashTable, Go 語言的 map 的使用非常簡易, 但其內部實現(xiàn)相對比較復雜, Go 語言的 Runtime 使用了多個數(shù)據(jù)結構來實現(xiàn) HashTable, 本文完整剖析 Golang 對于 HashTable 的底層實現(xiàn)

1. Go map 的底層結構

// Map contains Type fields specific to maps.
type Map struct {
    Key  *Type // Key type
    Elem *Type // Val (elem) type

    Bucket *Type // internal struct type representing a hash bucket
    Hmap   *Type // internal struct type representing the Hmap (map header object)
    Hiter  *Type // internal struct type representing hash iterator state
}

前兩個字段為key和value，Type由于 go map 支持多種數(shù)據(jù)類型, go 會在編譯期推斷其具體的數(shù)據(jù)類型,Bucket 是哈希桶,Hmap 表征了 map 底層使用的 HashTable 的元信息, 如當前 HashTable 中含有的元素數(shù)據(jù)、桶指針等, Hiter 是用于遍歷 go map 的數(shù)據(jù)結構, 將在下文中討論

Hmap數(shù)據(jù)結構

// A header for a Go map.
type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}

• Count: map目前的元素數(shù)目，在使用len獲取map長度時，由于獲取的是該字段，所以算法時間度為O(1).
• Flags : 標志 map 的狀態(tài), 如 map 當前正在被遍歷或正在被寫入
• B : 是哈希桶數(shù)目以 2 為底的對數(shù),在 go map 中, 哈希桶的數(shù)目都是 2 的整數(shù)次冪(這樣設計的好處是可以是用位運算來計算取余運算的值, 即 N mod M = N & (M-1)),
• Noverflow : 是溢出桶的數(shù)目, 這個數(shù)值不是恒定精確的, 當其 B>=16 時為近似值
• Hash0:是隨機哈希種子, map創(chuàng)建時調用 fastrand 函數(shù)生成的隨機數(shù), 設置的目的是為了降低哈希沖突的概率
• Buckets :是指向當前哈希桶的指針
• Oldbuckets :是當桶擴容時指向舊桶的指針
• Nevacuate :是當桶進行調整時指示的搬遷進度, 小于此地址的 buckets 是以前搬遷完畢的哈希桶,
• Mmapextra :則是表征溢出桶的變量

我們首先來看一下bmap,即哈希桶的結構

type bmap struct {
    topbits  [8]uint8     // 鍵哈希值的高 8 位
    keys     [8]keytype   // 哈希桶中的所有鍵
    elems    [8]elemtype  // 哈希桶中的所有值
    //pad      uintptr(新的 go 版本已經(jīng)移除了該字段, 我未具體了解此處的 change detail, 之前設置該字段是為了在 nacl/amd64p32 上的內存對齊)
    overflow uintptr  // 指向的溢出桶的地址的指針
}

topbits 是鍵哈希值的高 8 位, keys 存放了哈希桶中所有鍵, elems 存放了哈希桶中的所有值, overflow 是一個 uintptr 類型指針, 存放了所指向的溢出桶的地址,

go map 的每個哈希桶最多存放 8 個鍵值對, 當經(jīng)由哈希函數(shù)映射到該地址的元素數(shù)超過 8 個時, 會將新的元素放到溢出桶中, 并使用 overflow 指針鏈向這個溢出桶, 這里有一個需要注意的點是在哈希桶中, 鍵值之間并不是相鄰排列的, 這是為了保證內存對齊

MapExtra 數(shù)據(jù)結構

// mapextra holds fields that are not present on all maps.
type mapextra struct {
    // If both key and elem do not contain pointers and are inline, then we mark bucket
    // type as containing no pointers. This avoids scanning such maps.
    // However, bmap.overflow is a pointer. In order to keep overflow buckets
    // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
    // overflow and oldoverflow are only used if key and elem do not contain pointers.
    // overflow contains overflow buckets for hmap.buckets.
    // oldoverflow contains overflow buckets for hmap.oldbuckets.
    // The indirection allows to store a pointer to the slice in hiter.
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // nextOverflow holds a pointer to a free overflow bucket.
    nextOverflow *bmap
}

當一個 map 的 key 和 elem 都不含指針并且他們的長度都沒有超過 128 時(當 key 或 value 的長度超過 128 時, go 在 map 中會使用指針存儲), 該 map 的 bucket 類型會被標注為不含有指針, 這樣 gc 不會掃描該 map,

這會導致一個問題, bucket 的底層結構 bmap 中含有一個指向溢出桶的指針(uintptr類型, uintptr指針指向的內存不保證不會被 gc free 掉), 當 gc 不掃描該結構時, 該指針指向的內存會被 gc free 掉, 因此在 hmap 結構中增加了 mapextra 字段,

其中 overflow 是一個指向保存了所有 hmap.buckets 的溢出桶地址的 slice 的指針, 相對應的 oldoverflow 是指向保存了所有 hmap.oldbuckets 的溢出桶地址的 slice 的指針, 只有當 map 的 key 和 elem 都不含指針時這兩個字段才有效, 因為這兩個字段設置的目的就是避免當 map 被 gc 跳過掃描帶來的引用內存被 free 的問題, 當 map 的 key 和 elem 含有指針時, gc 會掃描 map, 從而也會獲知 bmap 中指針指向的內存是被引用的, 因此不會釋放對應的內存

hmap 結構相當于 go map 的頭, 它存儲了哈希桶的內存地址, 哈希桶之間在內存中緊密連續(xù)存儲, 彼此之間沒有額外的 gap, 每個哈希桶最多存放 8 個 k/v 對, 沖突次數(shù)超過 8 時會存放到溢出桶中, 哈希桶可以跟隨多個溢出桶, 呈現(xiàn)一種鏈式結構, 當 HashTable 的裝載因子超過閾值(6.5) 后會觸發(fā)哈希的擴容, 避免效率下降

Go map 的查找

當要 map 中查詢一個元素時, go 首先使用 key 和哈希表的 hash0, 即創(chuàng)建 map 時生成的隨機數(shù)做哈希函數(shù)運算得到哈希值, hmap 中的 B 表征了當前哈希表中的哈希桶數(shù)量, 哈希桶數(shù)量等于 2的B次方, 這里 go 使用了我們在第一節(jié)提到的除留余數(shù)法來計算得到相應的哈希桶, 因為桶的數(shù)量是 2 的整數(shù)次冪,

因此這里的取余運算可以使用位運算來替代, 將哈希值與桶長度減一做按位與即得到了對應的桶編號, 當前這里的桶編號是一個邏輯編號,

hmap 結構中存儲了哈希桶的內存地址, 在這個地址的基礎上偏移桶編號*桶長度便得到了對應的哈希桶的地址, 接下來進一步在該哈希桶中找尋 key 對應的元素,

在bmap中，比較的時候基于哈希值的高 8 位與桶中的 topbits 依次比較, 若相等便可以根據(jù) topbits 所在的相對位置計算出 key 所在的相對位置,

進一步比較 key 是否相等, 若 key 相等則此次查找過程結束, 返回對應位置上 elem, 若 key 不相等, 則繼續(xù)往下比較 topbits, 若當前桶中的所有 topbits 均與此次要找到的元素的 key 的哈希值的高 8 位不相等, 則繼續(xù)沿著 overflow 向后探查溢出桶, 重復剛剛的過程, 直到找到對應的 elem, 或遍歷完所有的溢出桶仍未找到目標元素, 此時返回該類型的零值

Go map 的插入/更新

go map 的插入和 go map 的查找過程類似, 在底層是調用 src/runtime/map.go#mapassign 函數(shù)實現(xiàn)的,

插入的具體過程是首先根據(jù) key 和哈希表的 hash0 采用哈希算法(aes/memhash)獲得哈希值, 然后使用哈希值與哈希桶數(shù)目使用位運算取余獲得哈希桶編號,

接下來依次遍歷哈希桶bmap中的 topbits 與此次計算的哈希值的高 8 位進行對比, 若遍歷到的 topbits 為空, 則臨時記錄下該位置, 然后繼續(xù)向后遍歷, 整個遍歷的優(yōu)先查找該 key 在 map 中是否存在,

若找到哈希值的高 8 位與哈希桶的 topbits 相等則進一步比較對應位置的 key, 若 key 也相等, 則此時更新該 key 對應的 elem, 在源碼中當更新完成后使用 goto 語句直接跳轉到函數(shù)最后,更新 hmap 的標志位, 移除正在寫入的標識并返回 elem 對應的指針, 在 go map 寫入的過程中,

若當前哈希桶未找到topbits 與哈希值高 8 位相等的, 則沿著 overflow 繼續(xù)向后遍歷溢出桶, 當遍歷到最后, 如果沒有找到相等的 key, 若遍歷的過程中找到空位, 則將新建的 k/v 插入到該空位上

否則意味著當前的所有哈希桶包括溢出桶在內都已經(jīng)存滿元素了, 此時要判定是否進行 HashTable 的擴容, HashTable 若要擴容需要滿足一定條件, 如當前沒有正在擴容并且 HashTable 的裝載因子已經(jīng)超過 6.5 了, 或者當前的溢出桶數(shù)目過多時會觸發(fā) HashTable 的擴容, 當 HashTable 擴容完畢后, 寫入操作會 goto 到一開始, 重復上述過程, 反過來, 若當前沒有達到 HashTable 擴容的條件, 則此時只是簡單地再生成一個溢出桶, 然后將 key 和 elem 放入新的溢出桶的第一個位置上, 完成此次的寫入操作

Go map 的刪除

go map 的刪除與查找/插入/更新操作的過程類似, 都是通過哈希映射、比較 topbits、依次遍歷哈希桶溢出桶、計算 key/elem 偏移量等過程來定位元素位置, 當找到元素后, 則清空的對應的內存位置的數(shù)據(jù), 有的元素是以指針形式存儲的(如長度超過 128 的 key/elem), 則定位到該指針對應的內存將數(shù)據(jù)清空

Go map 的擴容

隨著向 HashTable 中插入的元素越來越多, 哈希桶的 cell 逐漸被填滿, 溢出桶的數(shù)量可能也越來越多, 此時哈希沖突發(fā)生的頻率越來越高, HashTable 的性能將不斷下降, 為了解決這個問題, 此時需要對 HashTable 做擴容操作,

在 go map 中, 針對 go map 的特定數(shù)據(jù)結構, 其裝載因子等于 k/v 對數(shù)目除以哈希桶的數(shù)目(含溢出桶), golang 規(guī)定當該定義下的裝載因子達到 6.5 時便需要觸發(fā) map 的擴容, go map 擴容和策略共有兩種, 除了剛剛所說的裝載因子達到 6.5 之外, 若溢出桶過多也會觸發(fā) map 的擴容, 這是基于這樣的考慮, 向 map 中插入大量的元素, 哈希桶將逐漸被填滿, 這個過程中也可能創(chuàng)建了一些溢出桶, 但此時裝載因子并沒有超過設定的閾值, 然后對這些 map 做刪除操作, 刪除元素之后, map 中的元素數(shù)目變少, 使得裝載因子降低, 而后又重復上述的過程, 最終使得整體的裝載因子不大, 但整個 map 中存在了大量的溢出桶, 因此當溢出桶數(shù)目過多時, 即便沒有達到裝載因子 6.5 的閾值也會觸發(fā)擴容, 若裝載因子過大, 說明此時 map 中元素數(shù)目過多, 此時 go map 的擴容策略為將 hmap 中的 B 增一, 即將整個哈希桶數(shù)目擴充為原來的兩倍大小, 而當因為溢出桶數(shù)目過多導致擴容時, 因此時裝載因子并沒有超過 6.5, 這意味著 map 中的元素數(shù)目并不是很多, 因此這時的擴容策略是等量擴容, 即新建完全等量的哈希桶, 然后將原哈希桶的所有元素搬遷到新的哈希桶中

go map 的擴容是發(fā)生在插入和刪除的過程中

go map 的擴容類似于 redis, 都是采用漸進式擴容, 避免一次性對大 map 擴容造成的區(qū)間性能抖動, go 擴容的基本步驟是首先根據(jù)擴容條件(裝載因子 >= 6.5 或 溢出桶數(shù)目太多), 而確定擴容后的大小, 然后創(chuàng)建該大小的新哈希桶, 這時會將 hmap 中的 buckets 指針指向新創(chuàng)建的哈希桶, 而原先的哈希桶地址則保存在 oldbuckets 指針中

若是因為溢出桶數(shù)目過多造成的擴容, 則擴容是等量擴容, 整個過程是將原 Bucket 中的所有元素遷移到新的等量的 Bucket 中, 在遷移的過程中, 哈希桶(非溢出桶)的相對位置不會發(fā)生改變, 即原先位于 N 號 Bucket 的元素會映射到新的 N 號 Bucket 位置上, 而若是翻倍擴容, 則元素會被平均(此處不是數(shù)學意義上的嚴格平均, 其具體分流邏輯是用哈希值與原 Bucket 數(shù)目做邏輯與運算, 取決于 HashFunc 的該位是否足夠平均)分流到兩段上, 在 go 中每次只搬遷兩個 Bucket, 當所有元素都搬遷完畢之后, hmap 的 oldbuckets 指針會被設置為 nil, 因此 oldbuckets 指針是否為 nil 可以作為當前 map 是否處于擴容狀態(tài)的一個標志

Go map 的遍歷

go map 的遍歷原本是一件比較簡單的事情, 外層循環(huán)遍歷所有 Bucket, 中層循環(huán)橫向遍歷所有溢出桶, 內層循環(huán)遍歷 Bucket 的所有 k/v , 若沒有擴容邏輯的話, 以上所述的 3 層循環(huán)即可完成 map 的遍歷, 但由于擴容邏輯的存在, 使得 map 遍歷復雜性略微有所增加, map 的迭代器由如下結構來表征

每次遍歷的結果是不同的, 這是因為 go 隨機設置了遍歷起點, 不僅起始 Bucket 是隨機的, 對于 Bucket 中的起始 cell 也是隨機的(這樣做似乎是為了規(guī)避程序員故意使用這個 map 的順序?), map 在迭代過程中,需要檢查 map 的狀態(tài), 如果 map 當前正處于擴容狀態(tài), 則需要檢查遍歷到的 Bucket, 若 Bucket 尚未搬遷, 則需要去該 Bucket 對應的 oldBucket 里遍歷元素, 并且這里要注意因為 oldBucket 中的元素可能會分流到兩個新 Bucket 中, 因此在遍歷時只會取出會分流到當前 Bucket 的元素, 否則元素會被遍歷兩次, 具體細節(jié)可以看 mapiternext 函數(shù)的代碼

以上就是深入刨析Golang-map底層原理的詳細內容，更多關于Golang-map底層原理的資料請關注腳本之家其它相關文章！

最新評論