Golang map實現(xiàn)原理深入分析
簡介
本文主要通過探究在golang 中map的數(shù)據(jù)結(jié)構(gòu)及源碼實現(xiàn)來學(xué)習(xí)和了解map的特性,共包含map的模型探究、存取、擴容等內(nèi)容。歡迎大家共同討論。
Map 的底層內(nèi)存模型
在 goland 的源碼中表示 map 的底層 struct 是 hmap,其是 hashmap 的縮寫
type hmap struct { // map中存入元素的個數(shù), golang中調(diào)用len(map)的時候直接返回該字段 count int // 狀態(tài)標(biāo)記位,通過與定義的枚舉值進(jìn)行&操作可以判斷當(dāng)前是否處于這種狀態(tài) flags uint8 B uint8 // 2^B 表示bucket的數(shù)量, B 表示取hash后多少位來做bucket的分組 noverflow uint16 // overflow bucket 的數(shù)量的近似數(shù) hash0 uint32 // hash seed (hash 種子) 一般是一個素數(shù) buckets unsafe.Pointer // 共有2^B個 bucket ,但是如果沒有元素存入,這個字段可能為nil oldbuckets unsafe.Pointer // 在擴容期間,將舊的bucket數(shù)組放在這里, 新buckets會是這個的兩倍大 nevacuate uintptr // 表示已經(jīng)完成擴容遷移的bucket的指針, 地址小于當(dāng)前指針的bucket已經(jīng)遷移完成 extra *mapextra // optional fields }
B 是 buckets 數(shù)組的長度的對數(shù), 即 bucket 數(shù)組的長度是 2^B。bucket 的本質(zhì)上是一個指針,指向了一片內(nèi)存空間,其指向的 struct 如下所示:
// A bucket for a Go map. type bmap struct { tophash [bucketCnt]uint8 }
但這只是表面(src/runtime/hashmap.go)的結(jié)構(gòu),編譯期間會給它加料,動態(tài)地創(chuàng)建一個新的結(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 存滿了之后 }
bmap 就是我們常說的“桶”的底層數(shù)據(jù)結(jié)構(gòu), 一個桶中可以存放最多 8 個 key/value, map 使用 hash 函數(shù) 得到 hash 值決定分配到哪個桶, 然后又會根據(jù) hash 值的高 8 位來尋找放在桶的哪個位置 具體的 map 的組成結(jié)構(gòu)如下圖所示:
Map 的存與取
在 map 中存與取本質(zhì)上都是在進(jìn)行一個工作, 那就是:
查詢當(dāng)前 k/v 應(yīng)該存儲的位置。
賦值/取值, 所以我們理解了 map 中 key 的定位我們就理解了存取。
底層代碼
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) { // map 為空,或者元素數(shù)為 0,直接返回未找到 if h == nil || h.count == 0 { return unsafe.Pointer(&zeroVal[0]), false } // 不支持并發(fā)讀寫 if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } // 根據(jù)hash 函數(shù)算出hash值,注意key的類型不同可能使用的hash函數(shù)也不同 hash := t.hasher(key, uintptr(h.hash0)) // 如果 B = 5,那么結(jié)果用二進(jìn)制表示就是 11111 , 返回的是B位全1的值 m := bucketMask(h.B) // 根據(jù)hash的后B位,定位在bucket數(shù)組中的位置 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize))) // 當(dāng) h.oldbuckets 非空時,說明 map 發(fā)生了擴容 // 這時候,新的 buckets 里可能還沒有老的內(nèi)容 // 所以一定要在老的里面找,否則有可能發(fā)生“消失”的詭異現(xiàn)象 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 個元素后,就再也放不下了,這時候會創(chuàng)建新的 bucket,掛在原來的 bucket 的 overflow 指針成員上 // 遍歷當(dāng)前bucket的所有鏈?zhǔn)絙ucket for ; b != nil; b = b.overflow(t) { // 在bucket的8個位置上查詢 for i := uintptr(0); i < bucketCnt; i++ { // 如果找到了相等的 tophash,那說明就是這個 bucket 了 if b.tophash[i] != top { continue } // 根據(jù)內(nèi)存結(jié)構(gòu)定位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 一樣都是在初始化時首先申請較小的內(nèi)存空間,在 map 的不斷存入的過程中,動態(tài)的進(jìn)行擴容。擴容共有兩種,增量擴容與等量擴容(重新排列并分配內(nèi)存)。下面我們來了解一下擴容的觸發(fā)方式:
負(fù)載因子超過閾值,源碼里定義的閾值是 6.5。(觸發(fā)增量擴容)
overflow 的 bucket 數(shù)量過多:當(dāng) B 小于 15,也就是 bucket 總數(shù) 2^B 小于 2^15 時,如果 overflow 的 bucket 數(shù)量超過 2^B;當(dāng) B >= 15,也就是 bucket 總數(shù) 2^B 大于等于 2^15,如果 overflow 的 bucket 數(shù)量超過 2^15。(觸發(fā)等量擴容)
第一種情況
第二種情況
Map的有序性
先說結(jié)論,在 golang 中 map 是無序的,準(zhǔn)確的說是無法嚴(yán)格保證順序的, 從上面的源碼中我們可以知道,golang 中 map 在擴容后,可能會將部分 key 移至新內(nèi)存,由于在擴容搬移數(shù)據(jù)過程中,并未記錄原數(shù)據(jù)位置, 并且在 golang 的數(shù)據(jù)結(jié)構(gòu)中也并未保存數(shù)據(jù)的順序,所以那么這一部分在擴容后實際上就已經(jīng)是無序的了。
遍歷的過程,其實就是按順序遍歷內(nèi)存地址,同時按順序遍歷內(nèi)存地址中的 key。但這時已經(jīng)是無序的了。但是如果我就一個 map,我保證不會對 map 進(jìn)行修改刪除等操作,那么按理說沒有擴容就不會發(fā)生改變。但也是因為這樣,GO 才在源碼中 但是有一個有趣的現(xiàn)象,就算不對 map 進(jìn)行插入刪除等操作致使其擴容,其在遍歷過程中仍是無序的。
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")
以上的運行結(jié)果是
不難看出,即使不對 map 進(jìn)行擴容,在多次遍歷時也是無序的,這是因為 golang 官方在設(shè)計時故意加上隨機的元素,將遍歷 map 的順序隨機化,用來防止使用者用來順序遍歷。
而這是有風(fēng)險的代碼,在 GO 的嚴(yán)格語法規(guī)則下,是堅決不提倡的。所以我們在使用 map 時一定要記得其是無序的,不要依賴其順序。
Map 的并發(fā)
首先我們大家都知道,在 golang 中 map 并不是一個并發(fā)安全的數(shù)據(jù)結(jié)構(gòu),當(dāng)幾個 goruotine 同時對一個 map 進(jìn)行讀寫操作時,就會出現(xiàn)并發(fā)寫問題:fatal error: concurrent map writes。但是為什么 map 是不支持并發(fā)安全的呢, 主要是因為成本與效益。
官方答復(fù)原因如下:
- 典型使用場景:map 的典型使用場景是不需要從多個 goroutine 中進(jìn)行安全訪問。
- 非典型場景(需要原子操作):map 可能是一些更大的數(shù)據(jù)結(jié)構(gòu)或已經(jīng)同步的計算的一部分。
性能場景考慮:若是只是為少數(shù)程序增加安全性,導(dǎo)致 map 所有的操作都要處理 mutex,將會降低大多數(shù)程序的性能。同時 golang 提供了并發(fā)安全的 sync map。
// 不支持并發(fā)讀寫 if h.flags&hashWriting != 0 { throw("concurrent map read and map write") }
但是我們又有疑問了,為什么 golang map 并發(fā)沖突了不拋一個 error 出來,或者 panic 掉,而是要讓程序 panic,選擇讓程序 crash 崩潰掉。這里是 golang 官方出于權(quán)衡風(fēng)險和 map 使用復(fù)雜度場景考慮的,首先 map 在官方中就明確表示不支持并發(fā)讀寫, 所以并發(fā)對 map 進(jìn)行讀寫操作本身就是不正確的。
場景假設(shè)一:如果 map 選擇在寫入或者讀取時增加 error 返回值,會導(dǎo)致程序在使用 map 時就無法像現(xiàn)在一樣,需要額外的捕獲并判斷 err。
場景假設(shè)二:如果 map 選擇 panic(可被 recover),此時如果出現(xiàn)并發(fā)寫入數(shù)據(jù)的場景,就會導(dǎo)致走進(jìn) recover 中,如果沒有對這種場景進(jìn)行特殊處理,就會導(dǎo)致 map 中存在臟數(shù)據(jù),此時程序在使用 map 時就會引發(fā)不可預(yù)知的錯誤,此時排查起來也是很難找到問題的根因的。
所以 golang 在考慮了這些場景后,選擇明確的拋出 crash 崩潰異常,使得風(fēng)險被提前暴露??梢悦鞔_的定位到問題點。綜上所述我們在使用 map 時,已經(jīng)要嚴(yán)格保障其是在單線程內(nèi)使用的,如果有多線程場景,建議使用 sync map
到此這篇關(guān)于Golang map實現(xiàn)原理深入分析的文章就介紹到這了,更多相關(guān)Golang map內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
go語言切片slice使用細(xì)節(jié)和注意事項整理大全
這篇文章主要給大家介紹了關(guān)于go語言切片slice使用細(xì)節(jié)和注意事項整理的相關(guān)資料,需要的朋友可以參考下2024-05-05Golang WebView跨平臺的桌面應(yīng)用庫的使用
Golang WebView是一個強大的桌面應(yīng)用庫,本文介紹了Golang WebView的特點和使用方法,并列舉示例詳細(xì)的介紹了其在實際項目中的應(yīng)用,具有一定的參考價值,感興趣的可以了解一下2024-03-03golang通過遞歸遍歷生成樹狀結(jié)構(gòu)的操作
這篇文章主要介紹了golang通過遞歸遍歷生成樹狀結(jié)構(gòu)的操作,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04