GO 中 map 的實現(xiàn)原理

GO 中 map 的實現(xiàn)原理.jpg

image

• 分享了切片是什么
• 切片和數(shù)組的區(qū)別
• 切片的數(shù)據(jù)結(jié)構(gòu)
• 切片的擴(kuò)容原理
• 空切片 和 nil 切片的區(qū)別

要是對 GO 的slice 原理還有點興趣的話坟乾，歡迎查看文章 GO 中 slice 的實現(xiàn)原理

map 是什么？

是 GO 中的一種數(shù)據(jù)類型蝶防，底層實現(xiàn)是 hash 表甚侣，看到 hash 表 是不是會有一點熟悉的感覺呢

我們在寫 C/C++ 的時候，里面也有 map 這種數(shù)據(jù)結(jié)構(gòu)间学，是 key - value 的形式

可是在這里我們可別搞混了殷费，GO 里面的 map 和 C/C++ 的map 可不是同一種實現(xiàn)方式

• C/C++ 的 map 底層是 紅黑樹實現(xiàn)的
• GO 的 map 底層是hash 表實現(xiàn)的

可是別忘了C/C++中還有一個數(shù)據(jù)類型是 unordered_map，無序map低葫，他的底層實現(xiàn)是 hash 表详羡，與我們GO 里面的 map 實現(xiàn)方式類似

image

map 的數(shù)據(jù)結(jié)構(gòu)是啥樣的？

前面說到的 GO 中 string 實現(xiàn)原理嘿悬，GO 中 slice 實現(xiàn)原理殷绍， 都會對應(yīng)有他們的底層數(shù)據(jù)結(jié)構(gòu)

哈，沒有例外鹊漠，今天說的 map 必然也有自己的數(shù)據(jù)結(jié)構(gòu)主到， 相對來說會比前者會多一些成員茶行，我們這就來看看吧

map 具體 的實現(xiàn) 源碼位置是：src/runtime/map.go

image

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

hmap結(jié)構(gòu)中的成員我們來一個一個看看：

通過extra字段， 我們看到他是mapextra類型的塔鳍，我們看看細(xì)節(jié)

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

點進(jìn)來伯铣，這里主要是要和大家一起看看這個 bmap的數(shù)據(jù)結(jié)構(gòu)，

image

// A bucket for a Go map.
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

type bmap struct {
    tophash [8]uint8 //存儲哈希值的高8位
    data    byte[1]  //key value數(shù)據(jù):key/key/key/.../value/value/value...
    overflow *bmap   //溢出bucket的地址
}

源碼的意思是這樣的：

tophash 一般存放的是桶內(nèi)每一個key hash值字節(jié)，如果 tophash[0] < minTopHash掌唾， tophash[0] 是一個疏散狀態(tài)

這里源碼中有一個注意點：

實際上分配內(nèi)存的時候放前，內(nèi)存的前8個字節(jié)是 bmap ，后面跟著 8 個 key 糯彬、 8 個 value 和 1 個溢出指針

我們來看看圖吧

GO 中 map 底層數(shù)據(jù)結(jié)構(gòu)成員相對比 string 和 slice 多一些凭语，不過也不是很復(fù)雜，咱們畫圖來瞅瞅

咱們的 hmap的結(jié)構(gòu)是這樣的撩扒，可以關(guān)注桶數(shù)組（hmap.buckets）

image

若圖中的 B = 3的話的似扔，那么桶數(shù)組長度 就是 8

上面看到每一個 bucket ，最多可以存放 8 個key / value對

如果超出了 8 個的話搓谆， 那么就會溢出炒辉，此時就會鏈接到額外的溢出桶

理解起來是這個樣子的

image

嚴(yán)格來說，每一個桶里面只會有8 個鍵值對挽拔，若多余 8 的話辆脸，就會溢出，溢出的指針就會指向另外一個桶對應(yīng)的 8個鍵值對

這里我們結(jié)合一下上面 bmap 的數(shù)據(jù)結(jié)構(gòu)：

• tophash 是個長度為8的數(shù)組

哈希值低位相同的鍵存入當(dāng)前bucket時螃诅，會將哈希值的高位存儲在該數(shù)組中啡氢，便于后續(xù)匹配

