Golang map實現原理深入分析
簡介
本文主要通過探究在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
到此這篇關於Golang map實現原理深入分析的文章就介紹到這瞭,更多相關Golang map內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet!