1、哈希表

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

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

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

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

• m=5 （00000101）
• m-1 （00000100）

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

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

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

hmap

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

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

bmap

buckets 則是指向哈希表節(jié)點 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結構是靜態(tài)結構，在編譯過程中runtime.bmap會拓展成以下結構體：

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

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

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

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

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

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

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

mapextra與溢出桶

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

hmap 中最后有 extra 字段，它是指向mapextra結構體，里邊記錄的都是溢出桶相關的信息。

type mapextra struct {
  overflow *[]*bmap     // 記錄已使用的溢出桶的地址
  oldoverflow *[]*bmap  // 擴容階段舊桶使用的溢出桶地址
  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結構體。
• mapextra 中的 nextOverflow 指向下一個空閑溢出桶 33 號。

3、擴容規(guī)則

map擴容時使用漸進式擴容。

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

翻倍擴容

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

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

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

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

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

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

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

等量擴容

雖然沒有超過負載因子限制，但是使用溢出桶過多，就會觸發(fā)等量擴容，創(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ù)量增多，但負載因子又不高。同樣數(shù)目的鍵值對，遷移到新桶中會把松散的鍵值對重新排列一次，使其排列的更加緊湊，進而保證更快的存取，這就是等量擴容的意義所在。

4、其他特性

map遍歷無序

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

主要原因有2點：

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

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

map非線程安全

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

官方推薦對 map 上讀寫鎖，一個匿名結構（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ū)見上鎖又邏輯復雜。Go1.9 起支持的 sync.Map，其支持并發(fā)讀寫 map。采取了 “空間換時間” 的機制，冗余了兩個數(shù)據(jù)結構，分別是：read 和 dirty，減少加鎖對性能的影響。

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

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

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

最新評論