点击上方蓝色“后端开发杂谈”关注我们, 专注于后端日常开发技术分享
map 数据结构与实际的数据结构
map 中的数据被存放在一个数组中的, 数组的元素是桶(bucket), 每个桶至多包含8个键值对数据. 哈希值低位(low-order bits)用于选择桶, 哈希值高位(high-order bits)用于在一个独立的桶中区别出键. 哈希值高低位示意图如下:
image 源码位于
src/runtime/map.go
.
结构体
// A header for a Go map.
type hmap struct {
count int // 代表哈希表中的元素个数, 调用len(map)时, 返回的就是该字段值.
flags uint8 // 状态标志, 下文常量中会解释四种状态位含义.
B uint8 // buckets(桶)的对数log_2(哈希表元素数量最大可达到装载因子*2^B)
noverflow uint16 // 溢出桶的大概数量.
hash0 uint32 // 哈希种子.
buckets unsafe.Pointer // 指向buckets数组的指针, 数组大小为2^B, 如果元素个数为0, 它为nil.
oldbuckets unsafe.Pointer // 如果发生扩容, oldbuckets是指向老的buckets数组的指针, 老的buckets数组大小是新
// 的buckets的1/2.非扩容状态下, 它为nil. 它是判断是否处于扩容状态的标识
nevacuate uintptr // 表示扩容进度, 小于此地址的buckets代表已搬迁完成.
extra *mapextra // 这个字段是为了优化GC扫描而设计的. 当key和value均不包含指针, 并且都可以inline时使用.
// extra是指向mapextra类型的指针.
}
// mapextra holds fields that are not present on all maps.
type mapextra struct {
// 就使用 hmap 的 extra 字段来存储 overflow buckets,
// 如果 key 和 value 都不包含指针, 并且可以被 inline(<=128 字节), 则将 bucket type 标记为不包含指针 (使用
// ptrdata 字段, 为0表示不包含指针). 这样可以避免 GC 扫描整个 map. 但是 bmap.overflow 是一个指针. 这时候我
// 们只能把这些 overflow 的指针都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了.
//
// 当 key 和 elem 不包含指针时, 才使用 overflow 和 oldoverflow.
// overflow 包含的是 hmap.buckets 的 overflow bucket,
// oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow bucket.
overflow *[]*bmap
oldoverflow *[]*bmap
// 指向空闲的 overflow bucket 的指针(第一个空闲的bucket地址)
nextOverflow *bmap
}
// A bucket for a Go map.
type bmap struct {
// tophash包含此桶中每个键的哈希值最高字节(高8位)信息(也就是前面所述的high-order bits).
// 如果tophash[0]
tophash [bucketCnt]uint8
}
常量值
bmap(即map当中的bucket)内存结构
hmap (即map) 内存结构
bmap 也就是 bucket(桶)的内存模型图解如下(代码逻辑就是上述的
bmap
函数).
image
该桶的第7,8位cell还未有对应的键值对. 注意: key和value是各自存储起来的, 并非想象中的 key/value/key/value…的形式. 这样的做法好处在于消key/value之间的padding, 例如
map[int64]int
. 还有,在8个键值对数据后面还有一个overflow指针, 因为桶中最多只能装8个键值对, 如果有多余的键值对落到当前桶, 那么就需要再构建一个桶(溢出桶), 通过 overflow 指针链接起来.
最后, 这里展示一个 B=4 的完整 map 结构:
image
-
参考链接
1.8 万字详解 Go 是如何设计 Map 的