• data里面存放的是 key-value 數(shù)據(jù)

存放順序是8個key依次排開，8個value依次排開术裸，這是為啥呢倘是？

image

因為GO 里面為了字節(jié)對齊，節(jié)省空間

• overflow 指針袭艺，指向的是另外一個 桶

這里是解決了 2 個問題搀崭，第一是解決了溢出的問題，第二是解決了沖突問題

啥是哈希沖突？

上述我們說到 hash 沖突瘤睹，我們來看看啥是hash 沖突升敲，以及如何解決呢

關(guān)鍵字值不同的元素可能會映象到哈希表的同一地址上就會發(fā)生哈希沖突

簡單對應(yīng)到我們的上述數(shù)據(jù)結(jié)構(gòu)里面來，我們可以這樣理解

當(dāng)有兩個或以上的鍵(key)被哈希到了同一個bucket時轰传，這些鍵j就發(fā)生了沖突

關(guān)于解決hash 沖突的方式大體有如下 4 個驴党，網(wǎng)上查找的資料，咱們引用一下获茬，梳理一波看看：

• 開放定址法

當(dāng)沖突發(fā)生時港庄，使用某種探查(亦稱探測)技術(shù)在散列表中形成一個探查(測)序列。

沿此序列逐個單元地查找恕曲，直到找到給定 的關(guān)鍵字鹏氧，或者碰到一個開放的地址(即該地址單元為空)為止（若要插入，在探查到開放的地址佩谣，則可將待插入的新結(jié)點存人該地址單元）把还。

查找時探查到開放的 地址則表明表中無待查的關(guān)鍵字，即查找失敗稿存。

• 再哈希法

同時構(gòu)造多個不同的哈希函數(shù)笨篷。

• 鏈地址法

將所有哈希地址為i的元素構(gòu)成一個稱為同義詞鏈的單鏈表瞳秽，并將單鏈表的頭指針存在哈希表的第 i 個單元中

因而查找瓣履、插入和刪除主要在同義詞鏈中進(jìn)行。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況练俐。

• 建立公共溢出區(qū)

將哈希表分為基本表和溢出表兩部分袖迎，凡是和基本表發(fā)生沖突的元素，一律填入溢出表腺晾。

細(xì)心的小伙伴看到這里燕锥，有沒有看出來 GO 中的map 是如何解決 hash 沖突的？

image

沒錯悯蝉，GO 中的map 解決hash 沖突 就是使用的是 鏈地址法來解決鍵沖突

再來一個圖归形，咱們看看他是咋鏈 的，其實咱們上述說的溢出指針就已經(jīng)揭曉答案了

image

如上圖鼻由，每一個bucket 里面的溢出指針 會指向另外一個 bucket 暇榴，每一個bucket 里面存放的是 8 個 key 和 8 個 value ，bucket 里面的溢出指針又指向另外一個bucket蕉世，用類似鏈表的方式將他們連接起來

GO 中 map 的基本操作有哪些蔼紧？

map 的應(yīng)用比較簡單，感興趣的可以在搜索引擎上查找相關(guān)資料狠轻，知道 map 具體實現(xiàn)原理之后奸例，再去應(yīng)用就會很簡單了

• 有 map 的初始化
• map 的增、刪向楼、改查吊、查

GO 中 map 可以擴(kuò)容嗎谐区？

當(dāng)然可以擴(kuò)容，擴(kuò)容分為如下兩種情況：

• 增量擴(kuò)容
• 等量擴(kuò)容

咱們 map 擴(kuò)容也是有條件的逻卖，不是隨隨便便就能擴(kuò)容的卢佣。

image

當(dāng)一個新的元素要添加進(jìn)map的時候，都會檢查是否需要擴(kuò)容箭阶，擴(kuò)容的觸發(fā)條件就有 2 個：

• 當(dāng)負(fù)載因子 > 6.5的時候虚茶，也就是平均下來，每個bucket存儲的鍵值對達(dá)到6.5個的時候仇参，就會擴(kuò)容
• 當(dāng)溢出的數(shù)量 > 2^15 的時候嘹叫，也會擴(kuò)容

這里說一下啥是負(fù)載因子呢？

