💢歡迎來到張胤塵的開源技術站
💥開源如江河，匯聚眾志成。代碼似星辰，照亮行征程。開源精神長，傳承永不忘。攜手共前行，未來更輝煌💥

映射

在 golagn 中，映射是一種鍵值對的集合，其中每個鍵（key）都唯一地映射到一個值（value）。它類似于 c/c++ 中的 std::unordered_map，但是具體實現上還是有很大的區(qū)別，下面會進行詳細的剖析。

映射的定義

映射的類型定義為：

map[KeyType]ValueType

• KeyType：鍵的類型，必須是可比較的（可以進行 == 或 != 比較）。其中常見的可比較類型包括：
  • 基本類型：int, float64, string, bool 等。
  • 復合類型：指針、通道、接口、包含可比較字段的結構體。
• ValueType：值的類型可以是任何類型，包括基本類型、自定義類型、切片、結構體、映射等。

映射初始化

在 golang 中提供了兩種初始化映射的方式：make 函數、使用字面量。

make 函數

make 是 golang 中用于初始化切片、映射和通道的標準函數。對于映射來說，make 的語法如下：

m := make(map[KeyType]ValueType)

例如，創(chuàng)建一個空的映射，其中鍵為 string 類型，值為 int 類型，如下所示：

m := make(map[string]int)

另外在 golang 中可以為映射指定初始容量（如果不指定，默認容量為零）。

例如，創(chuàng)建一個初始容量為 10 的映射，如下所示：

m := make(map[string]int, 10)

這種方式創(chuàng)建映射中的鍵值對數量為 0，后續(xù)可以通過賦值操作添加鍵值對。

使用字面量

映射的字面量語法允許在聲明時直接初始化鍵值對。這種方式適用于在編譯時已知數據的情況。

語法如下所示：

m := map[KeyType]ValueType{Key1: Value1,Key2: Value2,// ...
}

例如：

m := map[string]int{"a": 1,"b": 2,"c": 3,
}

源碼分析

下面主要針對 map 中的數據結構、數據存儲、鍵值訪問、鍵值插入和擴容機制、鍵值刪除五大部分源碼進行剖析。

數據結構

在 map 的內部由兩個核心數據結構組成：hmap 和 bmap 。

hmap

hmap 是 golang 中 map 的底層核心數據結構之一，它封裝了哈希表的所有關鍵信息。源碼如下所示：

源碼位置：src/runtime/map.go

// A header for a Go map.
type hmap struct {// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/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     uint8B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for detailshash0     uint32 // hash seedbuckets    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 growingnevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)extra *mapextra // optional fields
}

• count：表示當前 map 中存儲的鍵值對數量，len() 直接訪問它。
• flags：用于存儲一些標志位，例如是否正在擴容、是否需要清理等。
• B：表示桶的數量為 2^B。例如，如果 B = 3，則桶的數量為 2^3 = 8。B 的值決定了 buckets 數組的大小。
• noverflow：表示溢出桶的數量。當一個桶滿了（最多存儲 8 對鍵值對），會創(chuàng)建一個溢出桶，并通過鏈表連接。
• hash0：哈希種子，用于計算鍵的哈希值。通過哈希種子可以避免哈希沖突，增加哈希值的隨機性。
• buckets：指向底層桶數組的指針，桶數組的大小為 2^B，每個桶是一個 bmap 結構體。
• oldbuckets：在擴容時，舊的桶數組會存儲在這里。新的桶數組大小是舊數組的兩倍。擴容完成后，oldbuckets 會被釋放。
• nevacuate：用于記錄擴容進度的計數器。表示已經遷移完成的桶數量。
• extra：存儲一些可選字段。

bmap

bmap 是存儲鍵值對的“桶”，每個桶可以存儲最多 8 對鍵值對。源碼如下所示：

源碼位置：src/runtime/map.go

// A bucket for a Go map.
type bmap struct {// tophash generally contains the top byte of the hash value// for each key in this bucket. If tophash[0] < minTopHash,// tophash[0] is a bucket evacuation state instead.tophash [abi.MapBucketCount]uint8// Followed by bucketCnt keys and then bucketCnt elems.// NOTE: packing all the keys together and then all the elems together makes the// code a bit more complicated than alternating key/elem/key/elem/... but it allows// us to eliminate padding which would be needed for, e.g., map[int64]int8.// Followed by an overflow pointer.
}

• tophash：abi.MapBucketCount 是一個常量，值為 8。存儲每個鍵的哈希值的最高字節(jié)（top byte）。特殊情況：如果 tophash[0] < minTopHash，則表示該桶處于遷移狀態(tài)，而不是存儲鍵的哈希值。

// Maximum number of key/elem pairs a bucket can hold.
MapBucketCountBits = 3 // log2 of number of elements in a bucket.
MapBucketCount     = 1 << MapBucketCountBits

minTopHash     = 5 // minimum tophash for a normal filled cell.

