基本分析

在 Go 底層源碼 src/runtime/map.go 中，擴(kuò)縮容的處理方法是 grow 為前綴的方法來(lái)處理的。

其中擴(kuò)縮容涉及到的是插入元素的操作，對(duì)應(yīng) mapassign 方法：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  ...
 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  hashGrow(t, h)
  goto again
 }
  ...
}
func (h *hmap) growing() bool {
 return h.oldbuckets != nil
}
func overLoadFactor(count int, B uint8) bool {
 return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
 if B > 15 {
  B = 15
 }
 return noverflow >= uint16(1)<<(B&15)
}　

核心看到針對(duì)擴(kuò)縮容的判斷邏輯：

當(dāng)前沒有在擴(kuò)容：條件為 oldbuckets 不為 nil。

是否可以進(jìn)行擴(kuò)容：條件為 hmap.count> hash 桶數(shù)量 (2^B)*6.5。其中 hmap.count 指的是map 的數(shù)據(jù)數(shù)目， 2^B 僅指 hash 數(shù)組的大小，不包含溢出桶。

是否可以進(jìn)行縮容：條件為溢出桶（noverflow）的數(shù)量 >= 32768（1<<15）。

可以關(guān)注到，無(wú)論是擴(kuò)容還是縮容，其都是由 hashGrow 方法進(jìn)行處理：

 func hashGrow(t *maptype, h *hmap) {
 bigger := uint8(1)
 if !overLoadFactor(h.count+1, h.B) {
  bigger = 0
  h.flags |= sameSizeGrow
 }
  ...
}

若是擴(kuò)容，則 bigger 為 1，也就是 B+1。代表 hash 表容量擴(kuò)大 1 倍。不滿足就是縮容，也就是 hash 表容量不變。

可以得出結(jié)論：map 的擴(kuò)縮容的主要區(qū)別在于 hmap.B 的容量大小改變。而縮容由于 hmap.B 壓根沒變，內(nèi)存空間的占用也是沒有變化的。

帶來(lái)的隱患

這種方式其實(shí)是存在運(yùn)行隱患的，也就是導(dǎo)致在刪除元素時(shí)，并不會(huì)釋放內(nèi)存，使得分配的總內(nèi)存不斷增加。如果一個(gè)不小心，拿 map 來(lái)做大 key/value 的存儲(chǔ)，也不注意管理，很容易就內(nèi)存爆了。

也就是 Go 語(yǔ)言的 map 目前實(shí)現(xiàn)的是 “偽縮容”，僅針對(duì)溢出桶過(guò)多的情況。若是觸發(fā)縮容，hash 數(shù)組的占用的內(nèi)存大小不變（等量擴(kuò)容）。

若要實(shí)現(xiàn) ”真縮容“，Go Contributor @josharian 表示目前唯一可用的解決方法是：創(chuàng)建一個(gè)新的 map 并從舊的 map 中復(fù)制元素。

示例如下：

old := make(map[int]int, 9999999)
new := make(map[int]int, len(old))
for k, v := range old {
    new[k] = v
}
old = new
...

為什么不支持縮容

下述內(nèi)容會(huì)主要基于如下兩個(gè) issues 和 proposal 來(lái)分析：

《runtime: shrink map as elements are deleted[1]》
《proposal: runtime: add way to clear and reuse a map's working storage[2]》

目前 map 的縮容處理起來(lái)比較棘手，最早的 issues 是 2016 年提出的，也有人提過(guò)一些提案，但都因?yàn)榉N種原因被拒絕了。

簡(jiǎn)單來(lái)講，就是沒有找到一個(gè)很好的方法實(shí)現(xiàn)，存在明確的實(shí)現(xiàn)成本問(wèn)題，沒辦法很方便的 ”告訴“ Go 運(yùn)行時(shí)，我要：

• 記得保留存儲(chǔ)空間，我要立即重用 map。
• 趕緊釋放存儲(chǔ)空間，map 從現(xiàn)在開始會(huì)小很多。

抽象來(lái)看癥結(jié)是：需要保證增長(zhǎng)結(jié)果在下一個(gè)開始之前完成，此處的增長(zhǎng)指的是 ”從小到大，從一個(gè)大小到相同大小，從大到小“ 的復(fù)雜過(guò)程。

這屬于一個(gè)多重 case，從而導(dǎo)致也就一直拖著，慢慢想。

到此這篇關(guān)于Golang中map縮容的實(shí)現(xiàn)的文章就介紹到這了,更多相關(guān)Golang map縮容 內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論