完整内容在此, 干话王_了解 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