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