Go數(shù)據(jù)結(jié)構(gòu)之映射map方式
Map作為Go原生支持的另一個主要的數(shù)據(jù)結(jié)構(gòu),其使用頻繁程度與切片有過之而無不及。用一句話描述map:存儲鍵-值對映射關(guān)系的無序數(shù)據(jù)結(jié)構(gòu),保證鍵的唯一性但不保證并發(fā)操作安全。
本文將介紹map的基本使用以及go 1.16版本其底層實現(xiàn)。
1 map的使用
1.1 map基本使用
聲明/初始化,一般有如下三種方式,
- 使用var聲明一個map變量,需要指定鍵值對分別的類型,這種方式僅僅只是聲明,返回的是一個nil map,既沒有分配內(nèi)存,無法對其進行寫入操作。如果要對其進行寫入操作,則還需要為其分配內(nèi)存。
- 比較常用的是直接使用make初始化,在初始化map類型時,可以傳一個容量(通常是不傳這個參數(shù),因為map底層有自動擴容機制,且無法準(zhǔn)確預(yù)估m(xù)ap所需的容量)。
- 第三種方式就是直接在定義的同時,對map進行寫入操作,這種方式適用于確定部分需要寫入map的場景
// 聲明一個map變量,鍵是string類型,值是int類型 // 但此時m還是一個nil map,無法對其進行寫入 var m map[string]int m["1"] = 1 // 報錯,nil map無法寫入 m = make(map[string]int) // 使用make為map分配內(nèi)存,此時可以正常寫入 // 可以將聲明和分配內(nèi)存合二為一,直接使用make函數(shù)為map分配內(nèi)存 // make函數(shù)第一個參數(shù)是map的類型,第二個參數(shù)可選,表示map的容量大小 m1 := make(map[string]int) // 第三種方式就是在定義的時候,連帶著給map進行賦值 m2 := map[string]int{ "1": 1, "2": 2, }
賦值,其實就比較簡單,直接將鍵放入中括號,對應(yīng)的值放在等號右邊即可,如果鍵之間存在,則實現(xiàn)更新;不存在,則實現(xiàn)插入。這里需要特別注意的是
- 對于nil map無法進行賦值操作,如果對nil map進行賦值,則會panic。
- map中的value是不可尋址的,無法直接通過map值進行更新操作,但有兩種例外,1)value為int類型,編譯器會通過語法糖進行直接更新;2)value為指針類型時,也能直接通過map值進行更新操作。
m := make(map[string]int) m["1"] = 1 type Person struct { name string age int } m1 := map[string]Person{} m1["Tom"].age++ // 錯誤,因為map的值是無法尋址的,這種情況需要接受舊值,將修改完后的值重新賦值 m2 := map[string]*Person{} m2["Tom"].age++ // 正確,這種情況下沒有改變map中的value,而是通過指針找到對應(yīng)存儲的值進行修改
- 查找,map對于查詢的處理原則就是,如果key不存在,則返回value對應(yīng)的零值(nil map也能進行查找,只是對于所有的查詢都返回value類型零值)。如果需要判斷key是否存在,則推薦使用v, ok := m["1"]的寫法,ok為true表示key存在于map中。
var m map[string]int fmt.Println(m["1"]) // nil map可以進行查找,返回的是value的默認(rèn)零值 // 如果需要判斷key是否存在于map中,則可以使用如下寫法 if _, ok := m["1"]; ok { fmt.Println("key存在") } else { fmt.Println("key不存在") }
- 刪除,主要通過調(diào)用delete函數(shù)實現(xiàn)map中鍵值對的刪除操作,對于nil map也能執(zhí)行刪除操作,如果待刪除的key不存在,則不做任何處理。
var m map[string]int delete(m ,"1")
- 遍歷,只能通過for range進行map的遍歷操作,而且遍歷是無序的,每次遍歷結(jié)果都不一樣,這樣做:一是為了讓使用者不依賴于map的遍歷順序,二也是與map的底層實現(xiàn)有很大關(guān)系。實際開發(fā)過程中,如果要確定的遍歷順序,往往需要借助切片保存順序,然后通過遍歷切片去map中取值。
m := map[string]int{ "1": 1, "2": 2, } // 無序遍歷,每次遍歷的順序都不一樣 for k, v := range m { fmt.Println(k, v) }
1.2 map注意事項
map是一種引用傳遞類型,其作為函數(shù)參數(shù)進行傳遞時,函數(shù)內(nèi)部修改會直接影響調(diào)用者。
map遍歷是無序的,即每次遍歷的結(jié)果都不一樣,可能是Go的設(shè)計者不想使用者依賴與map的遍歷順序性,個人認(rèn)為這個也是與其底層實現(xiàn)有關(guān),如果要保證有序,則需要維護額外的數(shù)據(jù)結(jié)構(gòu),與Go極簡的設(shè)計原則不符。
map的key必須是支持==、!=運算的數(shù)據(jù)類型(map的key可以為float類型、chan類型自定義結(jié)構(gòu)體,但不能是func、map、slice,value則可以為任意數(shù)據(jù)類型)。
因內(nèi)存訪問安全和哈希算法等緣故,字典被設(shè)置成“not addressable”,故不能直接修改value的值(實際上就是不允許直接修改map中的值)。如果需要對value進行修改,一般將需要將整個value返回,修改后再重新賦值,或直接將value設(shè)置成指針類型(指針能修改的原因是,通過指針修改原結(jié)構(gòu)體中的數(shù)據(jù),但沒有修改map中保存的數(shù)據(jù))。但是,如果map的value為int,那么可以直接修改value,例如:
m := map[string]int{"test":1} m["test"]++ // 實際上是語法糖 /* temp := m["test"] temp += 1 m["test"] = temp */
map并不是多線程讀寫安全的,在多線程開發(fā)中使用map需要特別小心,解決此問題一般可以使用sync.RWMutex進行保護或直接使用sync.Map。
訪問不存在的主鍵,返回對應(yīng)key的零值,并不會panic。刪除不存在的鍵值,也不會引發(fā)錯誤。
可對nil的字典進行讀、刪除操作,但是寫會引發(fā)panic!即,從nil的字典中,讀出來的都是value的默認(rèn)值;對nil字典進行刪除操作,實際不會產(chǎn)生任何效果。
2 map的底層數(shù)據(jù)結(jié)構(gòu)
在Go 1.16版本中,使用了hash table來實現(xiàn)map(Go 1.24版本已經(jīng)使用Swiss table作為map的底層實現(xiàn),后續(xù)有空研究下),其底層實現(xiàn)主要借助hmap、bmap,下面詳細介紹下這兩個數(shù)據(jù)。
2.1 bmap
bmap是Go map中bucket的抽象,為提高存儲效率,每一個 bmap
都能存儲 8 個鍵值對。
當(dāng)哈希表中存儲的數(shù)據(jù)過多,單個桶已經(jīng)裝滿時就會使用 extra.nextOverflow
中桶存儲溢出的數(shù)據(jù)。上述兩種不同的桶在內(nèi)存中是連續(xù)存儲的,我們在這里將它們分別稱為正常桶和溢出桶。
bucket
的結(jié)構(gòu)體 bmap
在 Go 語言源代碼中的定義只包含一個簡單的 tophash
字段,tophash
存儲了鍵的哈希的高 8 位,通過比較不同鍵的哈希的高 8 位可以減少訪問鍵值對次數(shù)以提高性能。在運行期間,bmap
結(jié)構(gòu)體其實不止包含 tophash
字段,因為哈希表中可能存儲不同類型的鍵值對,而且 Go 語言也不支持泛型,所以鍵值對占據(jù)的內(nèi)存空間大小只能在編譯時進行推導(dǎo)。runtime.bmap
中的其他字段在運行時也都是通過計算內(nèi)存地址的方式訪問的,所以它的定義中就不包含這些字段,不過我們能根據(jù)編譯期間的 cmd/compile/internal/gc.bmap
函數(shù)重建它的結(jié)構(gòu):
type bmap struct { tophash [bucketCnt]uint8 } // 利用../go/src/cmd/compile/internal/gc/reflect.go文件中的bmap函數(shù)反推 type bmap struct { topbits [8]uint8 keys [8]keytype values [8]valuetype overflow uintptr }
桶和溢出桶
- 桶(bucket): 每個桶包含固定數(shù)量的鍵值對,Go 中每個桶默認(rèn)可以存儲 8 對鍵值對。
- 溢出桶(overflow bucket): 當(dāng)一個桶已滿但仍需插入新的鍵值對時,會創(chuàng)建一個新的桶作為當(dāng)前桶的溢出桶。
溢出桶的作用
解決哈希沖突:
- 在理想情況下,每個鍵會被分配到不同的桶中。然而,在實際應(yīng)用中,由于哈希函數(shù)的特性,多個鍵可能會被分配到同一個桶中(即哈希沖突)。
- 當(dāng)一個桶已滿且仍然需要存儲新的鍵值對時,Go 會創(chuàng)建一個新的桶作為當(dāng)前桶的溢出桶,并將新鍵值對存儲在這個溢出桶中。
管理存儲空間:
- 溢出桶允許動態(tài)擴展 map 的存儲容量。通過使用鏈表結(jié)構(gòu)(由多個溢出桶組成),可以有效地管理超過初始桶容量的數(shù)據(jù)。
- 這種機制避免了頻繁地重新分配和復(fù)制整個哈希表,從而提高了性能。
高效查找:
- 即使存在多個溢出桶,Go 的
map
實現(xiàn)仍然能夠高效地進行鍵值對的查找。通過遍歷主桶及其關(guān)聯(lián)的溢出桶,可以快速找到所需的鍵值對。 - 溢出桶的設(shè)計確保了查找操作在平均情況下仍然是 O(1) 時間復(fù)雜度。
2.2 hmap
hmap是Go實現(xiàn)map的底層數(shù)據(jù)結(jié)構(gòu),主要用于管理bucket的擴容、元素的查找/刪除等,其具體結(jié)構(gòu)如下:
type hmap struct { count int // 元素個數(shù),調(diào)用 len(map) 時,直接返回此值 flags uint8 // 標(biāo)記,對應(yīng) const 中 '// flags' 下的幾個狀態(tài) B uint8 // buckets 的對數(shù) log_2 noverflow uint16 // overflow 的 bucket 近似數(shù) hash0 uint32 // 計算 key 的哈希的時候會傳入哈希函數(shù) buckets unsafe.Pointer // 指向 buckets 數(shù)組,大小為 2^B。如果元素個數(shù)為0,就為 nil // 擴容的時候,buckets 長度會是 oldbuckets 的兩倍 oldbuckets unsafe.Pointer // 指向擴容前的數(shù)組(漸進式擴容) nevacuate uintptr // 指示擴容進度,小于此地址的 buckets 遷移完成 extra *mapextra //保存溢出桶的信息 } type mapextra struct { // 如果 key 和 value 都不包含指針,并且可以被 inline(<=128 字節(jié)) // 使用 extra 來存儲 overflow bucket,這樣可以避免 GC 掃描整個 map // 然而 bmap.overflow 也是個指針。這時候我們只能把這些 overflow 的指針 // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了 overflow *[]*bmap // overflow 包含的是 hmap.buckets 的 overflow 的 bucket oldoverflow *[]*bmap // oldoverflow 包含擴容時的 hmap.oldbuckets 的 overflow 的 bucket nextOverflow *bmap // 指向空閑的 overflow bucket 的指針 }
3 map實現(xiàn)源碼
3.1 map的初始化
使用make函數(shù)創(chuàng)建map:
make(map[k]v, hint)
在 hint <= 8(鍵值對的個數(shù)) 時,會調(diào)用 makemap_small 來進行初始化,如果 hint > 8,則調(diào)用 makemap。在預(yù)估待插入的元素個數(shù)小于8或者需要的bucket為0時,Go編譯器會采用延遲分配策略,只有在真正往map中寫入數(shù)據(jù)時, 才會分配bucket。
makemap函數(shù)主要流程如下:
- 內(nèi)存安全檢查:通過計算預(yù)估內(nèi)存 = 元素數(shù)量(hint) × 單個桶大小(t.bucket.size),防止內(nèi)存溢出攻擊和無效分配,若檢測失敗,將 hint 重置為 0(后續(xù)按最小分配處理)
- 初始化 hmap 結(jié)構(gòu)體:若傳入
h
為 nil,新建hmap
結(jié)構(gòu)(map 的底層表示);隨后h.hash0 = fastrand()
:生成隨機哈希種子,用于增加哈希隨機性,防止哈希碰撞攻擊,相同 key 在不同 map 中產(chǎn)生不同哈希值 - 計算桶數(shù)量指數(shù) B:根據(jù)負(fù)載因子確定合適的桶數(shù)量(
2^B
個桶),循環(huán)增加B
直到滿足:6.5 * 2^B >= hint
- 分配桶數(shù)組:若
B == 0
(hint=0),延后到首次寫入時分配;其他情況,調(diào)用makeBucketArray
分配主桶數(shù)組(長度為2^B
),如果 B >= 4 額外預(yù)分配溢出桶(減少運行時分配開銷,這里也說明正常桶與溢出桶是內(nèi)存地址連續(xù)的數(shù)組) - 溢出桶管理:若存在預(yù)分配溢出桶(
nextOverflow != nil
),初始化h.extra
結(jié)構(gòu),記錄可用溢出桶鏈表。最后一個溢出桶的overflow指針會指向第一個正常桶,以此形成一個環(huán)。
func makemap_small() *hmap { h := new(hmap) h.hash0 = fastrand() return h } func makemap(t *maptype, hint int, h *hmap) *hmap { // 進行內(nèi)存大小的檢查,如果溢出或者內(nèi)存超出最大內(nèi)存空間,將hint(元素個數(shù))設(shè)置為0 mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size) if overflow || mem > maxAlloc { hint = 0 } // 初始化 Hmap,即如果當(dāng)前Hamp為空,則new hmap // 設(shè)置map的哈希計算種子隨機數(shù)hash0 if h == nil { h = new(hmap) } h.hash0 = fastrand() // Find the size parameter B which will hold the requested # of elements. // For hint < 0 overLoadFactor returns false since hint < bucketCnt. // 按照提供的元素個數(shù),根據(jù)負(fù)載因子計算合理的 B 值,以確保 6.5 * 2 ^ B >= hint B := uint8(0) for overLoadFactor(hint, B) { B++ } h.B = B // allocate initial hash table // if B == 0, the buckets field is allocated lazily later (in mapassign) // If hint is large zeroing this memory could take a while. // 初始化 hash table // 如果 B 等于 0,那么 buckets 就會在賦值( mapassign )的時候再分配 // 如果長度比較大,分配內(nèi)存會花費長一點 if h.B != 0 { var nextOverflow *bmap h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) if nextOverflow != nil { h.extra = new(mapextra) h.extra.nextOverflow = nextOverflow } } return h } func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) { // uintptr(1) << ( b & (sys.PtrSize*8-1)) 2^b base := bucketShift(b) nbuckets := base // 當(dāng)桶的數(shù)量小于2^4 時,由于數(shù)據(jù)較少、使用溢出桶的可能性較低, // 這時就會省略創(chuàng)建溢出桶的過程以減少額外開銷 if b >= 4 { // 當(dāng)桶的數(shù)量多于2^4時,就會額外創(chuàng)建 2^(b-4)個溢出桶 // 根據(jù)內(nèi)存的分配規(guī)則,計算出合適的內(nèi)存大小,并確定桶的數(shù)量 nbuckets += bucketShift(b - 4) sz := t.bucket.size * nbuckets up := roundupsize(sz) if up != sz { nbuckets = up / t.bucket.size } } // 如果桶之前沒有分配內(nèi)存,就初始化一個數(shù)組 // 反之,直接沿用之前的,并清理掉本次初始化所需要內(nèi)存大小的內(nèi)存,備用 if dirtyalloc == nil { buckets = newarray(t.bucket, int(nbuckets)) } else { // dirtyalloc was previously generated by // the above newarray(t.bucket, int(nbuckets)) // but may not be empty. buckets = dirtyalloc size := t.bucket.size * nbuckets if t.bucket.ptrdata != 0 { memclrHasPointers(buckets, size) } else { memclrNoHeapPointers(buckets, size) } } // 如果創(chuàng)建的桶數(shù)量不等于2^b,說明分配了額外的溢出桶 if base != nbuckets { // 2^b個桶后面就是溢出桶 nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize))) // 取nextOverflow 里面的最后一個元素,并把最后一個buckets 的末尾偏移的指針指向空閑的bucket (目前就是第一個buckets了) last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize))) last.setoverflow(t, (*bmap)(buckets)) } return buckets, nextOverflow }
下圖是不同B值時,初始化得到的map,如果B小于4,則編譯器不會為map分配溢出桶(認(rèn)為map的規(guī)模比較小,需要使用到溢出桶的概率不大);只有在B大于等于4時,才會為map分配 2^(B-4)個溢出桶,需要注意的是正常桶與溢出桶在底層是一個內(nèi)存地址連續(xù)的數(shù)組!
3.2 map的賦值
map的賦值操作核心是:通過hash函數(shù),找到key插入到bmap數(shù)據(jù)的下標(biāo)索引,然后就需要遍歷該下標(biāo)包含的所有bucket,尋找第一個能插入的位置或者尋找該key是否已經(jīng)存在。hash值在這里的主要作用有兩個:
- tophash:由于一個bucket存儲了8個鍵值對,為了快速比較key,編譯器會將hash值的前8位(64位操作系統(tǒng))存儲到bucket到tophash數(shù)組。
- 確定bmap的索引:hash值與map的B值進行mask操作,確定該key存儲的下標(biāo)位置。
賦值操作底層mapassign函數(shù)的主要流程:
1. 安全檢查和初始化
- 空 map 檢查:對 nil map 賦值會 panic
- 并發(fā)寫檢查:檢測到其他 goroutine 正在寫 map 時拋出異常(Go map 非并發(fā)安全)
- 哈希計算:使用類型特定的哈希函數(shù)計算鍵的哈希值
- 標(biāo)記寫操作:設(shè)置
hashWriting
標(biāo)志位(防止并發(fā)寫) - 延遲初始化:若桶數(shù)組未分配,分配一個桶(最小化空 map 開銷)
2. 定位桶和搜索鍵
雙層循環(huán)搜索:外層遍歷對應(yīng)index下所有的bucket,內(nèi)層循環(huán)處理每個桶的 8 個槽。
- 遍歷時,需要記錄第一個可以插入的位置。
- 同時,需要遍歷完全插入位置下,所有的bucket。如果遇到tophash相等,進一步判斷key是否一致,key也相等,則更新key的信息并結(jié)束循環(huán)。
- 遇到
emptyRest
(后續(xù)全空)時,提前終止搜索。
3. 鍵不存在時的處理
- 擴容條件:負(fù)載因子超標(biāo)(
count/(2^B) > 6.5
);溢出桶過多(noverflow >= 2^min(B, 15)
)。 - 擴容后重試:桶布局改變需重新定位
- 分配新溢出桶:當(dāng)所有桶都無空閑槽時,則申請一個溢出桶
4. 收尾工作
- 返回值的存儲位置:調(diào)用方通過此指針寫入值
- 間接值處理:若值類型為指針,返回實際值地址
/* t *maptype:map 的類型信息 h *hmap:map 的底層結(jié)構(gòu) key unsafe.Pointer:要插入或更新的鍵 返回:指向值存儲位置的指針(寫入值需通過此指針) */ func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer { // 對于nil的map不能進行寫操作,直接panic if h == nil { panic(plainError("assignment to entry in nil map")) } if raceenabled { callerpc := getcallerpc() pc := funcPC(mapassign) racewritepc(unsafe.Pointer(h), callerpc, pc) raceReadObjectPC(t.key, key, callerpc, pc) } if msanenabled { msanread(key, t.key.size) } // 如果有別的goroutine正在寫此map,即發(fā)生了并發(fā)寫,直接異常退出 if h.flags&hashWriting != 0 { throw("concurrent map writes") } // 計算需要寫入的key的hash值 hash := t.hasher(key, uintptr(h.hash0)) // 調(diào)用hasher函數(shù)時,可能發(fā)生paninc,因此沒法完成一次寫操作 // 如果hasher沒有發(fā)生panic,那么將flags設(shè)置成flags += 4 h.flags ^= hashWriting // 如果bucket沒有被分配內(nèi)存,則分配一個bucket(延遲初始化) if h.buckets == nil { h.buckets = newobject(t.bucket) // newarray(t.bucket, 1) } again: // 計算低 8 位 hash,根據(jù)計算出的 bucketMask 選擇對應(yīng)的 bucket 編號 bucket := hash & bucketMask(h.B) // 如果map正在擴容,則完成搬遷工作 if h.growing() { growWork(t, h, bucket) } // 計算key對應(yīng)桶編號的地址,以及hash值的高8位 b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) top := tophash(hash) var inserti *uint8 // 需要寫入tophash數(shù)組的下標(biāo) var insertk unsafe.Pointer // 寫入key的對象指針(地址) var elem unsafe.Pointer // 寫入value的對象指針(地址),即返回值 bucketloop: // 開啟雙層循環(huán),外層遍歷bucket的所有overflow桶,內(nèi)層遍歷每個bucket的cell // 目的:找到空的cell(key不存在),或者top所在的位置(key已存在) for { for i := uintptr(0); i < bucketCnt; i++ { if b.tophash[i] != top { // 當(dāng)前top不一致,繼續(xù)比對下一個 // 找到第一個空的cell,并保存下表以及地址信息 if isEmpty(b.tophash[i]) && inserti == nil { inserti = &b.tophash[i] insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) } // 此cell為空且后面也都是空cell,那么inserti必定已不為空。 // 這種情況直接退出bucket cell的遍歷 if b.tophash[i] == emptyRest { break bucketloop } continue } // 如果b.tophash[i] == top,計算key對應(yīng)的地址 // k是指針對象,解引用 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } // 如果相同的 hash 位置的 key 和要插入的 key 字面上不相等 // 如果兩個 key 的首八位后最后八位哈希值一樣,就會進行其值比較,算是一種哈希碰撞吧 if !t.key.equal(key, k) { continue } // map已經(jīng)有此key存在了,那么直接更新 if t.needkeyupdate() { typedmemmove(t.key, k, key) } elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) goto done } // bucket 的 8 個槽沒有滿足條件的能插入或者能更新的,去 overflow 里繼續(xù)找 // overflow 為 nil,說明到了 overflow 鏈表的末端了,退出外層循環(huán) ovf := b.overflow(t) if ovf == nil { break } // 賦值為鏈表的下一個元素,繼續(xù)循環(huán) b = ovf } // 沒有找到 key,分配新的空間 // 如果觸發(fā)了最大的 load factor,或者已經(jīng)有太多 overflow buckets // 并且這個時刻沒有在進行 growing 的途中,那么就開始 growing if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again // Growing the table invalidates everything, so try again } if inserti == nil { // The current bucket and all the overflow buckets connected to it are full, allocate a new one. // 前面在桶里找的時候,沒有找到能塞這個 tophash 的位置 // 說明當(dāng)前所有 buckets 都是滿的,分配一個新的 bucket newb := h.newoverflow(t, b) inserti = &newb.tophash[0] insertk = add(unsafe.Pointer(newb), dataOffset) elem = add(insertk, bucketCnt*uintptr(t.keysize)) } // store new key/elem at insert position if t.indirectkey() { // 如果鍵的比較大,則直接使用指針存儲 kmem := newobject(t.key) // 二級指針,insertk看作是指向指針的指針 *(*unsafe.Pointer)(insertk) = kmem insertk = kmem } if t.indirectelem() { vmem := newobject(t.elem) *(*unsafe.Pointer)(elem) = vmem } typedmemmove(t.key, insertk, key) *inserti = top h.count++ done: // 禁止并發(fā)寫 if h.flags&hashWriting == 0 { throw("concurrent map writes") } // flags對hashWriting按位置0,'^='表示按右邊hashWriting二進制為1的位置,置0 // 還原寫操作之前的flags h.flags &^= hashWriting if t.indirectelem() { // 如果value是個大對象,則bucket中存儲的是對象地址unsafe.Pointer,取出存放value對象的地址 elem = *((*unsafe.Pointer)(elem)) } return elem }
3.3 map的查找
mapaccess1、mapaccess2、mapaccessk是常用的map查找函數(shù),三個函數(shù)的主要實現(xiàn)基本類似,主要區(qū)別在于函數(shù)的返回值不同。
- mapaccess1只有一個value的返回值,v := m[k]時調(diào)用,如果k不存在,返回的是value類型對應(yīng)的零值
- mapaccess2返回value,bool,v, ok := m[k]時調(diào)用,如果k不存在,返回是value類型對應(yīng)的零值,false
- mapaccessk返回key,value,如果k不存在,返回nil,nil
下面主要分析下mapaccess2函數(shù)的實現(xiàn):
安全性檢查
- 空 map 處理:如果 map 為 nil 或元素數(shù)為 0,直接返回零值和 false
- 特殊處理:如果鍵類型可能引發(fā) panic(如函數(shù)類型),調(diào)用哈希函數(shù)觸發(fā) panic
- 讀寫沖突檢測:當(dāng)其他 goroutine 正在寫 map 時拋出異常(Go map 非并發(fā)安全)
計算哈希和定位桶
bucketMask(h.B)
:生成用于取模的掩碼(如 B=3 時,mask=0b111)- 桶定位公式:桶地址 = buckets起始地址 + (hash & mask) * 桶大小
擴容期間的特殊處理:當(dāng) map 正在擴容時,數(shù)據(jù)可能存在于新舊桶中(擴容有等量擴容與雙倍擴容兩種,詳細解釋見3.4節(jié)),如果是雙倍擴容,且該下標(biāo)還沒有遷移完成,則在老桶中查找
雙層循環(huán)搜索鍵值對
- tophash 比較:先比較哈希高8位,快速過濾不匹配項
- emptyRest 優(yōu)化:遇到標(biāo)記為
emptyRest
的槽位,表示后續(xù)全部為空,直接跳出循環(huán)
鍵值定位:
- 鍵位置:桶地址 + 數(shù)據(jù)偏移 + 索引 * 鍵大小
- 值位置:桶地址 + 數(shù)據(jù)偏移 + 8*鍵大小 + 索引 * 值大小
- 間接存儲處理:若鍵或值為指針類型,需解引用獲取實際數(shù)據(jù)
- 未找到處理:返回預(yù)定義的零值地址和 false
/* t *maptype:map 的類型信息 h *hmap:map 的底層結(jié)構(gòu) key unsafe.Pointer:要查找的鍵 返回值: unsafe.Pointer:指向值的指針(未找到時指向零值) bool:表示鍵是否存在 */ func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) { if raceenabled && h != nil { callerpc := getcallerpc() pc := funcPC(mapaccess2) racereadpc(unsafe.Pointer(h), callerpc, pc) raceReadObjectPC(t.key, key, callerpc, pc) } if msanenabled && h != nil { msanread(key, t.key.size) } // 如果map為空,或者元素個數(shù)為零,直接返回零值 if h == nil || h.count == 0 { if t.hashMightPanic() { t.hasher(key, 0) } return unsafe.Pointer(&zeroVal[0]), false } // 讀、寫沖突 if h.flags&hashWriting != 0 { throw("concurrent map read and map write") } // 計算哈希值,并且加入 hash0 引入隨機性 hash := t.hasher(key, uintptr(h.hash0)) // 如果 B = 3,那么結(jié)果用二進制表示就是 111,2^B-1 m := bucketMask(h.B) // b 就是存儲key所在的 bucket 的地址 b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize))) // h.oldbuckets != nil時,說明 map 發(fā)生了擴容。這時候,新的 buckets 里可能還沒有老的內(nèi)容, // 所以一定要在老的里面找,否則有可能發(fā)生“消失”的詭異現(xiàn)象 if c := h.oldbuckets; c != nil { if !h.sameSizeGrow() { // 如果不是等量擴容,新bucket的數(shù)量是老bucket的兩倍 m >>= 1 } // 求出 key 在老的 map 中的 bucket 位置 oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize))) // 如果oldb 沒有搬遷到新的 bucket,那就在老的 bucket 中尋找 if !evacuated(oldb) { b = oldb } } // 計算高 8 位的 hash,相當(dāng)于右移 56 位,只取高8位 top := tophash(hash) bucketloop: // 兩層循環(huán),第一層遍歷bucket后面所有的溢出桶 // 第二層遍歷每個桶內(nèi)部的8個key位置 for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { // 如果top不匹配 if b.tophash[i] != top { // emptyRest標(biāo)記此cell后面所有的key(包括overflow桶)都為空,此時直接跳出循環(huán) if b.tophash[i] == emptyRest { break bucketloop } continue } // 通過 bmap的地址+dataOffset+i*keysize 定位key的位置 dataOffset = unsafe.Offsetof(struct{ b bmap // bmap理解為[bucketCnt]uint8 v int64 }{}.v) k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { // 如果key是指針,那么解引用 k = *((*unsafe.Pointer)(k)) // 先將k轉(zhuǎn)化為*unsafe.Pointer類型,然后取出該地址存儲的值 } // 如果key相等,定位value的位置,在map中找到了key-value,然后返回 if t.key.equal(key, k) { e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { // 如果value是指針,那么解引用 e = *((*unsafe.Pointer)(e)) } return e, true } } } // 如果遍歷完所有的bucket(包括溢出桶),還沒找到,則返回零值 return unsafe.Pointer(&zeroVal[0]), false }
3.4 map的擴容
擴容是hash table中比較常見的一種操作,主要用于提高查詢效率。Go map的擴容觸發(fā)條件如下:
是不是已經(jīng)到了 load factor 的臨界點,即元素個數(shù) >= 桶個數(shù)*6.5,這時候說明大部分的桶可能都快滿了,如果插入新元素,有大概率需要掛在 overflow 的桶上。
overflow 的桶是不是太多了,
當(dāng) bucket 總數(shù) < 2 ^ 15 時,overflow 的 bucket 總數(shù) >= bucket 的總數(shù)
當(dāng) bucket 總數(shù) >= 2 ^ 15 時,overflow 的 bucket >= 2 ^ 15
滿足上述兩種情況時,就被認(rèn)為溢出桶太多了。為啥會導(dǎo)致這種情況呢?是因為我們對 map 一邊插入,一邊刪除,會導(dǎo)致其中很多桶出現(xiàn)空洞,這樣使得 bucket 使用率不高,值存儲得比較稀疏。在查找時效率會下降。
// 裝載因子超過 6.5 func overLoadFactor(count int64, B uint8) bool { return count >= bucketCnt && float32(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) } // overflow buckets 太多 func tooManyOverflowBuckets(noverflow uint16, B uint8) bool { if B > 15 { B = 15 } // The compiler doesn't see here that B < 16; mask B to generate shorter shift code. return noverflow >= uint16(1)<<(B&15) }
針對上述兩種情況,采用了不同的解決方法:
- 針對 1,將 B + 1,進而 hmap 的 bucket 數(shù)組擴容一倍;
- 針對 2,通過移動 bucket 內(nèi)容,使其傾向于緊密排列從而提高 bucket 利用率(等量擴容)。
3.4.1 hashGrow函數(shù)
hashGrow函數(shù)只有在往map中新插入一個值,且需要觸發(fā)擴容時才會被調(diào)用。該函數(shù)主要根據(jù)擴容條件判斷需要執(zhí)行哪一種擴容,然后申請新的bucket內(nèi)存,更新bucket、oldbucket的信息,具體的遷移工作是由growWork 和 evacuate函數(shù)中完成的。Go map的擴容也采用的漸進式遷移,每一次賦值、刪除操作時,如果map處于擴容狀態(tài),則會保證key對應(yīng)的索引完全遷移(這樣,后續(xù)的操作只需要在h.bucket中完成即可),同時將h.nevacuate指示的下標(biāo)索引對應(yīng)的所有bucket也完成遷移。
func hashGrow(t *maptype, h *hmap) { // If we've hit the load factor, get bigger. // Otherwise, there are too many overflow buckets, so keep the same number of buckets and "grow" laterally. // 如果 load factor 超過了閾值,那么需要對 map 進行擴容,即 B = B + 1,bucket 總數(shù)會變?yōu)樵瓉淼亩? // 如果還沒到閾值,那么只需要保持相同數(shù)量的 bucket,橫向拍平就行了(等量擴容) bigger := uint8(1) if !overLoadFactor(h.count+1, h.B) { bigger = 0 h.flags |= sameSizeGrow // 如果flags原先的值小于sameSizeGrow,h.flags += sameSizeGrow } // 將原先的bucket分給oldbuckets,然后申請新的bucket內(nèi)存 oldbuckets := h.buckets newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) // 先把 h.flags 中 iterator 和 oldIterator 對應(yīng)位清 0,然后如果發(fā)現(xiàn) iterator 位為 1,那就把它轉(zhuǎn)接到 oldIterator 位,使得 oldIterator 標(biāo)志位變成 1。 // 潛臺詞就是:buckets 現(xiàn)在掛到了 oldBuckets 名下了,對應(yīng)的標(biāo)志位也轉(zhuǎn)接過去吧。 flags := h.flags &^ (iterator | oldIterator) if h.flags&iterator != 0 { flags |= oldIterator } // 更新map的信息 h.B += bigger h.flags = flags h.oldbuckets = oldbuckets h.buckets = newbuckets h.nevacuate = 0 h.noverflow = 0 // 將原先的overflow搬到oldoverflow if h.extra != nil && h.extra.overflow != nil { // Promote current overflow buckets to the old generation. if h.extra.oldoverflow != nil { throw("oldoverflow is not nil") } h.extra.oldoverflow = h.extra.overflow h.extra.overflow = nil } // 如果新的bucket有overflow bucket,賦值給nextOverflow if nextOverflow != nil { if h.extra == nil { h.extra = new(mapextra) } h.extra.nextOverflow = nextOverflow } // the actual copying of the hash table data is done incrementally by growWork() and evacuate(). // 實際的哈希表元素的拷貝工作是在 growWork 和 evacuate 中增量慢慢地進行的 }
3.4.3 evacuate函數(shù)
evacuate函數(shù)實現(xiàn)遷移的核心點在于:
evacDst
結(jié)構(gòu):跟蹤遷移目標(biāo)位置
等量擴容:只使用 x
(相同索引位置,平行遷移)
翻倍擴容:使用 x
和 y
兩個目標(biāo),將原來一個索引下的bucket內(nèi)容分配到新bmap數(shù)組的兩個相關(guān)索引下:
x
:新桶數(shù)組低位(索引 =oldbucket
)y
:新桶數(shù)組高位(索引 =oldbucket + newbit
)
在翻倍擴容的時候,雖然鍵的哈希值沒有變化,但通過精妙的遷移策略和新索引計算機制,仍然能確保鍵的正確查找!翻倍擴容時,新掩碼(newbit) = 1 << B(B 是舊桶數(shù)量的指數(shù)),遷移到新桶數(shù)組到高位或地位,決定于hash & newbit。然后在查找時,使用新掩碼計算索引,在不改變hash函數(shù)的情況完美解決查找問題。(新舊mask的區(qū)別就是:新mask比舊值多了 B+1 bit位的判斷,后 B bit位還是保持一致,所以可以利用hash的第 B+1位值來確定key遷移到低位還是高位)
新索引 = { 舊索引 (當(dāng) hash & newbit == 0 時) 舊索引 + newbit (當(dāng) hash & newbit != 0 時) } ======> 新索引 = hash & (newMask),新mask的第 B+1 bit位的值 == 2^B
newMask = (1 << (B+1)) - 1 = (1 << B) * 2 - 1 = newbit*2 - 1
假設(shè):
- 舊 B=2 (4個桶,掩碼 0b11)
- 新 B=3 (8個桶,掩碼 0b111)
- newbit = 1<<2 = 4 (0b100)
- 鍵哈希值:h = 13 (二進制 0b1101)
階段 | 計算過程 | 結(jié)果 |
---|---|---|
舊索引 | h & 0b11 = 0b1101 & 0b0011 | 1 (0b01) |
遷移決策 | h & newbit = 0b1101 & 0b0100 | 4 (非0) → 遷移到高位 |
新索引 | h & 0b111 = 0b1101 & 0b0111 | 5 (0b101) |
驗證 | 舊索引(1) + newbit(4) | 5 |
// evacDst is an evacuation destination. type evacDst struct { b *bmap // current destination bucket i int // key/elem index into b k unsafe.Pointer // pointer to current key storage e unsafe.Pointer // pointer to current elem storage } // 該函數(shù)用于實現(xiàn)hmap擴容時,數(shù)據(jù)的搬遷工作 // 如果是等量擴容,那么就初始化一個evacDst // 如果是翻倍擴容,那么就初始化兩個evacDst func evacuate(t *maptype, h *hmap, oldbucket uintptr) { // 定位舊bucket的地址以及擴容前map的容量 b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) newbit := h.noldbuckets() // 如果 b 沒有被搬遷過 if !evacuated(b) { // xy contains the x and y (low and high) evacuation destinations. // xy 包含的是移動的目標(biāo) // x 表示新 bucket 數(shù)組的前(low)半部分,y 表示新 bucket 數(shù)組的后(high)半部分 var xy [2]evacDst x := &xy[0] x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize))) x.k = add(unsafe.Pointer(x.b), dataOffset) x.e = add(x.k, bucketCnt*uintptr(t.keysize)) if !h.sameSizeGrow() { // Only calculate y pointers if we're growing bigger. // Otherwise GC can see bad pointers. // 如果不是等 size 擴容,前后 bucket 序號有變,使用 y 來進行搬遷 // 擴容后的map bucket數(shù)量是原先的兩倍,x,y分別各占一半,數(shù)量與擴容前一樣 // y部分桶的編號: oldbucket+newbit y := &xy[1] y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize))) y.k = add(unsafe.Pointer(y.b), dataOffset) y.e = add(y.k, bucketCnt*uintptr(t.keysize)) } // 遍歷所有的 bucket,包括 overflow buckets,b 是老的 bucket 地址 for ; b != nil; b = b.overflow(t) { // 從oldbucket的第一個cell開始 k := add(unsafe.Pointer(b), dataOffset) e := add(k, bucketCnt*uintptr(t.keysize)) // 遍歷 bucket 中的所有 cell for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) { // 當(dāng)前 cell 的 top hash 值 top := b.tophash[i] // 如果 cell 為空,即沒有 key if isEmpty(top) { // 那就標(biāo)志它被"搬遷"過,繼續(xù)下一個cell b.tophash[i] = evacuatedEmpty continue } // 正常不會出現(xiàn)這種情況 // 未被搬遷的 cell 只可能是 empty 或是正常的 top hash(大于 minTopHash) if top < minTopHash { throw("bad map state") } k2 := k if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } var useY uint8 if !h.sameSizeGrow() { // Compute hash to make our evacuation decision (whether we need // to send this key/elem to bucket x or bucket y). // 計算哈希,以判斷我們的數(shù)據(jù)要轉(zhuǎn)移到哪一部分的 bucket, // 可能是 x 部分,也可能是 y 部分 hash := t.hasher(k2, uintptr(h.hash0)) if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) { // If key != key (NaNs), then the hash could be (and probably // will be) entirely different from the old hash. Moreover, // it isn't reproducible. Reproducibility is required in the // presence of iterators, as our evacuation decision must // match whatever decision the iterator made. // Fortunately, we have the freedom to send these keys either // way. Also, tophash is meaningless for these kinds of keys. // We let the low bit of tophash drive the evacuation decision. // We recompute a new random tophash for the next level so // these keys will get evenly distributed across all buckets // after multiple grows. useY = top & 1 top = tophash(hash) } else { // 根據(jù)hash & newbit 來確定新bucket的索引,確保遷移完成之后, // 使用原先的hash值 & 新的mask 還能找到正確的索引 if hash&newbit != 0 { useY = 1 } } } if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY { throw("bad evacuatedN") } // 在oldbucket對應(yīng)的cell中標(biāo)記top的搬遷狀態(tài) b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY dst := &xy[useY] // evacuation destination // 當(dāng)前bucket中已經(jīng)放滿了元素,需要使用overflow bucket if dst.i == bucketCnt { dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) dst.e = add(dst.k, bucketCnt*uintptr(t.keysize)) } dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check if t.indirectkey() { *(*unsafe.Pointer)(dst.k) = k2 // copy pointer } else { typedmemmove(t.key, dst.k, k) // copy elem } if t.indirectelem() { *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e) } else { typedmemmove(t.elem, dst.e, e) } dst.i++ // These updates might push these pointers past the end of the // key or elem arrays. That's ok, as we have the overflow pointer // at the end of the bucket to protect against pointing past the // end of the bucket. dst.k = add(dst.k, uintptr(t.keysize)) dst.e = add(dst.e, uintptr(t.elemsize)) } } // Unlink the overflow buckets & clear key/elem to help GC. // 如果沒有協(xié)程在使用老的 buckets,就把老 buckets 清除掉,幫助gc if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 { b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)) // Preserve b.tophash because the evacuation state is maintained there. // 只清除bucket 的 key,value 部分,保留 top hash 部分,指示搬遷狀態(tài) ptr := add(b, dataOffset) n := uintptr(t.bucketsize) - dataOffset memclrHasPointers(ptr, n) } } // 更新搬遷進度,如果此次搬遷的 bucket 等于當(dāng)前進度 if oldbucket == h.nevacuate { advanceEvacuationMark(h, t, newbit) } }
3.5 map的刪除
map的刪除主要流程就是需要在key所在的索引bmap鏈表中查找到對應(yīng)的值,進行內(nèi)容的刪除釋放。這里需要特別注意的是,為了提升查找效率,有一個emptyRest前向傳播機制:如果被刪除的key后續(xù)位置都是emptyRest,則需要將其前面標(biāo)記為emptyOne的cell升級為emptyRest,表示從這個cell往后不再有數(shù)據(jù)。
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) { if raceenabled && h != nil { callerpc := getcallerpc() pc := funcPC(mapdelete) racewritepc(unsafe.Pointer(h), callerpc, pc) raceReadObjectPC(t.key, key, callerpc, pc) } if msanenabled && h != nil{ msanread(key, t.key.size) } // 如果map為空,或者元素個數(shù)為零,直接返回 if h == nil || h.count == 0 { if t.hashMightPanic() { t.hasher(key, 0) } return } // 有g(shù)oroutine在寫map時,無法完成刪除操作 if h.flags&hashWriting != 0 { throw("concurrent map writes") } // 計算需要寫入的key的hash值 hash := t.hasher(key, uintptr(h.hash0)) // 調(diào)用hasher函數(shù)時,可能發(fā)生paninc,因此沒法完成一次寫操作 // 如果hasher沒有發(fā)生panic,那么將flags設(shè)置成flags += 4 h.flags ^= hashWriting // 計算低 8 位 hash,根據(jù)計算出的 bucketMask 選擇對應(yīng)的 bucket 編號 bucket := hash & bucketMask(h.B) // 如果map正在擴容,則完成搬遷工作 if h.growing() { growWork(t, h, bucket) } // 計算key對應(yīng)桶編號的地址,以及hash值的高8位 b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) bOrig := b top := tophash(hash) search: // 兩層循環(huán),第一層遍歷bucket后面所有的溢出桶 // 第二層遍歷每個桶內(nèi)部的8個key位置 for ; b != nil; b = b.overflow(t) { for i := uintptr(0); i < bucketCnt; i++ { // 如果top不匹配 if b.tophash[i] != top { // emptyRest標(biāo)記此cell后面所有的key(包括overflow桶)都為空,此時直接跳出循環(huán) if b.tophash[i] == emptyRest { break search } continue } // 如果b.tophash[i] == top,計算key對應(yīng)的地址 // k是指針對象,解引用 k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) // 為了保存key的原始類型,便于后續(xù)的清理 k2 := k if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } // 如果相同的 hash 位置的 key 和要插入的 key 字面上不相等 // 如果兩個 key 的首八位后最后八位哈希值一樣,就會進行其值比較,算是一種哈希碰撞 if !t.key.equal(key, k2) { continue } // Only clear key if there are pointers in it. if t.indirectkey() { *(*unsafe.Pointer)(k) = nil } else if t.key.ptrdata != 0 { memclrHasPointers(k, t.key.size) } e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize)) if t.indirectelem() { *(*unsafe.Pointer)(e) = nil } else if t.elem.ptrdata != 0 { memclrHasPointers(e, t.elem.size) } else { memclrNoHeapPointers(e, t.elem.size) } // 標(biāo)記tophash的狀態(tài) b.tophash[i] = emptyOne // If the bucket now ends in a bunch of emptyOne states, change those to emptyRest states. // It would be nice to make this a separate function, but for loops are not currently inlineable. if i == bucketCnt-1 { // 刪除的key位于bucket的尾巴 // 如果后續(xù)還有overflow桶,且桶內(nèi)部還有元素,那么直接跳到notLast // 將此tophash標(biāo)記為emptyOne即可 if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest { goto notLast } } else { // 如果key不是最后一個,且后續(xù)cell還有元素,也直接跳到notLast if b.tophash[i+1] != emptyRest { goto notLast } } for { // 刪除的key后面不再有元素,需要將tophash標(biāo)記為emptyRest // 同時往前尋找,并將前面tophash為emptyOne的位置標(biāo)記為emptyRest b.tophash[i] = emptyRest if i == 0 { if b == bOrig { break // beginning of initial bucket, we're done. } // Find previous bucket, continue at its last entry. c := b // 從key的bucket開始,查找當(dāng)前bucket的前一個桶地址 for b = bOrig; b.overflow(t) != c; b = b.overflow(t) { } // bucket內(nèi)部從最后一個cell開始查找tophash為emptyOne的cell i = bucketCnt - 1 } else { i-- } // 查找到一個有內(nèi)容的tophash,結(jié)束循環(huán) if b.tophash[i] != emptyOne { break } } notLast: h.count-- // Reset the hash seed to make it more difficult for attackers to // repeatedly trigger hash collisions. See issue 25237. if h.count == 0 { h.hash0 = fastrand() } break search } } // 禁止并發(fā)寫 if h.flags&hashWriting == 0 { throw("concurrent map writes") } // flags對hashWriting按位置0, // '^='表示按右邊hashWriting二進制為1的位置,置0,其他位置與flags保持一致 // 還原寫操作之前的flags h.flags &^= hashWriting }
3.6 map的遍歷
3.6.1 hiter結(jié)構(gòu)體
在對map進行遍歷時,會借助迭代器hiter輔助完成整個map的循環(huán)遍歷,其中startBucket標(biāo)記此次遍歷的起始位置,wrapped標(biāo)記遍歷是否從頭開始,checkBucket則是用于擴容中進行遍歷時,堅持oldBucket中的數(shù)據(jù)。
type hiter struct { // key 指針,保存此次遍歷得到的key key unsafe.Pointer // value 指針,保存此次遍歷得到的value value unsafe.Pointer // map 類型,包含如 key size 大小等 t *maptype // map header h *hmap // 初始化時指向的 bucket buckets unsafe.Pointer // 當(dāng)前遍歷到的 bmap bptr *bmap overflow [2]*[]*bmap // 起始遍歷的 bucet 編號 startBucket uintptr // 遍歷開始時 cell 的編號(每個 bucket 中有 8 個 cell) offset uint8 // 是否從頭遍歷了 wrapped bool // B 的大小 B uint8 // 指示當(dāng)前 cell 序號 i uint8 // 指向當(dāng)前的 bucket bucket uintptr // 因為擴容,需要檢查的 bucket checkBucket uintptr }
3.6.2 mapiternext函數(shù)
對map進行遍歷時,首先會調(diào)用mapiterinit函數(shù),初始化hiter,該函數(shù)邏輯比較簡單,主要就是隨機確定遍歷起始位置,這里的起始位置包括:bmap的數(shù)組的起始下標(biāo)、bmap bucket內(nèi)部cell的起始點。隨后調(diào)用mapiternext函數(shù)開始執(zhí)行具體的遍歷操作(每調(diào)用一次mapiternext函數(shù)獲取一個map中的鍵值對),該過程的主要流程如下:
1. 首先檢查是否有并發(fā)寫操作,如果有則拋出異常。
2. 獲取迭代器當(dāng)前的狀態(tài)(當(dāng)前遍歷的bucket,當(dāng)前bucket內(nèi)的位置i,當(dāng)前bucket指針b等)。
3. 如果當(dāng)前bucket(b)為nil,說明需要處理下一個bucket或者已經(jīng)遍歷完一圈。
- 如果當(dāng)前bucket序號(bucket)等于起始bucket(it.startBucket)且已經(jīng)標(biāo)記為繞回(wrapped),說明已經(jīng)遍歷完所有bucket,設(shè)置key和elem為nil并返回。
- 如果map正在擴容且迭代器開始時的B(it.B)等于當(dāng)前map的B(h.B),說明迭代開始后擴容未完成,需要處理舊桶:
- 計算對應(yīng)的舊桶(oldbucket)地址。
- 如果該舊桶尚未遷移(evacuated),則設(shè)置checkBucket為當(dāng)前bucket(用于后續(xù)判斷鍵是否屬于當(dāng)前新桶),并繼續(xù)遍歷舊桶。
- 如果已經(jīng)遷移,則直接遍歷新桶中對應(yīng)位置的桶,并將checkBucket設(shè)置為noCheck。
- 否則,直接遍歷新桶中當(dāng)前bucket位置的桶。
- 然后bucket序號加1,如果達到bucket總數(shù)(2^B),則重置為0并標(biāo)記wrapped為true(表示已經(jīng)繞回一圈)。
- 重置i為0,開始遍歷新桶。
4. 遍歷當(dāng)前bucket(b)的8個cell(槽位),注意這里不是從0開始,而是根據(jù)it.offset進行偏移(使用offi = (i+it.offset) & (bucketCnt-1))以實現(xiàn)隨機開始。
- 如果tophash[offi]為空(emptyOne或evacuatedEmpty)則跳過。
- 獲取鍵k和值e的地址。
- 如果checkBucket不為noCheck(說明在擴容過程中且當(dāng)前遍歷的是舊桶),則需要判斷該鍵是否屬于當(dāng)前迭代的新桶(checkBucket):
- 對于正常鍵(非NaN),計算其哈希值并判斷它是否屬于checkBucket,如果不屬于則跳過。
- 對于NaN(k!=k),使用tophash的低位來決定它應(yīng)該去哪個桶,如果與checkBucket的高位不匹配則跳過。
- 如果鍵值有效,則判斷該槽位是否已經(jīng)被遷移(evacuatedX或evacuatedY)且鍵是正常的(可比較且相等):
- 如果未被遷移,或者鍵是NaN(不可比較),則直接使用當(dāng)前找到的鍵值對(因為此時數(shù)據(jù)還未遷移或無法比較,所以認(rèn)為有效)。
- 否則,說明在迭代過程中map已經(jīng)擴容完成,該鍵可能已經(jīng)被遷移,需要從新map中查找(調(diào)用mapaccessK):如果返回的鍵為nil,說明該鍵已被刪除,跳過;否則使用返回的鍵值對。
5. 設(shè)置迭代器的狀態(tài)(key, elem, bucket, bptr, i, checkBucket)并返回。
6. 如果當(dāng)前bucket的8個cell都遍歷完了,則跳到overflow bucket(如果有),重置i為0,然后跳轉(zhuǎn)到next標(biāo)簽繼續(xù)處理。
func mapiternext(it *hiter) { h := it.h if raceenabled { callerpc := getcallerpc() racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapiternext)) } // 如果有g(shù)oroutine正在寫,拋出異常 if h.flags&hashWriting != 0 { throw("concurrent map iteration and writes") } t := it.t bucket := it.bucket b := it.bptr i := it.i checkBucket := it.checkBucket next: // 后續(xù)沒有overflow bucket需要遍歷 if b == nil { // 當(dāng)前遍歷的bucket=startBucket,即完成循環(huán)回到最初的位置 // 且該bucket已經(jīng)從頭到尾遍歷完了,map的遍歷結(jié)束 if bucket == it.startBucket && it.wrapped { // end of iteration it.key = nil it.elem = nil return } // 如果map正處于擴容狀態(tài),還需要遍歷oldbucket if h.growing() && it.B == h.B { // Iterator was started in the middle of a grow, and the grow isn't done yet. // If the bucket we're looking at hasn't been filled in yet (i.e. the old // bucket hasn't been evacuated) then we need to iterate through the old // bucket and only return the ones that will be migrated to this bucket. oldbucket := bucket & it.h.oldbucketmask() // 根據(jù)bucket num在oldbucket的編號位置,計算bucket的地址 b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))) if !evacuated(b) { // 如果oldbucket中此編號的bucket沒有完成搬遷,那么標(biāo)記check checkBucket = bucket } else { // 如果oldbucket中此編號的bucket完成了搬遷,直接遍歷newbucket中對應(yīng)位置的bucket b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) checkBucket = noCheck } } else { b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) checkBucket = noCheck } // 指向下一個bucket bucket++ // 判斷是否已經(jīng)遍歷到了末尾,如果是,則需要從頭重新開始遍歷, // 直至bucket == startbucket,標(biāo)記一次完整的遍歷 if bucket == bucketShift(it.B) { bucket = 0 it.wrapped = true } i = 0 } // 遍歷bucket的8個cell,但不是從頭開始遍歷的 for ; i < bucketCnt; i++ { offi := (i + it.offset) & (bucketCnt - 1) // 如果tophash為空,即沒有數(shù)據(jù),直接檢查下一個 if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty { // TODO: emptyRest is hard to use here, as we start iterating // in the middle of a bucket. It's feasible, just tricky. continue } k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize)) if checkBucket != noCheck && !h.sameSizeGrow() { // Special case: iterator was started during a grow to a larger size // and the grow is not done yet. We're working on a bucket whose // oldbucket has not been evacuated yet. Or at least, it wasn't // evacuated when we started the bucket. So we're iterating // through the oldbucket, skipping any keys that will go // to the other new bucket (each oldbucket expands to two buckets during a grow). if t.reflexivekey() || t.key.equal(k, k) { // If the item in the oldbucket is not destined for the current new bucket in the iteration, skip it. hash := t.hasher(k, uintptr(h.hash0)) if hash&bucketMask(it.B) != checkBucket { continue } } else { // Hash isn't repeatable if k != k (NaNs). We need a // repeatable and randomish choice of which direction // to send NaNs during evacuation. We'll use the low // bit of tophash to decide which way NaNs go. // NOTE: this case is why we need two evacuate tophash // values, evacuatedX and evacuatedY, that differ in their low bit. if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) { continue } } } if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) || !(t.reflexivekey() || t.key.equal(k, k)) { // This is the golden data, we can return it. // OR // key!=key, so the entry can't be deleted or updated, so we can just return it. // That's lucky for us because when key!=key we can't look it up successfully. it.key = k if t.indirectelem() { e = *((*unsafe.Pointer)(e)) } it.elem = e } else { // The hash table has grown since the iterator was started. // The golden data for this key is now somewhere else. // Check the current hash table for the data. // This code handles the case where the key has been deleted, updated, or deleted and reinserted. // NOTE: we need to regrab the key as it has potentially been // updated to an equal() but not identical key (e.g. +0.0 vs -0.0). rk, re := mapaccessK(t, h, k) if rk == nil { continue // key has been deleted } it.key = rk it.elem = re } it.bucket = bucket if it.bptr != b { // avoid unnecessary write barrier; see issue 14921 it.bptr = b } it.i = i + 1 it.checkBucket = checkBucket return } // 通過it.i走到此處,遍歷overflow bucket b = b.overflow(t) i = 0 goto next }
總結(jié)
以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。
相關(guān)文章
golang包循環(huán)引用的幾種解決方案總結(jié)
golang有包循環(huán)引用問題,用過的應(yīng)該都知道,下面這篇文章主要給大家介紹了關(guān)于golang包循環(huán)引用的幾種解決方案,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下2022-09-09Go類型斷言提取測試接口值動態(tài)類型及靜態(tài)轉(zhuǎn)換確保類型接口編譯安全
這篇文章主要為大家介紹了Go類型斷言提取測試接口值動態(tài)類型及靜態(tài)轉(zhuǎn)換確保類型實現(xiàn)特定接口的編譯時安全性詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪2023-10-10