map底層原理刨析

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

1. Go map 的底層結(jié)構(gòu)

// 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
}

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

Hmap數(shù)據(jù)結(jié)構(gòu)

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

我們首先來看一下bmap,即哈希桶的結(jié)構(gòu)

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

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

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

MapExtra 數(shù)據(jù)結(jié)構(gòu)

// 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
}

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

這會導(dǎo)致一個(gè)問題, bucket 的底層結(jié)構(gòu) bmap 中含有一個(gè)指向溢出桶的指針(uintptr類型, uintptr指針指向的內(nèi)存不保證不會被 gc free 掉), 當(dāng) gc 不掃描該結(jié)構(gòu)時(shí), 該指針指向的內(nèi)存會被 gc free 掉, 因此在 hmap 結(jié)構(gòu)中增加了 mapextra 字段,

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

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

Go map 的查找

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

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

hmap 結(jié)構(gòu)中存儲了哈希桶的內(nèi)存地址, 在這個(gè)地址的基礎(chǔ)上偏移桶編號*桶長度便得到了對應(yīng)的哈希桶的地址, 接下來進(jìn)一步在該哈希桶中找尋 key 對應(yīng)的元素,

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

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

Go map 的插入/更新

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

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

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

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

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

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

Go map 的刪除

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

Go map 的擴(kuò)容

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

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

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

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

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

Go map 的遍歷

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

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

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

最新評論