有這么一個公式诈乒，來計算負(fù)載因子：

負(fù)載因子 = 鍵的數(shù)量 / bucket 數(shù)量

舉個例子：

若有bucket有8個罩扇，鍵值對也有8個，則這個哈希表的負(fù)載因子就是 1

哈希表也是要對負(fù)載因子進(jìn)行控制的怕磨，不能讓他太大喂饥，也不能太小，要在一個合適的范圍內(nèi)肠鲫，具體的合適范圍根據(jù)不同的組件有不同的值员帮，若超過了這個合適范圍，哈希表就會觸發(fā)再哈希（rehash）

例如

• 哈希因子太小的話导饲，這就表明空間利用率低
• 哈希因子太大的話捞高，這就表明哈希沖突嚴(yán)重，存取效率比較低

注意了渣锦，在 Go 里面硝岗，負(fù)載因子達(dá)到6.5時會觸發(fā)rehash

啥是增量擴(kuò)容

就是當(dāng)負(fù)載因子過大，也就是哈希沖突嚴(yán)重的時候袋毙，會做如下 2 個步驟

• 新建一個 bucket型檀，新的bucket 是原 bucket 長度的 double
• 再將原來的 bucket 數(shù)據(jù) 搬遷到 新的 bucket 中

可是我們想一想，如果有上千萬听盖，上億級別鍵值對胀溺，那么遷移起來豈不是很耗時

所以GO 還是很聰明的，他采用的逐步搬遷的方法媳溺，每次訪問map月幌，都會觸發(fā)一次遷移

咱們畫個圖來瞅瞅

咱畫一個hmap，里面有 1 個bucket0悬蔽，這個桶的滿載是 4個 key-value扯躺，此時的負(fù)載因子是 4

image

實際上是不會觸發(fā)擴(kuò)容的，因為GO 的默認(rèn)負(fù)載因子是 6.5

但是我們?yōu)榱搜菔痉奖悖M一下擴(kuò)容的效果

當(dāng)再插入一個鍵值對的時候录语，就會觸發(fā)擴(kuò)容操作倍啥，擴(kuò)容之后再把新插入的鍵值對，放到新的bucket中澎埠，即bucket1虽缕，而舊的bucket指針就會指向原來的那個bucket

image

最后，再做一個遷移蒲稳，將舊的bucket氮趋，遷移到新的bucket上面來，刪掉舊的bucket

image

根據(jù)上述的數(shù)據(jù)搬遷圖江耀，我們可以知道

在數(shù)據(jù)搬遷的過程中剩胁，原來的bucket中的鍵值對會存在于新的bucket的前面

新插入的鍵值對，會存在與另外一個bucket中祥国，自然而然的會放到原來 bucket 的后面了

image

啥是等量擴(kuò)容

等量擴(kuò)容昵观，等量這個名字感覺像是，擴(kuò)充的容量和原來的容量是一一對齊的舌稀，也就是說成倍增長

其實不然啊犬，等量擴(kuò)容，其實buckets數(shù)量沒有變化

只是對bucket的鍵值對重新排布壁查，整理的更加有條理觉至，讓其使用率更加的高

例如 等量擴(kuò)容后，對于一些 溢出的 buckets潮罪，且里面的內(nèi)容都是空的鍵值對康谆，這時领斥，就可以把這些降低效率且無效的buckets清理掉

這樣嫉到，是提高buckets效率的一種有效方式

總結(jié)

• 分享 map 是什么
• map 的底層數(shù)據(jù)結(jié)構(gòu)是啥樣的
• 什么是哈希沖突，并且如何解決
• GO 的map 擴(kuò)容方式月洛，以及畫圖進(jìn)行理解

歡迎點贊何恶，關(guān)注，收藏

朋友們嚼黔，你的支持和鼓勵细层，是我堅持分享，提高質(zhì)量的動力

image

好了唬涧，本次就到這里疫赎，下一次 GO 中 Chan 的實現(xiàn)原理分享

技術(shù)是開放的，我們的心態(tài)碎节，更應(yīng)是開放的捧搞。擁抱變化，向陽而生，努力向前行胎撇。

我是小魔童哪吒介粘，歡迎點贊關(guān)注收藏，下次見~