golang map
2023-02-11 本文已影响0人
robertzhai
type hmap struct {
count int // 当前 map 中的元素个数，用于 len() 操作。
flags uint8 // 用于记录 map 当前状态，如是否正在执行写操作，后面会具体介绍。
B uint8 // 该值用于控制常规桶数组的长度。
noverflow uint16 // 用到的溢出桶的大概个数，为啥是大概？后面介绍溢出桶时候再说。
hash0 uint32 // hash seed，后面会具体介绍。
buckets unsafe.Pointer // 指向当前桶数组地址的指针，数组长度 2^B 。
oldbuckets unsafe.Pointer // 用于扩容过程中，保存扩容旧的桶数组的指针，仅在扩容阶段非 nil。
nevacuate uintptr // 用于在扩容过程中记录迁移进度，小于这个数的桶索引是已经迁移完成的。
extra *mapextra // 保存了 map 的一些可选数据。
}
// 保存了 map 的一些可选数据，不是每个 map 都有该数据，目前主要保存了溢出桶相关数据。
// bmap 是桶的结构，下面会再单独介绍。
type mapextra struct {
// 下面 2 个是比较特别的指针数组，和 GC 相关，仅在 bmap 不包含指针时候使用，溢出桶部分会详细介绍。
overflow *[]*bmap // 存储 buckets 用到的溢出桶指针集合。
oldoverflow *[]*bmap // 存储 oldbuckets 用到的溢出桶指针集合。
nextOverflow *bmap // 存储下一个可用的溢出桶指针。
}
// 桶的数据结构。
type bmap struct {
// 槽位状态数组，槽位无数据时用于快速判断槽位状态，
// 槽位有数据时则存储了 hash(key) 的最高字节。
tophash [bucketCnt]uint8
}
- Go 语言中使用拉链法来解决哈希碰撞的问题实现了哈希表，访问、写入和删除等操作都在编译期间被转换成了对应的运行时函数或者方法。
- 哈希在每一个桶中存储键对应哈希的前 8 位，当对哈希进行操作时，这些 tophash 就成为了一级缓存帮助哈希快速遍历桶中元素，每一个桶都只能存储 8 个键值对，一旦当前哈希的某个桶超出 8 个，新的键值对就会被存储到哈希的溢出桶中。
- 随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围时就会触发扩容操作，扩容时会将桶的数量分配，元素再分配的过程也是在调用写操作时增量进行的，不会造成性能的瞬时巨大波动。
image.png
