1、哈希表

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

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

• m=4 （00000100）
• m-1 （00000011）

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

• 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í)際上就是一個(gè)指針，指向hmap結(jié)構(gòu)體。

type hmap struct {
  count     int              // 存儲(chǔ)的鍵值對(duì)數(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ò)容階段下一個(gè)要遷移的舊桶編號(hào)
  extra *mapextra            // 指向mapextra結(jié)構(gòu)體里邊記錄的都是溢出桶相關(guān)的信息
}

bmap

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

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

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

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

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

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

tophash字段不僅存儲(chǔ)key哈希值的高8位，還會(huì)存儲(chǔ)一些狀態(tài)值，用來表明當(dāng)前桶單元狀態(tài)，這些狀態(tài)值都是小于minTopHash的。為了避免key哈希值的高8位值和這些狀態(tài)值相等，產(chǎn)生混淆情況，所以當(dāng)key哈希值高8位若小于minTopHash時(shí)候，自動(dòng)將其值加上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對(duì)應(yīng)的tophash值
func tophash(hash uintptr) uint8 {
    top := uint8(hash >> (goarch.PtrSize*8 - 8))
    if top < minTopHash {
        top += minTopHash
    }
    return top
}

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

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

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

mapextra與溢出桶

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

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

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

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

• 此時(shí)編號(hào)為 2 的 bmap 桶存滿了，overflow 指向下一個(gè)溢出桶地址，這里指向 32 號(hào)。
• hmap 中 noverflow 表示使用溢出桶數(shù)量，這里為 1。extra 字段指向記錄溢出桶的mapextra結(jié)構(gòu)體。
• mapextra 中的 nextOverflow 指向下一個(gè)空閑溢出桶 33 號(hào)。

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

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

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

翻倍擴(kuò)容

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

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

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

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

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

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

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

等量擴(kuò)容

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

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

4、其他特性

map遍歷無序

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

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

• map在遍歷時(shí)，并不是從固定的0號(hào)bucket開始遍歷的，每次遍歷，都會(huì)從一個(gè)隨機(jī)值序號(hào)的bucket，再從其中隨機(jī)的cell開始遍歷
• map遍歷時(shí)，是按序遍歷bucket，同時(shí)按需遍歷bucket中和其overflow bucket中的cell。但是map在擴(kuò)容后，會(huì)發(fā)生key的搬遷，這造成原來落在一個(gè)bucket中的key，搬遷后，有可能會(huì)落到其他bucket中了，從這個(gè)角度看，遍歷map的結(jié)果就不可能是按照原來的順序了

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

map非線程安全

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

官方推薦對(duì) map 上讀寫鎖，一個(gè)匿名結(jié)構(gòu)（struct）體，包含一個(gè)原生和一個(gè)嵌入讀寫鎖 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ù)量非常大時(shí)，只有一把鎖會(huì)效率低下，分區(qū)見上鎖又邏輯復(fù)雜。Go1.9 起支持的 sync.Map，其支持并發(fā)讀寫 map。采取了 “空間換時(shí)間” 的機(jī)制，冗余了兩個(gè)數(shù)據(jù)結(jié)構(gòu)，分別是：read 和 dirty，減少加鎖對(duì)性能的影響。

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

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

到此這篇關(guān)于Go map底層實(shí)現(xiàn)與擴(kuò)容規(guī)則和特性分類詳細(xì)講解的文章就介紹到這了,更多相關(guān)Go map底層實(shí)現(xiàn)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論