• 在 tophash 之后，bmap 會依次存儲鍵和值。鍵和值的存儲方式是連續(xù)的：先存儲所有鍵（bucketCnt 個鍵），然后存儲所有值（bucketCnt 個值）。這種設計可以減少內存對齊時的填充，從而節(jié)省內存。例如，在 map[int64]int8 的情況下，如果鍵和值交替存儲，可能會因為對齊問題浪費內存。
• 最后在每個 bmap 的末尾包含一個指向下一個溢出桶的指針（overflow）。當一個桶滿了（最多存儲 8 對鍵值對）時，會通過鏈表的方式創(chuàng)建一個溢出桶，用于存儲額外的鍵值對。

數據存儲

例如：在64位平臺上有一個 map[int]string，鍵的大小為 8 字節(jié)（int64），值的大小為 16 字節(jié)（指向字符串數據的指針（8 字節(jié)）和字符串的長度（8 字節(jié)））。一個 bmap 的內存布局如下所示：

鍵值訪問

由 map 數據存儲模型可知，因為鍵和值的存儲是動態(tài)的，訪問鍵和值時就需要通過指針偏移來實現。源碼內容如下所示：

源碼位置：src/runtime/map.go

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the elem type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {// ...
}

• t *maptype：map 的類型信息，例如鍵的類型、值的類型、哈希函數等。
• h *hmap： map 的底層結構，包含哈希表的元數據（如桶數組、鍵值對數量等）。
• key unsafe.Pointer：查找目標鍵的指針。
• 返回值：返回指向值的指針。如果鍵不存在，則返回值類型的零值的指針。

對于 mapaccess1 源碼的流程進行了如下步驟的拆解：

• 競態(tài)檢測
• Sanitizer 檢測
• 空檢查
• 并發(fā)寫檢查
• 哈希值計算
• 桶定位
• 擴容情況處理
• 桶查找

下面針對每一步驟進行詳細說明。

競態(tài)檢測

如果啟用了競態(tài)檢測，記錄當前操作的上下文，以便在發(fā)生競態(tài)時能夠追蹤。

if raceenabled && h != nil {callerpc := getcallerpc()pc := abi.FuncPCABIInternal(mapaccess1)racereadpc(unsafe.Pointer(h), callerpc, pc)raceReadObjectPC(t.Key, key, callerpc, pc)
}

Sanitizer 檢測

msanread 會標記對 key 的讀取操作，確保該內存區(qū)域已經被正確初始化。防止程序讀取未初始化的內存，從而避免潛在的未定義行為。

asanread 會檢查對 key 的讀取操作是否安全，例如是否越界或是否訪問了已釋放的內存。

if msanenabled && h != nil {msanread(key, t.Key.Size_)
}
if asanenabled && h != nil {asanread(key, t.Key.Size_)
}

空檢查

如果 map 為空，直接返回值類型的零值。

if h == nil || h.count == 0 {if err := mapKeyError(t, key); err != nil {panic(err) // see issue 23734}return unsafe.Pointer(&zeroVal[0])
}

并發(fā)寫檢查

如果 map 正在被寫入（hashWriting 標志被設置），拋出并發(fā)讀寫錯誤，這一點也表明 map 并不支持并發(fā)安全。

if h.flags&hashWriting != 0 {fatal("concurrent map read and map write")
}

哈希值計算

使用鍵的哈希函數計算哈希值，其中 h.hash0 是哈希種子，用于避免哈希沖突。

hash := t.Hasher(key, uintptr(h.hash0))

桶定位

代碼中使用哈希值的低 B 位（bucketMask(h.B)）定位到初始桶。其中 BucketSize 是每個桶的大小（包括鍵和值的存儲）。

m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))

擴容情況處理

如果當前真正在擴容，那么檢查舊的桶數組 oldbuckets。如果舊桶尚未遷移完成（!evacuated(oldb)），使用舊桶進行查找。

if c := h.oldbuckets; c != nil {if !h.sameSizeGrow() {// There used to be half as many buckets; mask down one more power of two.// 如果擴容前的桶數量是當前的一半，進一步掩碼哈希值m >>= 1}oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))if !evacuated(oldb) {b = oldb}
}

桶內查找

// 獲取鍵的哈希值的最高字節(jié)
top := tophash(hash)
bucketloop:// 遍歷當前桶及其溢出桶for ; b != nil; b = b.overflow(t) {// 遍歷桶內的所有鍵值對for i := uintptr(0); i < abi.MapBucketCount; i++ {// 檢查當前個鍵的哈希值最高字節(jié)是否匹配，如果不相等，說明當前槽位的鍵與目標鍵不匹配if b.tophash[i] != top {// 如果遇到空槽（emptyRest）跳出桶循環(huán)，因為后續(xù)槽位都是空的if b.tophash[i] == emptyRest {break bucketloop}// 不匹配則跳過當前槽位continue}// 計算第 i 個鍵的地址k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))// 如果鍵是指針類型，解引用鍵的指針if t.IndirectKey() {k = *((*unsafe.Pointer)(k))}// 比較傳入的鍵和當前鍵是否相等if t.Key.Equal(key, k) {// 計算第 i 個值的地址e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))// 如果值是指針類型，解引用值的指針if t.IndirectElem() {e = *((*unsafe.Pointer)(e))}// 返回值的指針return e}}}// 如果未找到，則返回值類型的零值指針return unsafe.Pointer(&zeroVal[0])

根據上一小結中的 bmap 數據存儲模型可知，桶內查找中最為重要的就是鍵的偏移量計算和值的偏移量計算，如下所示：

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))

