完整內容在此, 幹話王_了解 Go Map

GO map shrink 最近同事給了我這篇文章, 文章想證明 Go 的 map 哪怕改成 swisstable 版本, 在元素都刪除後且 GC 發生後, map 的大小依然不那麼小, 好像不會 shrink. 但這問題的根本我們得先了解 map 的組成.

1.23 版本的 Map

[Source Code](https://github.com/golang/go/blob/go1.23.0/src/runtime/map.go) Go 的 map 實際上是基於 hash table 的資料結構。資料存儲在一個 bucket 的array 中，每個 bucket(Go的map中叫 bmap) 可以存放 8 個key value pair 。 選擇bucket的方式是透過 hash value 的低位值來選擇對應的bucket。如果要存入新的元素時, 所處的 bucket 元素個數已經 8 個了, 則會進行 overflow 的處理, 會使用額外的 bucket 來存儲這些額外的key value。新的overflow bucket 會被鏈接到本來的 bucket，形成一個linked list結構。當然 overflow bucket 只去臨時性的應對方案, 當 overflow bucket 太多時會進行 groupup 擴容.

而當 hash table 的大小達到一定的負載因子(load factor) 時，會將 bucket 的數量成倍增加，通常是將 bucket array 的大小擴展為原來的兩倍。在擴展過程中，舊的 bucket array 中的 bucket 會被逐步複製到新的、更大的 bucket array中(hashGrow+growWork+evacuate )。

// map 的主要結構，包含了關於整個 map 的 metadata
type hmap struct {
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
	flags     uint8
	B         uint8  // log_2  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
}
// 用於儲存與 map 相關的額外資訊，特別是與 overflow bucket 管理相關的內容。
type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
	nextOverflow *bmap
}
// 每個 bucket 的結構，實際儲存 key-value pair 的數據
// 但因為元素的key與value 的類型其實是動態執行時期才會得知的, 所以編譯時期如下
type bmap struct {
	tophash [abi.MapBucketCount]uint8
}

// 當宣告好 map 的類型時, 就會產生如下的結構
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

完整內容在此, 幹話王_了解 Go Map