golang map 底層實現
【導讀】只使用 Go map 而不知道底層原理,可能寫出性能和質量有問題的代碼。本文針對 map 的實現進行了詳細介紹。
本文內容基於 go1.13.1 源碼。
在閱讀 Go map 的實現代碼時,最好先了解哈希表這種數據結構實現的算法思想,對理解 Go map 的實現會有幫助,我這裏簡單總結下:
-
map 內部採用的是數組存儲 KV,每個數組元素可以認爲是一個桶
-
key 經過哈希算法後再與 map 的數組長度取模映射到某個桶中
-
如果多個 key 映射到了相同的桶,就意味着出現了哈希衝突,解決衝突的方式有兩種:開放尋址法和鏈表法
-
當 KV 過多時,map 就需要擴容(因爲數組是固定大小的),擴容的策略是新分配一個更大的數組,然後在插入和刪除 key 的時候,將對應的桶的數據搬移到新分配的數組的桶中。這種方式把擴容所需要的 O(n) 時間開銷均攤到了 O(1) 的插入和刪除操作中。
-
map 中用裝載因子(map 中元素的個數 / map 的容量)來表示空閒位置的情況。裝載因子越大,說明空閒位置越少,衝突越多。
調試用的 go 代碼 map.go:
package main
func main() {
myMap := make(map[string]int, 53)
myMap["key"] = 1
print(myMap["key"])
delete(myMap, "key")
}
-
當 make 的 hint <= 8 時,會直接在棧上分配一個 bucket,一個 bucket 可以存儲 8 對 KV(筆者測試了下將 value 的類型由 int 換爲 [8192]string,也是這樣子)
-
當 make 的 hint > 8 && hint <= 52 時,會在堆上分配 bucket,此時不會分配 overflow bucket
-
當 make 的 hint > 52 時,會在堆上分配 bucket 和 overflow bucket
通過對比 hint <= 8 和 hint> 8 生成的"".main
彙編代碼 go tool compile -N -l -S map.go
:
-
hint <= 8 直接在
"".main
的棧上初始化 hmap 結構體和一個 bucket -
hint > 8 會通過調用
runtime.makemap
在棧上初始化 hmap 結構體,並在堆上分配 bucket
通過 dlv debug,可以單步調試代碼,並且可以使用 si 命令,單步執行彙編代碼
hmap 結構體如下:
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
// mapextra holds fields that are not present on all maps.
type mapextra struct {
// If both key and elem do not contain pointers and are inline, then we mark bucket
// type as containing no pointers. This avoids scanning such maps.
// However, bmap.overflow is a pointer. In order to keep overflow buckets
// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
// overflow and oldoverflow are only used if key and elem do not contain pointers.
// overflow contains overflow buckets for hmap.buckets.
// oldoverflow contains overflow buckets for hmap.oldbuckets.
// The indirection allows to store a pointer to the slice in hiter.
overflow *[]*bmap
oldoverflow *[]*bmap
// nextOverflow holds a pointer to a free overflow bucket.
nextOverflow *bmap
}
初始化
func makemap(t *maptype, hint int, h *hmap) *hmap {
// 判斷 hint 是否合法
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
hint = 0
}
// initialize Hmap
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.
// 找到滿足 loadFactor * 2^B >= hint 的 B,其中 loadFactor = loadFactorNum / loadFactorDen = 13 / 2 = 6.5
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.
if h.B != 0 {
var nextOverflow *bmap
// makeBucketArray 中會判斷 h.B 是否 >= 4,如果是,則會分配 nextOverflow,即 overflow bucket
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
overflow bucket 的作用是用於存儲哈希衝突的 KV(go map 採用鏈表法的方式解決哈希衝突))。當 hint = 53 時,分配的 bucket 情況如下:
賦值
func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer {
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
if raceenabled {
callerpc := getcallerpc()
racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapassign_faststr))
}
// 不允許併發寫
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
key := stringStructOf(&s)
// 調用 key 類型對應的 hash 算法
hash := t.key.alg.hash(noescape(unsafe.Pointer(&s)), uintptr(h.hash0))
// Set hashWriting after calling alg.hash for consistency with mapassign.
// 異或操作,設置寫標記位
h.flags ^= hashWriting
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
// 計算 key 存儲在哪個 bucket
bucket := hash & bucketMask(h.B)
if h.growing() {
// 如果 map 正在擴容,需要確保 bucket 已經被搬運到 hmap.buckets 中了
growWork_faststr(t, h, bucket)
}
// 取得對應 bucket 的內存地址
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
// 取 hash 的高 8 位
top := tophash(hash)
// 實際插入的 bucket,雖然上面計算出了 b,但可能 b 已經滿了,需要插入到 b 的 overflow bucket,或者 map 需要擴容了
var insertb *bmap
// 插入到 bucket 中的哪個位置
var inserti uintptr
// bucket 中 key 的地址
var insertk unsafe.Pointer
bucketloop:
for {
// bucketCnt = 8
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
if isEmpty(b.tophash[i]) && insertb == nil { // 在 b 中找到位置 i 可以存放賦值的 KV
insertb = b
inserti = i
// 爲何這裏不執行 break bucketloop?因爲有可能 K 已經存在,需要找到它的位置
}
// 如果餘下的位置都是空的,則不需要再往下找了
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// tophash 相同,還需要仔細比較實際的 K 是否一樣
k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+i*2*sys.PtrSize))
if k.len != key.len {
continue
}
if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) {
continue
}
// K 已經在 map 中了
// already have a mapping for key. Update it.
inserti = i
insertb = b
goto done
}
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
// K 不在 map 中,需要判斷是否進行擴容或者增加 overflow bucket
// Did not find mapping for key. Allocate new cell & add entry.
// If we hit the max load factor or we have too many overflow buckets,
// and we're not already in the middle of growing, start growing.
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
// 如果 map 沒有擴容,並且負載因子超過閾值或者有太多 overflow bucket,則進行擴容
hashGrow(t, h)
// 跳轉回 again
goto again // Growing the table invalidates everything, so try again
}
// 如果還是沒找到空閒的位置存放新的 KV,則需要存儲到 overflow bucket 中
if insertb == nil {
// all current buckets are full, allocate a new one.
insertb = h.newoverflow(t, b)
inserti = 0 // not necessary, but avoids needlessly spilling inserti
}
insertb.tophash[inserti&(bucketCnt-1)] = top // mask inserti to avoid bounds checks
// 插入 K
insertk = add(unsafe.Pointer(insertb), dataOffset+inserti*2*sys.PtrSize)
// store new key at insert position
*((*stringStruct)(insertk)) = *key
h.count++
done:
// 獲取 V 的地址
elem := add(unsafe.Pointer(insertb), dataOffset+bucketCnt*2*sys.PtrSize+inserti*uintptr(t.elemsize))
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
// 清除寫標記位
h.flags &^= hashWriting
// 返回 V 的地址,實際賦值是由編譯器生成的彙編代碼進行賦值的
return elem
}
當出現 key 衝突時,key 會存儲到 overflow bucket 中,以上面的圖爲例,假設超過 8 個 key 都 hash 到了索引 0 的位置:
h.mapextra.nextOverflow
指向下一個可用作 overflow bucket 的空閒 bucket。
訪問
func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool) {
if raceenabled && h != nil {
callerpc := getcallerpc()
racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapaccess2_faststr))
}
// 返回零值,已經 false,表示 key 不存在
if h == nil || h.count == 0 {
return unsafe.Pointer(&zeroVal[0]), false
}
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
key := stringStructOf(&ky)
if h.B == 0 {
// 只有 1 個 bucket
// One-bucket table.
b := (*bmap)(h.buckets)
if key.len < 32 {
// key 比較短,直接進行比較
// short key, doing lots of comparisons is ok
for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
k := (*stringStruct)(kptr)
if k.len != key.len || isEmpty(b.tophash[i]) {
// 後面已經沒有 KV 了,不用再找下去了
if b.tophash[i] == emptyRest {
break
}
continue
}
// 找到 key
if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.elemsize)), true
}
}
// 未找到,返回零值
return unsafe.Pointer(&zeroVal[0]), false
}
// key 比較長
// long key, try not to do more comparisons than necessary
keymaybe := uintptr(bucketCnt)
for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
k := (*stringStruct)(kptr)
if k.len != key.len || isEmpty(b.tophash[i]) {
// 後面已經沒有 KV 了,不用再找下去了
if b.tophash[i] == emptyRest {
break
}
continue
}
// 找到了,內存地址一樣
if k.str == key.str {
return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.elemsize)), true
}
// 檢查頭 4 字節
// check first 4 bytes
if *((*[4]byte)(key.str)) != *((*[4]byte)(k.str)) {
continue
}
// 檢查尾 4 字節
// check last 4 bytes
if *((*[4]byte)(add(key.str, uintptr(key.len)-4))) != *((*[4]byte)(add(k.str, uintptr(key.len)-4))) {
continue
}
// 走到這裏,說明有至少 2 個 key 有可能匹配
if keymaybe != bucketCnt {
// Two keys are potential matches. Use hash to distinguish them.
goto dohash
}
keymaybe = i
}
// 有 1 個 key 可能匹配
if keymaybe != bucketCnt {
k := (*stringStruct)(add(unsafe.Pointer(b), dataOffset+keymaybe*2*sys.PtrSize))
if memequal(k.str, key.str, uintptr(key.len)) {
return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+keymaybe*uintptr(t.elemsize)), true
}
}
return unsafe.Pointer(&zeroVal[0]), false
}
dohash:
hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// 判斷是否正在擴容
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// There used to be half as many buckets; mask down one more power of two.
// 如果不是相同大小的擴容,則需要縮小一倍,因爲此時 len(h.buckets) = 2*len(h.oldbuckets)
m >>= 1
}
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
// 判斷對應的 bucket 是否已經從 h.oldbuckets 搬到 h.buckets
if !evacuated(oldb) {
// 還沒有搬
b = oldb
}
}
top := tophash(hash)
// 在 b,以及 b 的 overflow bucket 中查找
for ; b != nil; b = b.overflow(t) {
for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
k := (*stringStruct)(kptr)
if k.len != key.len || b.tophash[i] != top {
continue
}
if k.str == key.str || memequal(k.str, key.str, uintptr(key.len)) {
return add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.elemsize)), true
}
}
}
return unsafe.Pointer(&zeroVal[0]), false
}
刪除
func mapdelete_faststr(t *maptype, h *hmap, ky string) {
if raceenabled && h != nil {
callerpc := getcallerpc()
racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapdelete_faststr))
}
if h == nil || h.count == 0 {
return
}
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
key := stringStructOf(&ky)
hash := t.key.alg.hash(noescape(unsafe.Pointer(&ky)), uintptr(h.hash0))
// Set hashWriting after calling alg.hash for consistency with mapdelete
h.flags ^= hashWriting
bucket := hash & bucketMask(h.B)
// 如果正在擴容,確保 bucket 已經從 h.oldbuckets 搬到 h.buckets
if h.growing() {
growWork_faststr(t, h, bucket)
}
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
bOrig := b
top := tophash(hash)
search:
// 在 b,已經 b 的 overflow bucket 中查找
for ; b != nil; b = b.overflow(t) {
for i, kptr := uintptr(0), b.keys(); i < bucketCnt; i, kptr = i+1, add(kptr, 2*sys.PtrSize) {
k := (*stringStruct)(kptr)
if k.len != key.len || b.tophash[i] != top {
continue
}
if k.str != key.str && !memequal(k.str, key.str, uintptr(key.len)) {
continue
}
// 找到了
// Clear key's pointer.
k.str = nil
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*2*sys.PtrSize+i*uintptr(t.elemsize))
// 與 GC 相關
if t.elem.ptrdata != 0 {
memclrHasPointers(e, t.elem.size)
} else {
memclrNoHeapPointers(e, t.elem.size)
}
// 標記當前單元是空閒的
b.tophash[i] = emptyOne
// If the bucket now ends in a bunch of emptyOne states,
// change those to emptyRest states.
// 判斷>i 的單元是否都是空閒的
if i == bucketCnt-1 {
if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
goto notLast
}
} else {
if b.tophash[i+1] != emptyRest {
goto notLast
}
}
// >i 的單元都是空閒的,那麼將當前單元,以及<i 的 emptyOne 單元都標記爲 emptyRest
// emptyRest 的作用就是在查找的時候,遇到 emptyRest 就不用再往下找了,加速查找的過程
for {
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
for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
}
i = bucketCnt - 1
} else {
i--
}
if b.tophash[i] != emptyOne {
break
}
}
notLast:
h.count--
break search
}
}
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting
}
下圖演示了在一個有一個 overflow bucket 的 bucket 中刪除 KV,bmap.tophash 標記位變化的過程:
擴容
兩種情況下會進行擴容:
-
overLoadFactor(h.count+1, h.B)
裝載因子過大時,擴容一倍 -
tooManyOverflowBuckets(h.noverflow, h.B))
當使用的 overflow bucket 過多時,實際上沒有擴容,重新分配了一樣大的空間,主要是爲了回收空閒的 overflow 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.
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
// 如果裝載因子沒有超過閾值,那麼按相同大小的空間“擴容”
bigger = 0
h.flags |= sameSizeGrow
}
oldbuckets := h.buckets
// 分配新空間
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
// 清除 iterator,oldIterator 的標記位
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// commit the grow (atomic wrt gc)
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
h.nevacuate = 0 // 統計搬了多少個 bucket
h.noverflow = 0
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
}
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().
}
實際的搬遷 bucket:
// 插入和刪除的時候,發現正在擴容的話,會調用該方法
func growWork_faststr(t *maptype, h *hmap, bucket uintptr) {
// make sure we evacuate the oldbucket corresponding
// to the bucket we're about to use
evacuate_faststr(t, h, bucket&h.oldbucketmask())
// evacuate one more oldbucket to make progress on growing
if h.growing() {
evacuate_faststr(t, h, h.nevacuate)
}
}
func evacuate_faststr(t *maptype, h *hmap, oldbucket uintptr) {
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
newbit := h.noldbuckets()
// 判斷該 bucket 是否已經搬遷了
if !evacuated(b) {
// TODO: reuse overflow buckets instead of using new ones, if there
// is no iterator using the old buckets. (If !oldIterator.)
// xy contains the x and y (low and high) evacuation destinations.
// xy 指向新空間的高低區間的起點
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*2*sys.PtrSize)
// 如果是擴容一倍,纔會用到 y
if !h.sameSizeGrow() {
// Only calculate y pointers if we're growing bigger.
// Otherwise GC can see bad pointers.
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*2*sys.PtrSize)
}
// 將當前 bucket 以及其 overflow bucket 進行搬遷
for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
e := add(k, bucketCnt*2*sys.PtrSize)
for i := 0; i < bucketCnt; i, k, e = i+1, add(k, 2*sys.PtrSize), add(e, uintptr(t.elemsize)) {
top := b.tophash[i]
// 這裏是不是可以判斷到 emptyRest 就停止循環了?
if isEmpty(top) {
b.tophash[i] = evacuatedEmpty
continue
}
if top < minTopHash {
throw("bad map state")
}
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).
hash := t.key.alg.hash(k, uintptr(h.hash0))
if hash&newbit != 0 { // 新的位置位於高區間
useY = 1
}
}
b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY, enforced in makemap
dst := &xy[useY] // evacuation destination
if dst.i == bucketCnt { // 是否要放到 overflow bucket 中
dst.b = h.newoverflow(t, dst.b)
dst.i = 0
dst.k = add(unsafe.Pointer(dst.b), dataOffset)
dst.e = add(dst.k, bucketCnt*2*sys.PtrSize)
}
dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
// Copy key.
*(*string)(dst.k) = *(*string)(k)
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, 2*sys.PtrSize)
dst.e = add(dst.e, uintptr(t.elemsize))
}
}
// Unlink the overflow buckets & clear key/elem to help 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.
ptr := add(b, dataOffset)
n := uintptr(t.bucketsize) - dataOffset
memclrHasPointers(ptr, n)
}
}
// 統計搬遷的進度,如果數據都搬遷完了,則結束擴容
if oldbucket == h.nevacuate {
advanceEvacuationMark(h, t, newbit)
}
}
關於 map 元素無法取址問題
如果我們嘗試對 map 的元素取址,會遇到 cannot take the address of m["a"]
錯誤。
因爲 map 在擴容後m["a"]
的地址是會發生改變的。
關於 map 的類型 value 是 struct 或數組類型無法直接修改 value 的某個字段 / 元素的問題
cannot assign to struct field m["a"].i in map
和 cannot assign to m["a"][0]
錯誤是在編譯階段就報錯的。
如果 key "a"
存在的話,從實現上來講,是可以做到對 m["a"].i
或 m["a"][0]
進行賦值的。如果 key "a"
不存在的話,就需要考慮是否拋出 runtime error(返回零值使賦值能成功不太合適,因爲需要把零值的 key "a"
插入到 map 中,但又感覺又不符合代碼的語意)。
關於這個問題在 Go 的代碼倉庫有個 issue:proposal: spec: cannot assign to a field of a map element directly:m[“foo”\].f = x #3117
如果 key 的類型是 struct 或 指針
對於不同類型的 key 會調用相應的runtime.mapassign*
和runtime.mapaccess*
函數,計算 key 的哈希算法也不一樣。
比如type Key struct{a int}
會使用與 key 類型爲 int 相同的runtime.mapassign_fast64
和runtime.mapaccess1_fast64
函數,type Key struct{a string}
會使用與 key 類型爲 string 相同的runtime.mapassign_faststr
和runtime.mapaccess1_faststr
函數。但是type Key struct{a int; b string}
則使用的是runtime.mapassign
和runtime.mapaccess1
。
遺留問題
-
map 併發寫的檢測是通過判斷 h.flags 是否有標記位 hashWriting 這種方式是否不夠嚴謹?
-
相同大小容量的 “擴容”,我判斷出來的是爲了解決過多空閒 overflow bucket 的問題,如果是真的要解決這個問題,是否可以在刪除 key 的時候做回收?
轉自:
yangxikun.github.io/golang/2019/10/07/golang-map.html
本文由 Readfog 進行 AMP 轉碼,版權歸原作者所有。
來源:https://mp.weixin.qq.com/s/2mH4pmD-NZCqUvNm4rxAQQ