其中，dataOffset 是 tophash 數組之后的偏移量，i * uintptr(t.KeySize) 是計算得第 i 個鍵的偏移量。

e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))

其中，dataOffset + abi.MapBucketCount*uintptr(t.KeySize) 是值的起始偏移量（所有鍵之后）；i * uintptr(t.ValueSize) 是第 i 個值的偏移量。

鍵值插入、擴容機制

在 map 實現中，當插入元素到達一定的時機后會觸發(fā)擴容機制，下面從元素的插入開始深入研究映射的擴容機制。

在 golang 中，mapassign 是一個底層的運行時函數，用于實現 map 的賦值操作。當使用 m[key] = value 語法向 map 中插入或更新鍵值對時，最終會調用 mapassign 函數。

源碼位置：src/runtime/map.go

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
//
// mapassign should be an internal detail,
// but widely used packages access it using linkname.
// Notable members of the hall of shame include:
//   - github.com/bytedance/sonic
//   - github.com/cloudwego/frugal
//   - github.com/RomiChan/protobuf
//   - github.com/segmentio/encoding
//   - github.com/ugorji/go/codec
//
// Do not remove or change the type signature.
// See go.dev/issue/67401.
//
//go:linkname mapassign
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {// ...
}

根據上面的函數原型參數解釋：

• t *maptype 是 map 的類型信息。
• h *hmap 是 map 的底層數據結構。
• key unsafe.Pointer 是要插入或更新的鍵的指針。

將 mapassign 函數內部將代碼執(zhí)行流程劃分了如下幾個階段：

• 參數檢查
• 競態(tài)檢測
• Sanitizer 檢測
• 并發(fā)檢測
• 哈希值計算
• 初始化桶數組
• 定位桶和處理擴容
• 遍歷桶并檢查鍵
• 檢查是否需要擴容
• 插入或更新鍵值對
• 返回值的地址

下面針對每一步驟進行詳細說明。

參數檢查

如果 h 是 nil，則直接拋出錯誤，因為不能對 nil 的 map 進行賦值。

if h == nil {panic(plainError("assignment to entry in nil map"))
}

競態(tài)檢測

如果啟用了競態(tài)檢測，記錄當前操作的上下文，以便在發(fā)生競態(tài)時能夠追蹤。

if raceenabled && h != nil {callerpc := getcallerpc()pc := abi.FuncPCABIInternal(mapaccess1)racereadpc(unsafe.Pointer(h), callerpc, pc)raceReadObjectPC(t.Key, key, callerpc, pc)
}

Sanitizer 檢測

asanread 會檢查對 key 的讀操作是否安全，例如是否越界或是否訪問了已釋放的內存。

if msanenabled && h != nil {msanread(key, t.Key.Size_)
}
if asanenabled && h != nil {asanread(key, t.Key.Size_)
}

并發(fā)檢測

如果 h.flags 中的 hashWriting 標志被設置，說明當前有其他協程正在寫入 map，直接觸發(fā) fatal 錯誤。這也說明 map 不支持并發(fā)寫入。

if h.flags&hashWriting != 0 {fatal("concurrent map writes")
}

哈希值計算

使用鍵的哈希函數計算哈希值，并結合哈希種子以避免哈希沖突。

hash := t.Hasher(key, uintptr(h.hash0))

初始化桶數組

如果 map 的桶數組尚未初始化，則分配一個初始大小的桶數組（默認）。

if h.buckets == nil {h.buckets = newobject(t.Bucket) // newarray(t.Bucket, 1)
}

定位桶和處理擴容

again:bucket := hash & bucketMask(h.B)	// 計算當前鍵的哈希值對應的桶索引if h.growing() {	// 如果 hashWriting 被設置，表示 map 正在擴容，則調用 growWork 函數處理擴容邏輯growWork(t, h, bucket)}

growWork 函數是擴容的核心邏輯，負責遷移舊桶中的數據到新桶中，源碼如下所示：

func growWork(t *maptype, h *hmap, bucket uintptr) {// make sure we evacuate the oldbucket corresponding// to the bucket we're about to use// bucket&h.oldbucketmask() 表示當前桶索引對應的舊桶索引evacuate(t, h, bucket&h.oldbucketmask())	// 將舊桶中的數據遷移到新桶中// evacuate one more oldbucket to make progress on growingif h.growing() {	// 檢查是否設置了 hashWriting 標志，表示 map 是否正在擴容// h.nevacuate 記錄當前需要遷移的舊桶索引evacuate(t, h, h.nevacuate)}
}

