Go?map底層實(shí)現(xiàn)、擴(kuò)容規(guī)則和特性分類源碼分析

這篇文章主要介紹“Go map底層實(shí)現(xiàn)、擴(kuò)容規(guī)則和特性分類源碼分析”的相關(guān)知識，小編通過實(shí)際案例向大家展示操作過程，操作方法簡單快捷，實(shí)用性強(qiáng)，希望這篇“Go map底層實(shí)現(xiàn)、擴(kuò)容規(guī)則和特性分類源碼分析”文章能幫助大家解決問題。

1、哈希表

哈希表用來存儲鍵值對，通過 hash 函數(shù)把鍵值對散列到一個個桶（bucket）中。

Go 使用與運(yùn)算，桶個數(shù) m，則編號 [0, m-1]，把鍵的 hash 值與 m-1 與運(yùn)算。為保證所有桶都會被選中，m 一定為 2 的整數(shù)次冪。這樣 m 的二進(jìn)制表示一定只有一位為 1，m-1 的二進(jìn)制表示一定是低于這一位的所有位均為 1。下文擴(kuò)容規(guī)則有詳細(xì)樣例。

• m=4 （00000100）

• m-1 （00000011）

如果桶的個數(shù)不是2的整數(shù)次冪，就有可能出現(xiàn)有些桶絕對不會被選中的情況 ：

• m=5 （00000101）

• m-1 （00000100）

則 [1, 3] 注定是空桶。

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

2、Go map底層實(shí)現(xiàn)

hmap

Golang的map就是使用哈希表作為底層實(shí)現(xiàn)，map 實(shí)際上就是一個指針，指向hmap結(jié)構(gòu)體。

type hmap struct {
  count     int              // 存儲的鍵值對數(shù)目
  flags     uint8            // 狀態(tài)標(biāo)志（是否處于正在寫入的狀態(tài)等）
  B         uint8            // 桶的數(shù)目 2^B
  noverflow uint16           // 使用的溢出桶的數(shù)量
  hash0     uint32           // 生成hash的隨機(jī)數(shù)種子
  buckets    unsafe.Pointer  // bucket數(shù)組指針，數(shù)組的大小為2^B（桶）
  oldbuckets unsafe.Pointer  // 擴(kuò)容階段用于記錄舊桶用到的那些溢出桶的地址
  nevacuate  uintptr         // 記錄漸進(jìn)式擴(kuò)容階段下一個要遷移的舊桶編號
  extra *mapextra            // 指向mapextra結(jié)構(gòu)體里邊記錄的都是溢出桶相關(guān)的信息
}

bmap

buckets 則是指向哈希表節(jié)點(diǎn) bmap 即 bucket 的指針，Go 中一個桶里面會最多裝 8 個 key。

hash 值低8位用來定位 bucket，高8位定位 tophash。

type bmap struct {
    tophash [bucketCnt]uint8        
    // len為8的數(shù)組，用來快速定位key是否在這個bmap中
    // 一個桶最多8個槽位，如果key所在的tophash值在tophash中，則代表該key在這個桶中
}

上面bmap結(jié)構(gòu)是靜態(tài)結(jié)構(gòu)，在編譯過程中runtime.bmap會拓展成以下結(jié)構(gòu)體：

type bmap struct{
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr        // 內(nèi)存對齊使用，可能不需要
    overflow uintptr        // 當(dāng)bucket 的8個key 存滿了之后
    // overflow 指向下一個溢出桶 bmap，
    // overflow是uintptr而不是*bmap類型，保證bmap完全不含指針，是為了減少gc，溢出桶存儲到extra字段中
}

tophash：是個長度為8的數(shù)組，哈希值低位相同的鍵存入當(dāng)前bucket時會將哈希值的高 8 位存儲在該數(shù)組中，以方便后續(xù)匹配。

tophash字段不僅存儲key哈希值的高8位，還會存儲一些狀態(tài)值，用來表明當(dāng)前桶單元狀態(tài)，這些狀態(tài)值都是小于minTopHash的。為了避免key哈希值的高8位值和這些狀態(tài)值相等，產(chǎn)生混淆情況，所以當(dāng)key哈希值高8位若小于minTopHash時候，自動將其值加上minTopHash作為該key的tophash。

