Go 中 map 使用哈希表来作为底层实现，一个哈希表可以有多个哈希表节点，即 bucket，每个 bucket 保存了 map 中的一个或一组键值对。map 的一些基础使用可以看下之前的文章，传送门。
先声明文中使用的 Go 版本为：
go version go1.16.3 windows/amd64
map 数据结构在
在 runtime/map.go 定义如下：
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}
复制代码
bucket大多时候被翻译为桶，哈希桶 即 bucket。
如图展示了一个拥有 4 个 bucket 的 map:
元素在经过哈希运算之后，会在某个 bucket 中存储，查找过程也如此。
bucket 数据结构
在 runtime/map.go 定义如下：
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 [bucketCnt]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.}
复制代码
bmap 存储了一个 unit8 类型的数组--tophash。
评论