作者｜?趙燕輝
簡介
本文主要通過探究在golang 中map的數據結構及源碼實現來學習和了解map的特性，共包含map的模型探究、存取、擴容等內容。歡迎大家共同討論。
Map 的底層內存模型
在 goland 的源碼中表示 map 的底層 struct 是 hmap，其是 hashmap 的縮寫
type hmap struct {
// map中存入元素的個數， golang中調用len(map)的時候直接返回該字段
count int
// 狀態標記位，通過與定義的枚舉值進行&操作可以判斷當前是否處于這種狀態
flags uint8
B uint8 // 2^B 表示bucket的數量， B 表示取hash后多少位來做bucket的分組
noverflow uint16 // overflow bucket 的數量的近似數
hash0 uint32 // hash seed （hash 種子） 一般是一個素數
buckets unsafe.Pointer // 共有2^B個 bucket ，但是如果沒有元素存入，這個字段可能為nil
oldbuckets unsafe.Pointer // 在擴容期間，將舊的bucket數組放在這里， 新buckets會是這個的兩倍大
nevacuate uintptr // 表示已經完成擴容遷移的bucket的指針， 地址小于當前指針的bucket已經遷移完成
extra *mapextra // optional fields
}B 是 buckets 數組的長度的對數， 即 bucket 數組的長度是 2^B。bucket 的本質上是一個指針，指向了一片內存空間，其指向的 struct 如下所示：
// A bucket for a Go map.
type bmap struct {
tophash [bucketCnt]uint8
}
但這只是表面(src/runtime/hashmap.go)的結構，編譯期間會給它加料，動態地創建一個新的結構：
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr // 內存對齊使用，可能不需要
overflow uintptr // 當bucket 的8個key 存滿了之后
}bmap 就是我們常說的“桶”的底層數據結構， 一個桶中可以存放最多 8 個 key/value, map 使用 hash 函數 得到 hash 值決定分配到哪個桶， 然后又會根據 hash 值的高 8 位來尋找放在桶的哪個位置 具體的 map 的組成結構如下圖所示：
Map 的存與取
在 map 中存與取本質上都是在進行一個工作， 那就是:
- 查詢當前 k/v 應該存儲的位置。
- 賦值/取值， 所以我們理解了 map 中 key 的定位我們就理解了存取。
底層代碼
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
// map 為空，或者元素數為 0，直接返回未找到
if h == nil || h.count == 0 {
return unsafe.Pointer(&zeroVal[0]), false
}
// 不支持并發讀寫
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
// 根據hash 函數算出hash值，注意key的類型不同可能使用的hash函數也不同
hash := t.hasher(key, uintptr(h.hash0))
// 如果 B = 5，那么結果用二進制表示就是 11111 ， 返回的是B位全1的值
m := bucketMask(h.B)
// 根據hash的后B位，定位在bucket數組中的位置
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
// 當 h.oldbuckets 非空時，說明 map 發生了擴容
// 這時候，新的 buckets 里可能還沒有老的內容
// 所以一定要在老的里面找，否則有可能發生“消失”的詭異現象
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// 說明之前只有一半的 bucket，需要除 2
m >>= 1
}
oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
if !evacuated(oldb) {
b = oldb
}
}
// tophash 取其高 8bit 的值
top := tophash(hash)
// 一個 bucket 在存儲滿 8 個元素后，就再也放不下了，這時候會創建新的 bucket，掛在原來的 bucket 的 overflow 指針成員上
// 遍歷當前bucket的所有鏈式bucket
for ; b != nil; b = b.overflow(t) {
// 在bucket的8個位置上查詢
for i := uintptr(0); i < bucketCnt; i++ {
// 如果找到了相等的 tophash，那說明就是這個 bucket 了
if b.tophash[i] != top {
continue
}
// 根據內存結構定位key的位置
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey {
k = *((*unsafe.Pointer)(k))
}
// 校驗找到的key是否匹配
if t.key.equal(key, k) {
// 定位v的位置
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
if t.indirectvalue {
v = *((*unsafe.Pointer)(v))
}
return v, true
}
}
}
// 所有 bucket 都沒有找到，返回零值和 false
return unsafe.Pointer(&zeroVal[0]), false
}尋址過程
Map 的擴容
在 golang 中 map 和 slice 一樣都是在初始化時首先申請較小的內存空間，在 map 的不斷存入的過程中，動態的進行擴容。擴容共有兩種，增量擴容與等量擴容（重新排列并分配內存）。下面我們來了解一下擴容的觸發方式：
- 負載因子超過閾值，源碼里定義的閾值是 6.5。(觸發增量擴容)
- overflow 的 bucket 數量過多：當 B 小于 15，也就是 bucket 總數 2^B 小于 2^15 時，如果 overflow 的 bucket 數量超過 2^B；當 B >= 15，也就是 bucket 總數 2^B 大于等于 2^15，如果 overflow 的 bucket 數量超過 2^15。（觸發等量擴容）
第一種情況
第二種情況
Map 的有序性
先說結論，在 golang 中 map 是無序的，準確的說是無法嚴格保證順序的， 從上面的源碼中我們可以知道，golang 中 map 在擴容后，可能會將部分 key 移至新內存，由于在擴容搬移數據過程中，并未記錄原數據位置， 并且在 golang 的數據結構中也并未保存數據的順序，所以那么這一部分在擴容后實際上就已經是無序的了。
遍歷的過程，其實就是按順序遍歷內存地址，同時按順序遍歷內存地址中的 key。但這時已經是無序的了。但是如果我就一個 map，我保證不會對 map 進行修改刪除等操作，那么按理說沒有擴容就不會發生改變。但也是因為這樣，GO 才在源碼中 但是有一個有趣的現象，就算不對 map 進行插入刪除等操作致使其擴容，其在遍歷過程中仍是無序的。
objMap := make(map[string]int)
for i := 0; i < 5; i++ {
objMap[strconv.Itoa(i)] = i
}
for i := 0 ; i < 5; i ++ {
var valStr1, valStr2 string
for k, v := range objMap {
fmt.Println(k)
fmt.Println(v)
valStr1 += k
}
for k, v := range objMap {
fmt.Println(k)
fmt.Println(v)
valStr2 += k
}
fmt.Println(valStr1 == valStr2)
if valStr1 != valStr2 {
fmt.Println("not equal")
}
}
fmt.Println("end")
?以上的運行結果是
?不難看出，即使不對 map 進行擴容，在多次遍歷時也是無序的，這是因為 golang 官方在設計時故意加上隨機的元素，將遍歷 map 的順序隨機化，用來防止使用者用來順序遍歷。
而這是有風險的代碼，在 GO 的嚴格語法規則下，是堅決不提倡的。所以我們在使用 map 時一定要記得其是無序的，不要依賴其順序。
Map 的并發
首先我們大家都知道，在 golang 中 map 并不是一個并發安全的數據結構，當幾個 goruotine 同時對一個 map 進行讀寫操作時，就會出現并發寫問題：fatal error: concurrent map writes。但是為什么 map 是不支持并發安全的呢， 主要是因為成本與效益。
官方答復原因如下：?
- 典型使用場景：map 的典型使用場景是不需要從多個 goroutine 中進行安全訪問。
- 非典型場景（需要原子操作）：map 可能是一些更大的數據結構或已經同步的計算的一部分。
?性能場景考慮：若是只是為少數程序增加安全性，導致 map 所有的操作都要處理 mutex，將會降低大多數程序的性能。同時 golang 提供了并發安全的 sync map。
， // 不支持并發讀寫
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
但是我們又有疑問了，為什么 golang map 并發沖突了不拋一個 error 出來，或者 panic 掉，而是要讓程序 panic，選擇讓程序 crash 崩潰掉。這里是 golang 官方出于權衡風險和 map 使用復雜度場景考慮的，首先 map 在官方中就明確表示不支持并發讀寫， 所以并發對 map 進行讀寫操作本身就是不正確的。
場景假設一：如果 map 選擇在寫入或者讀取時增加 error 返回值，會導致程序在使用 map 時就無法像現在一樣，需要額外的捕獲并判斷 err。
場景假設二：如果 map 選擇 panic（可被 recover），此時如果出現并發寫入數據的場景，就會導致走進 recover 中，如果沒有對這種場景進行特殊處理，就會導致 map 中存在臟數據，此時程序在使用 map 時就會引發不可預知的錯誤，此時排查起來也是很難找到問題的根因的。
所以 golang 在考慮了這些場景后，選擇明確的拋出 crash 崩潰異常，使得風險被提前暴露。可以明確的定位到問題點。綜上所述我們在使用 map 時，已經要嚴格保障其是在單線程內使用的，如果有多線程場景，建議使用 sync map?