需要注意的是每次遷移完成一個舊桶后，h.nevacuate 才會更新為下一個需要遷移的舊桶索引，這樣設計的好處是避免一次性遷移所有數據導致的性能抖動。

下面介紹 evacuate 函數，它的核心邏輯包括：

• 遍歷舊桶及其溢出桶。
• 將舊桶中的鍵值對重新哈希并插入到新桶中。
• 更新 h.nevacuate 需要遷移的舊桶索引，并記錄已遷移的舊桶數量。

函數定義如下所示：

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {// ...
}

• t：map 的類型信息。
• h：map 的底層數據結構。
• oldbucket：當前需要遷移的舊桶索引。

函數內容如下所示：

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {// 通過舊桶數組的指針和舊桶索引，計算出當前舊桶的地址// h.oldbuckets: 舊桶數組的指針// oldbucket*uintptr(t.BucketSize)): 計算當前舊桶的偏移量// 然后通過 add 函數計算處舊桶的地址b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))// 算新桶的掩碼值newbit := h.noldbuckets()if !evacuated(b) {	// 檢查當前舊桶是否已經被遷移，如果未遷移，則執(zhí)行以下邏輯var xy [2]evacDstx := &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, abi.MapBucketCount*uintptr(t.KeySize))// 如果擴容，則初始化第二個遷移目標if !h.sameSizeGrow() {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, abi.MapBucketCount*uintptr(t.KeySize))}// 遍歷當前舊桶及其所有溢出桶for ; b != nil; b = b.overflow(t) {k := add(unsafe.Pointer(b), dataOffset)	// 當前桶中鍵的首地址e := add(k, abi.MapBucketCount*uintptr(t.KeySize))	// 當前桶中值的首地址// 遍歷當前桶中的所有鍵值對for i := 0; i < abi.MapBucketCount; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) {top := b.tophash[i]	// 當前鍵值對的哈希高位值// 如果當前鍵值對為空，標記該槽已遷移且為空if isEmpty(top) {b.tophash[i] = evacuatedEmptycontinue}// 如果哈希高位值小于 minTopHash，表示哈希表狀態(tài)異常if top < minTopHash {throw("bad map state")}// 判斷鍵是否為指針類型，如果是指針類型，則解引用指針獲取實際地址k2 := kif t.IndirectKey() {k2 = *((*unsafe.Pointer)(k2))}// 判斷是遷移到 x 還是遷移到 yvar 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.Hasher(k2, uintptr(h.hash0))// 判斷是否是 NaN 鍵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.// 使用舊桶的 tophash 的最低位決定是否遷移到桶 yuseY = top & 1top = tophash(hash)	// 重新計算 tophash} else {// 對于普通鍵，根據新哈希值的 newbit 是否是1來決定是否遷移到桶y中if hash&newbit != 0 {useY = 1}}}if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {throw("bad evacuatedN")}// 標記當前鍵值對已遷移b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY// 確定遷移目的桶dst := &xy[useY]                 // evacuation destination// 判斷目標桶是否已經滿了，如果已經滿了，則創(chuàng)建一個新的溢出桶，然后繼續(xù)遷移if dst.i == abi.MapBucketCount {dst.b = h.newoverflow(t, dst.b)dst.i = 0dst.k = add(unsafe.Pointer(dst.b), dataOffset)dst.e = add(dst.k, abi.MapBucketCount*uintptr(t.KeySize))}// 下面為真正遷移的代碼，每行都是簡單的指針操作，不再贅述dst.b.tophash[dst.i&(abi.MapBucketCount-1)] = top // mask dst.i as an optimization, to avoid a bounds checkif 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.ValueSize))}}// Unlink the overflow buckets & clear key/elem to help GC.// 如果舊桶不再被迭代器使用，清理舊桶中的指針以幫助 GCif h.flags&oldIterator == 0 && t.Bucket.Pointers() {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) - dataOffsetmemclrHasPointers(ptr, n)}}// 如果當前桶是正在遷移的桶，更新遷移進度if oldbucket == h.nevacuate {advanceEvacuationMark(h, t, newbit)}
}

遍歷桶并檢查鍵

下面這段代碼遍歷目標桶及其溢出桶，尋找合適的插入位置或更新現有鍵值對。如下所示：