emptyRest      = 0 // 表明此桶單元為空，且更高索引的單元也是空
emptyOne       = 1 // 表明此桶單元為空
evacuatedX     = 2 // 用于表示擴(kuò)容遷移到新桶前半段區(qū)間
evacuatedY     = 3 // 用于表示擴(kuò)容遷移到新桶后半段區(qū)間
evacuatedEmpty = 4 // 用于表示此單元已遷移
minTopHash     = 5 // key的tophash值與桶狀態(tài)值分割線值，小于此值的一定代表著桶單元的狀態(tài)，大于此值的一定是key對應(yīng)的tophash值
func tophash(hash uintptr) uint8 {
    top := uint8(hash >> (goarch.PtrSize*8 - 8))
    if top < minTopHash {
        top += minTopHash
    }
    return top
}

一個桶里邊可以放8個鍵值對，但是為了讓內(nèi)存排列更加緊湊，8個key放一起，8個value放一起，在8個key前面是8個tophash，每個tophash都是對應(yīng)哈希值的高8位。

當(dāng)key和value類型不一樣的時候，key和value占用字節(jié)大小不一樣，使用key/value這種形式可能會因為內(nèi)存對齊導(dǎo)致內(nèi)存空間浪費(fèi)。

overflow：指向一個溢出桶，溢出桶的布局與常規(guī)的桶布局相同，是為了減少擴(kuò)容次數(shù)引入的（即哈希沖突的拉鏈法）。當(dāng)一個桶存滿了，還有可用的溢出桶時，就會在桶后邊鏈一個溢出桶繼續(xù)往里面存。

mapextra與溢出桶

如果哈希表要分配的桶的數(shù)目大與 **** 2 4 2^4 24**次方，就認(rèn)為使用到溢出桶的幾率較大，就會預(yù)分配 2 ( B − 4 ) 2^{(B-4)} 2(B−4) 個溢出桶備用**，這些溢出桶與常規(guī)桶在內(nèi)存中是連續(xù)的，只是前 2 B 2^B 2B 個用作常規(guī)桶。

hmap 中最后有 extra 字段，它是指向mapextra結(jié)構(gòu)體，里邊記錄的都是溢出桶相關(guān)的信息。

type mapextra struct {
  overflow *[]*bmap     // 記錄已使用的溢出桶的地址
  oldoverflow *[]*bmap  // 擴(kuò)容階段舊桶使用的溢出桶地址
  nextOverflow *bmap    // 指向下一個空閑溢出桶地址
}

如下圖所示，分配桶數(shù)目為 2 5 = 32 2^5 = 32 25=32，則備用溢出桶數(shù)目為 2 ( 5 − 4 ) = 2 2^{(5-4)} = 2 2(5−4)=2。

• 此時編號為 2 的 bmap 桶存滿了，overflow 指向下一個溢出桶地址，這里指向 32 號。

• hmap 中 noverflow 表示使用溢出桶數(shù)量，這里為 1。extra 字段指向記錄溢出桶的mapextra結(jié)構(gòu)體。

• mapextra 中的 nextOverflow 指向下一個空閑溢出桶 33 號。

3、擴(kuò)容規(guī)則

map擴(kuò)容時使用漸進(jìn)式擴(kuò)容。

由于 map 擴(kuò)容需要將原有的 key/value 重新搬遷到新的內(nèi)存地址，如果map存儲了數(shù)以億計的key-value，一次性搬遷將會造成比較大的延時，因此 Go map 的擴(kuò)容采取了一種稱為**“漸進(jìn)式”的方式，原有的 key 并不會一次性搬遷完畢，每次最多只會搬遷 2 個 bucket。只有在插入或修改、刪除 key 的時候，都會嘗試進(jìn)行搬遷 buckets 的工作**。先檢查 oldbuckets 是否搬遷完畢，具體來說就是檢查 oldbuckets 是否為 nil。

翻倍擴(kuò)容

count/(2^B) > 6.5：當(dāng)負(fù)載因子超過6.5時就會觸發(fā)翻倍擴(kuò)容。

如下圖，原來 B = 0，只有一個桶，裝滿后觸發(fā)翻倍擴(kuò)容，B = 1，buckets 指向兩個新桶，oldbuckets 指向舊桶，nevacuate 表示接下來要遷移編號為 0 的舊桶。舊桶的鍵值對會漸進(jìn)式分流到兩個新桶中。直到舊桶中的鍵值對全部搬遷完畢后，刪除oldbuckets。

遷移過程中使用與運(yùn)算法hash & (m-1)，把舊桶遷移到新桶上，用這個舊桶的hash值跟擴(kuò)容后的桶的個數(shù) m-1 的值相與(&)，得幾就在哪個位置上。