// 通過目標桶的索引 bucket 定位到對應的桶
b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
// 根據鍵的哈希值計算其哈希高位值
top := tophash(hash)var inserti *uint8
var insertk unsafe.Pointer
var elem unsafe.Pointer
bucketloop:for {// 遍歷當前桶的所有槽位for i := uintptr(0); i < abi.MapBucketCount; i++ {// 當前槽位的哈希高位值是否與目標值匹配，如果不匹配，說明當前槽位不包含目標鍵if b.tophash[i] != top {// 如果當前槽位為空且未找到空閑槽位，則記錄該槽位，用于后續(xù)插入if isEmpty(b.tophash[i]) && inserti == nil {// inserti:空閑槽地址inserti = &b.tophash[i]// insertk:空閑槽鍵的地址insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))// elem:空閑槽值的地址elem = add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))}// 如果當前槽位的哈希值為 emptyRest，說明后續(xù)槽位均為空，結束遍歷if b.tophash[i] == emptyRest {break bucketloop}continue}// 獲取當前槽的鍵地址k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))if t.IndirectKey() {	// 是否是指針類型，如果是指針類型，需要解引用k = *((*unsafe.Pointer)(k))}if !t.Key.Equal(key, k) { // 鍵不相等，直接跳過continue}// 找到匹配的鍵，更新其值// already have a mapping for key. Update it.if t.NeedKeyUpdate() {typedmemmove(t.Key, k, key)	// 復制目標鍵到當前鍵位置}// 計算值的地址elem = add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))goto done	// 結束操作}// 如果當前桶未找到匹配的鍵或空閑槽位，則檢查溢出桶ovf := b.overflow(t)	// 獲取當前桶的溢出桶if ovf == nil {break	// 如果沒有溢出桶，則結束遍歷}b = ovf	// 如果有溢出桶，更新桶的地址}

檢查是否需要擴容

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
}

根據上述代碼中的邏輯，核心在于 overLoadFactor 和 tooManyOverflowBuckets 的判斷，下面對這兩個函數進行刨析。

overLoadFactor

判斷當前 map 的負載因子是否超過了設定的閾值。其中 count 表示當前 map 中的鍵值對數量；B 表示當前 map 的桶數量的對數（2^B 是當前桶的數量）。

func overLoadFactor(count int, B uint8) bool {return count > abi.MapBucketCount && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

具體計算邏輯如下所示：

• count > abi.MapBucketCount：確保鍵值對數量大于單個桶的容量（8 個鍵值對）。

• uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)：計算當前負載因子是否超過閾值。

$$loadFactorDen=2$$

$$\begin{gathered} loadFactorNum \\ =loadFactorDen?abi.MapBucketCount?13/16 \\ =2?8?13/16 \\ =13 \end{gathered}$$

func bucketShift(b uint8) uintptr {// Masking the shift amount allows overflow checks to be elided.return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}

• goarch.PtrSize：表示指針的大小（以字節(jié)為單位）。在 64 位系統(tǒng)中，goarch.PtrSize = 8；在 32 位系統(tǒng)中，goarch.PtrSize = 4。

假設 B = 3 則有：

$$\begin{gathered} bucketShift(B)=>bucketShift(3) \\ =uintptr(1)<<(3\&(8?8?1)) \\ =uintptr(1)<<3\&63 \\ =uintptr(1)<<3 \\ =8 \end{gathered}$$

綜上所述，結算結果為：

$$\begin{gathered} uintptr(count)>loadFactorNum?(bucketShift(B)/loadFactorDen) \\ =uintptr(count)>13?(8/2) \\ =13?4 \\ =52 \end{gathered}$$

因此，當鍵值對數量 count 超過 52 時，overLoadFactor 返回 true，觸發(fā)擴容。

通過負載因子（loadFactorThreshold）可以快速的計算出擴容的時機，公式如下所示：

$$\begin{gathered} loadFactorThreshold \\ =loadFactorNum/loadFactorDen \\ =13/2 \\ =6.5 \end{gathered}$$

這意味著當鍵值對數量超過 當前桶的容量 的 6.5 倍 時，map 會觸發(fā)擴容。

tooManyOverflowBuckets

判斷當前 map 的溢出桶數量是否過多。如果溢出桶數量過多，說明 map 的哈希表分布不夠均勻，需要擴容以優(yōu)化性能。

// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets.
// Note that most of these overflow buckets must be in sparse use;
// if use was dense, then we'd have already triggered regular map growth.
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {// If the threshold is too low, we do extraneous work.// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.// "too many" means (approximately) as many overflow buckets as regular buckets.// 當溢出桶的數量接近或超過當前桶的數量時，認為溢出桶過多。// See incrnoverflow for more details.if B > 15 {// 如果 B 大于 15，將其限制為 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)
}

• noverflow：當前 map 的溢出桶數量。
• B：當前 map 的桶數量的對數（2^B 是當前桶的數量）。

為什么限制 B 的最大值為 15？

首先對于 map 來說 2^15 = 32768，這已經是一個非常大的哈希表。另外對于內存的使用效率來說，如果 B 超過 15 可能會導致內存使用過多，或者哈希表過于稀疏，從而降低性能。

插入或更新鍵值對

插入位置為空

if inserti == nil {// The current bucket and all the overflow buckets connected to it are full, allocate a new one.// 檢查當前的插入位置是否為空。如果為空，說明當前桶及其所有溢出桶都已滿，需要分配一個新的溢出桶newb := h.newoverflow(t, b)	// 創(chuàng)建一個新的溢出桶inserti = &newb.tophash[0]	// 指向新溢出桶的第一個 tophash 位置。tophash 是一個數組，用于存儲鍵的哈希值的高位信息insertk = add(unsafe.Pointer(newb), dataOffset)	// 計算新溢出桶中鍵的存儲位置。add 是一個低級操作，用于通過偏移量計算指針位置。dataOffset 是鍵值對數據在桶中的偏移量elem = add(insertk, abi.MapBucketCount*uintptr(t.KeySize))	// 計算新溢出桶中值的存儲位置。abi.MapBucketCount 是每個桶中鍵值對的數量，t.KeySize 是鍵的大小。通過偏移量計算出值的存儲位置
}

存儲新的鍵值對

// store new key/elem at insert position
if t.IndirectKey() {	// 判斷鍵是否是指針類型。如果是指針類型，則需要間接存儲kmem := newobject(t.Key)	// 分配一個新的對象，用于存儲鍵*(*unsafe.Pointer)(insertk) = kmem	// 將分配的對象地址存儲到 insertk 指向的位置insertk = kmem	// 更新 insertk 使其指向實際的鍵存儲位置
}if t.IndirectElem() {	// 判斷值是否是指針類型。如果是指針類型，則需要間接存儲vmem := newobject(t.Elem)	// 分配一個新的對象，用于存儲值*(*unsafe.Pointer)(elem) = vmem	// 將分配的對象地址存儲到 elem 指向的位置
}typedmemmove(t.Key, insertk, key) // 將傳入的鍵 key 復制到 insertk 指向的位置
*inserti = top	// 將鍵的哈希值的高位信息存儲到 inserti 指向的位置。top 是哈希值的高位部分
h.count++	// 增加哈希表的計數器 count，表示哈希表中鍵值對的數量增加了一個

返回值的地址

done:if h.flags&hashWriting == 0 {	// 檢查 h.flags 是否設置了 hashWriting 標志// hashWriting 在 map 寫入操作開始時設置，寫入操作結束時清除。它用于檢測并發(fā)寫入沖突// 如果檢測到并發(fā)寫入，調用 fatal 函數拋出致命錯誤fatal("concurrent map writes")}h.flags &^= hashWriting	// 清除 hashWriting 標志if t.IndirectElem() {	// 判斷 map 的值是否是指針類型elem = *((*unsafe.Pointer)(elem)) // 如果 map 的值是指針類型，則需要通過指針解引用獲取實際的值地址}return elem	// 返回值的地址

鍵值刪除

在 golang 中，mapdelete 是一個底層的運行時函數，用于實現 map 的鍵值刪除邏輯。

源碼位置：src/runtime/map.go

下面給出函數原型，如下所示：

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {// ...
}

• t：map 的類型信息。
• h：map 的底層數據結構。
• key：要刪除的鍵的指針。

將 mapdelete 函數中的代碼邏輯分為如下幾個階段：

• 競態(tài)檢測
• Sanitizer 檢測
• 參數檢查
• 并發(fā)檢測
• 設置寫入標記
• 計算哈希值和目標桶
• 處理擴容
• 定位目標桶
• 查找鍵值對
• 刪除目標鍵值對
• 清理空閑槽
• 重置哈希種子
• 清除寫入標記

下面針對每一步驟進行詳細說明。

競態(tài)檢測

如果啟用了競態(tài)檢測，記錄對 map 的寫操作和鍵的讀操作，以便在發(fā)生競態(tài)時能夠追蹤。

if raceenabled && h != nil {callerpc := getcallerpc()pc := abi.FuncPCABIInternal(mapdelete)// 記錄寫操作的程序計數器信息racewritepc(unsafe.Pointer(h), callerpc, pc)// 記錄讀操作的程序計數器信息raceReadObjectPC(t.Key, key, callerpc, pc)
}

Sanitizer 檢測

記錄鍵的讀操作，檢測未初始化或越界的內存訪問。

if msanenabled && h != nil {msanread(key, t.Key.Size_)
}
if asanenabled && h != nil {asanread(key, t.Key.Size_)
}

參數檢查

如果 map 為 nil 或者鍵值對數量為 0，直接返回。如果鍵無效 mapKeyError 則報出異常。

if h == nil || h.count == 0 {if err := mapKeyError(t, key); err != nil {panic(err) // see issue 23734}return
}

并發(fā)檢測

檢查是否已經有其他協程正在寫入 map，不支持并發(fā)操作。

if h.flags&hashWriting != 0 {fatal("concurrent map writes")
}

設置寫入標記

設置 hashWriting 標志，表示當前正在寫入 map。

h.flags ^= hashWriting

計算哈希值和目標桶

計算鍵的哈希值和目標桶的索引，用于定位目標桶。

hash := t.Hasher(key, uintptr(h.hash0))
bucket := hash & bucketMask(h.B)

處理擴容

如果 map 正在擴容，調用 growWork 處理擴容邏輯。

有關擴容的源碼分析，請查看 “鍵值插入、擴容機制” 小結。

if h.growing() {growWork(t, h, bucket)
}

定位目標桶

通過目標桶的索引 bucket ，進行指針偏移定位到對應的桶

b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
bOrig := b

查找目標鍵

// 根據鍵的哈希值計算其哈希高位值
top := tophash(hash)
search:// 遍歷目標桶及其所有溢出桶for ; b != nil; b = b.overflow(t) {// 遍歷當前桶中的所有鍵值對for i := uintptr(0); i < abi.MapBucketCount; i++ {// 如果當前槽位的哈希值不匹配，跳過if b.tophash[i] != top {// 如果遇到 emptyRest，表示后續(xù)槽位均為空，結束搜索if b.tophash[i] == emptyRest {break search}continue}// 獲取當前槽的鍵地址k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))k2 := kif t.IndirectKey() {	// 判斷鍵是否為指針類型k2 = *((*unsafe.Pointer)(k2))}if !t.Key.Equal(key, k2) {	// 比較鍵是否相等，如果不相等則跳過本次循環(huán)continue}// 刪除目標鍵值對}}

刪除目標鍵值對

刪除鍵值對的核心邏輯，負責清空鍵和值的內容，并更新桶的狀態(tài)。

// Only clear key if there are pointers in it.
if t.IndirectKey() {	// 判斷鍵是否為指針類型*(*unsafe.Pointer)(k) = nil	// 如果是指針類型，直接將指針置為 nil
} else if t.Key.Pointers() {memclrHasPointers(k, t.Key.Size_)	// 如果鍵包含指針，則清空鍵的內容，幫助 GC
}// 計算當前槽位的值的地址
e := add(unsafe.Pointer(b), dataOffset+abi.MapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
// 根據值的類型，清空值的內容
if t.IndirectElem() {	// 判斷值是否為指針類型*(*unsafe.Pointer)(e) = nil	// 如果是指針類型，直接將指針置為 nil
} else if t.Elem.Pointers() {	// 判斷值是否包含指針memclrHasPointers(e, t.Elem.Size_)	// 如果值包含指針，則清空值的內容，幫助 GC
} else {memclrNoHeapPointers(e, t.Elem.Size_)	// 如果值不包含指針，則清空值的內容，不需要指針操作
}// 更新槽位狀態(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.
// 檢查當前槽是否是最后一個槽，以及后續(xù)槽是否需要繼續(xù)清理
if i == abi.MapBucketCount-1 {// 如果當前桶有溢出桶并且溢出桶的第一個槽不是 emptyRest，表示后續(xù)槽仍包含數據if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {goto notLast}
} else {// 下一個槽不是 emptyRest，表示后續(xù)槽仍包含數據if b.tophash[i+1] != emptyRest {goto notLast}
}// 清理空閑槽
for {// 將當前槽的狀態(tài)更新為 emptyRestb.tophash[i] = emptyRestif 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 = abi.MapBucketCount - 1	// 繼續(xù)清理前一個桶的最后一個槽} else {// 繼續(xù)清理當前桶的前一個槽i--}// 如果當前槽不是 emptyOne，清理完成 if b.tophash[i] != emptyOne {break}
}
notLast:// 減少鍵值對的數量h.count--

重置哈希種子

如果 map 中沒有鍵值對，重置哈希種子以防止哈希碰撞攻擊

if h.count == 0 {h.hash0 = uint32(rand())
}

清除寫入標記

清除 hashWriting 標志，表示寫入操作完成

// 如果標志未設置，說明可能存在并發(fā)寫入問題
if h.flags&hashWriting == 0 {fatal("concurrent map writes")
}// 清除
h.flags &^= hashWriting

常用操作

訪問映射值

通過鍵訪問對應的值，格式如下所示：

value := m["key"]

其中，如果鍵不存在，則返回值類型的零值。例如：

package mainimport "fmt"func main() {m := map[string]int{"apple":  1,"banana": 2,"cherry": 3,}fmt.Println(m["apple"])  // 1fmt.Println(m["orange"]) // 0
}

檢查鍵是否存在

通過多值賦值檢查鍵是否存在，格式如下所示：

value, ok := m["key"]
if ok {fmt.Println("Key exists, value:", value)
} else {fmt.Println("Key does not exist")
}

• ok 是一個布爾值，表示鍵是否存在。
• 如果鍵存在，ok 為 true，value 是對應的值。
• 如果鍵不存在，ok 為 false，value 是值類型的零值。

例如：

package mainimport "fmt"func main() {m := map[string]int{"apple":  1,"banana": 2,"cherry": 3,}value, ok := m["apple"]if ok {fmt.Println("Key exists, value:", value) // Key exists, value: 1} else {fmt.Println("Key does not exist")}
}

修改映射的值

通過鍵直接賦值，格式如下所示：

m["key"] = newValue

例如：

package mainimport "fmt"func main() {m := map[string]int{"apple":  1,"banana": 2,"cherry": 3,}m["apple"] = 10         // 修改鍵為 "apple" 的值為 10fmt.Println(m["apple"]) // 10
}

添加鍵值對

直接賦值即可，格式如下所示：

m["newKey"] = newValue

例如：

package mainimport "fmt"func main() {m := map[string]int{"apple":  1,"banana": 2,"cherry": 3,}m["orange"] = 4          // 添加鍵為 "orange"，值為 4 的鍵值對fmt.Println(m["orange"]) // 4
}

刪除鍵值對

使用 delete 函數進行刪除，格式如下所示：

delete(m, "key")

例如：

package mainimport "fmt"func main() {m := map[string]int{"apple":  1,"banana": 2,"cherry": 3,}fmt.Println(m["banana"]) // 2delete(m, "banana")      // 刪除鍵為 "banana" 的鍵值對fmt.Println(m["banana"]) // 0
}

遍歷映射

使用 for range 循環(huán)遍歷映射中的鍵值對，例如：

package mainimport "fmt"func main() {m := map[string]int{"apple":  1,"banana": 2,"cherry": 3,}// Key: apple, Value: 1// Key: banana, Value: 2// Key: cherry, Value: 3for key, value := range m {fmt.Printf("Key: %v, Value: %v\n", key, value)}
}

需要注意的是，映射的遍歷順序是隨機的，因為映射內部是無序的。

獲取映射長度

使用 len 函數獲取映射中鍵值對的數量，例如：

package mainimport "fmt"func main() {m := map[string]int{"apple":  1,"banana": 2,"cherry": 3,}length := len(m)fmt.Println(length) // 3
}

映射嵌套

映射的值可以是任何類型，包括另一個映射，從而實現嵌套映射，例如：

package mainimport "fmt"func main() {nestedMap := map[string]map[string]int{"fruits": {"apple":  1,"banana": 2,},"vegetables": {"carrot":   3,"broccoli": 4,},}fmt.Println(nestedMap["fruits"]["apple"]) // 1
}

映射的拷貝

映射是引用類型，直接賦值會共享同一個底層數據結構。如果需要拷貝映射，需要手動創(chuàng)建一個新的映射并復制鍵值對。例如：

package mainimport "fmt"func main() {m1 := map[string]int{"apple":  1,"banana": 2,}m2 := make(map[string]int)for key, value := range m1 {m2[key] = value	// 深拷貝}// Key: apple, Value: 1// Key: banana, Value: 2for key, value := range m2 {fmt.Printf("Key: %s, Value: %d\n", key, value)}m2["apple"] = 3fmt.Println(m1["apple"]) // 此時訪問 m1 中的 apple，并沒有修改
}

清空映射

雖然 golang 沒有直接清空映射的函數，但可以通過遍歷映射并刪除所有鍵值對來實現。例如：

package mainimport "fmt"func main() {m := map[string]int{"apple":  1,"banana": 2,}fmt.Println(len(m)) // 2for key := range m {delete(m, key)}fmt.Println(len(m)) // 0
}

常見問題

檢查鍵是否存在

在訪問映射中的值之前，應始終檢查鍵是否存在，以避免誤用零值。例如：

value, exists := myMap["key"]
if exists {fmt.Println("Value:", value)
} else {fmt.Println("Key does not exist")
}

初始化映射時指定容量

如果已知映射的大小，建議在初始化時指定容量，以減少后續(xù)的內存重新分配。例如：

myMap := make(map[string]int, 100) // 預計映射大小為 100

避免并發(fā)修改

golang 的映射不是線程安全的，因此在并發(fā)場景下直接修改映射會導致競態(tài)條件。

• 使用 sync.Mutex 加鎖保護映射

var mu sync.Mutex
mu.Lock()
myMap["key"] = value
mu.Unlock()

• 使用并發(fā)安全的映射 sync.Map，這個是 golang 標準庫中提供的數據類型。

var myMap sync.Map
myMap.Store("key", 1) // 存儲鍵值對
val, ok := myMap.Load("key") // 根據鍵讀取值

關于更多并發(fā)相關的知識點，請關注后續(xù)文章 《Golang 并發(fā)編程》。

不使用映射存儲大量的數據

映射是基于哈希表實現的，其內部結構需要額外的內存來存儲哈希值、指針和元數據。也就是說映射的內存占用通常比數組或切片更高。對于大量數據，這種額外的內存開銷可能會導致顯著的性能問題。

下面給出一些可以替代的方案：

• 使用外部數據庫存儲大規(guī)模數據。
• 使用切片存儲，切片的內存占用相對較低，另外對于有序的數據切片的性能通常會優(yōu)于映射的性能。
• 采用分塊存儲，將多個數據分散到不同的映射中，每個映射負責一部分數據，從而減少擴容的開銷。
• 定期清理不需要的鍵值對，優(yōu)化內存使用。
• 另外如果對于數據量較小且不需要頻繁查詢的數據，可以考慮其他的數據結構。

🌺🌺🌺撒花！

如果本文對你有幫助，就點關注或者留個👍
如果您有任何技術問題或者需要更多其他的內容，請隨時向我提問。