如果舊桶數(shù)量為4，那么新桶的數(shù)量就為 8。如果一個哈希值選擇 0 號舊桶，那么哈希值的二進(jìn)制低兩位一定為 0。

舊桶 m-1 = 3 = 00000011，選擇 0 號舊桶說明哈希值為 xxxxxx00，00000011 & xxxxxx00 = 0

所以選擇新桶的結(jié)果只有兩種，取決于哈希值的第三位是 0還是 1。

新桶 m-1 = 7 = 00000111，與原哈希值與運(yùn)算，若第三位是 0 則為 0，第三位為 1 則為 00000100 = 4。

等量擴(kuò)容

雖然沒有超過負(fù)載因子限制，但是使用溢出桶過多，就會觸發(fā)等量擴(kuò)容，創(chuàng)建和舊桶數(shù)目一樣多的新桶，然后把原來的鍵值對遷移到新桶中。

如果常規(guī)桶的數(shù)目小于等于 2 15 2^{15} 215 , 使用的溢出桶大于常規(guī)桶數(shù)目 2 B 2^B 2B就是多了。

B <= 15，noverflow >= 2^B

如果常規(guī)桶的數(shù)目大于 2 15 2^{15} 215 , 使用的溢出桶大于 2 15 2^{15} 215就是多了。

B > 15， noverflow >= 2^15

一般發(fā)生在很多鍵值對被刪除的情況下，這樣會造成overflow的bucket數(shù)量增多，但負(fù)載因子又不高。同樣數(shù)目的鍵值對，遷移到新桶中會把松散的鍵值對重新排列一次，使其排列的更加緊湊，進(jìn)而保證更快的存取，這就是等量擴(kuò)容的意義所在。

4、其他特性

map遍歷無序

使用 range 多次遍歷 map 時輸出的 key 和 value 的順序可能不同。這是 Go 語言的設(shè)計者們有意為之，旨在提示開發(fā)者們，Go 底層實(shí)現(xiàn)并不保證 map 遍歷順序穩(wěn)定，請大家不要依賴 range 遍歷結(jié)果順序。

主要原因有2點(diǎn)：

• map在遍歷時，并不是從固定的0號bucket開始遍歷的，每次遍歷，都會從一個隨機(jī)值序號的bucket，再從其中隨機(jī)的cell開始遍歷

• map遍歷時，是按序遍歷bucket，同時按需遍歷bucket中和其overflow bucket中的cell。但是map在擴(kuò)容后，會發(fā)生key的搬遷，這造成原來落在一個bucket中的key，搬遷后，有可能會落到其他bucket中了，從這個角度看，遍歷map的結(jié)果就不可能是按照原來的順序了

map 本身是無序的，且遍歷時順序還會被隨機(jī)化，如果想順序遍歷 map，需要對 map key 先排序，再按照 key 的順序遍歷 map。

map非線程安全

Go 官方認(rèn)為 Go map 更應(yīng)適配典型使用場景（不需要從多個 goroutine 中進(jìn)行安全訪問），而不是為了小部分情況（并發(fā)訪問），導(dǎo)致大部分程序付出加鎖代價（性能），決定了不支持，若并發(fā)讀寫 map 直接報錯。

官方推薦對 map 上讀寫鎖，一個匿名結(jié)構(gòu)（struct）體，包含一個原生和一個嵌入讀寫鎖 sync.RWMutex：

var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}
counter.RLock()
n := counter.m["煎魚"]
counter.RUnlock()
counter.Lock()
counter.m["煎魚"]++
counter.Unlock()

map 的數(shù)據(jù)量非常大時，只有一把鎖會效率低下，分區(qū)見上鎖又邏輯復(fù)雜。Go1.9 起支持的 sync.Map，其支持并發(fā)讀寫 map。采取了 “空間換時間” 的機(jī)制，冗余了兩個數(shù)據(jù)結(jié)構(gòu)，分別是：read 和 dirty，減少加鎖對性能的影響。

type Map struct {
   mu Mutex
   read atomic.Value // readOnly
   dirty map[interface{}]*entry
   misses int
}

其是專門為 append-only 場景設(shè)計的，也就是適合讀多寫少的場景。如果寫多性能會急劇下降。

關(guān)于“Go map底層實(shí)現(xiàn)、擴(kuò)容規(guī)則和特性分類源碼分析”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識，可以關(guān)注億速云行業(yè)資訊頻道，小編每天都會為大家更新不同的知識點(diǎn)。