MAP底层原理分析
参考
- https://golang.design/go-questions/map/principal
- map | Golang 中文学习文档
-
先来看一下map结构体，（
runtime.hmap结构体就是代表着 go 中的map，与切片一样map的内部实现也是结构体）type hmap struct {// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/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 uint8B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for detailshash0 uint32 // hash seedbuckets 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 growingnevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)clearSeq uint64extra *mapextra // optional fields }内部实现图
简单说明一下各个字段含义
-
count：表示 hamp 中的元素数量，结果等同于len(map) -
flags: hmap 的标志位，用于表示 hmap 处于什么状态，有以下几种可能const (iterator = 1 // 迭代器正在使用桶oldIterator = 2 // 迭代器正在使用旧桶hashWriting = 4 // 一个协程正在写入hmapsameSizeGrow = 8 // 正在等量扩容 ) -
B：hmap 中的哈希桶的数量为1 << B -
noverflow，hmap 中溢出桶的大致数量。 -
哈希种子，在 hmap 被创建时指定，用于计算哈希值。
-
buckets，存放哈希桶数组的指针。 -
oldbuckets，存放 hmap 在扩容前哈希桶数组的指针。 -
extra，存放着 hmap 中的溢出桶，溢出桶指的是就是当前桶已经满了，创建新的桶来存放元素，新创建的桶就是溢出桶。type mapextra struct {// 溢出桶的指针切片overflow *[]*bmap// 扩容前旧的溢出桶的指针切片oldoverflow *[]*bmap// 指向下一个空闲的溢出桶的指针nextOverflow *bmap }
-
一直说的桶是个什么东西 ？
hamp 中的
buckets也就是桶切片指针，在 go 中对应的结构为runtime.bmap，如下所示// A bucket for a Go map. type bmap struct {tophash [abi.OldMapBucketCount]uint8 } // OldMapBucketCount是如下的这个变量 // Maximum number of key/elem pairs a bucket can hold. OldMapBucketCountBits = 3 // log2 of number of elements in a bucket. OldMapBucketCount = 1 << OldMapBucketCountBits // 默认为8表面上看，它只有一个字段
tophash，不过实际上来说，bmap的字段不止这些，这是因为map可以存储各种类型的键值对，所以需要在编译时根据类型来推导占用的内存空间，在cmd/compile/internal/reflectdata/reflect.go中的MapBucketType函数的功能就是在编译时构造 bmap，它会进行一系列检查工作，比如 key 的类型是否comparable。// MapBucketType makes the map bucket type given the type of the map. func MapBucketType(t *types.Type) *types.Typebmap内部结构：HOB Hash指的就是 top hash。
实际上bmap结构如下；不过这些字段对我们是不可见的，go 在实际操作中是通过移动 unsafe 指针来进行访问
// 实际运行时定义（简化为可理解的结构）
type bmap struct {// 哈希值高8位数组 (每个槽位1字节)tophash [abi.OldMapBucketCount]uint8 // bucketCnt = 8// 以下是隐式字段（编译器在编译时根据键值类型动态生成内存布局）keys [abi.OldMapBucketCount]keyType // 键数组（连续存储）elems [abi.OldMapBucketCount]elemType // 值数组（连续存储）注意：1.17+ 改名为 elems// 溢出桶指针（重要：在 keys/elems 之后存储）overflow *bmap
}
// 注意:有些文章还有pad字段 ，该字段是为了保持内存对齐，提高一些操作的效率的
tophash字段是什么 ？
首先，根据字面意思就是一个为uint8类型的长度为 8的数组 ，此时也就定义了 一个桶中可以存放8个键值对，桶中每个元素是uint8，代表每个键（key）对应的hash值得高八位， 用于定位该键（key）在本桶的位置。
另外，tophash还有一些特殊的值，通常是处于扩容的迁移状态下：
const (emptyRest = 0 // 当前元素是空的，并且该元素后面也没有可用的键值了emptyOne = 1 // 当前元素是空的，但是该元素后面有可用的键值。evacuatedX = 2 // 扩容时出现，只能出现在oldbuckets中，表示当前元素被搬迁到了新哈希桶数组的上半区evacuatedY = 3 // 扩容时出现只能出现在oldbuckets中，表示当前元素被搬迁到了新哈希桶数组的下半区evacuatedEmpty = 4 // 扩容时出现，元素本身就是空的，在搬迁时被标记minTopHash = 5 // 对于一个正常的键值来说tophash的最小值
)
minTopHash：当一个cell（每个tophash元素抽象成每一个cell） 的tophash值小于minTopHash时，标志这个cell的迁移状态。因为这个状态值是放在tophash数组里，为了和正常的哈希值区分开，会给key计算出来的哈希值一个增量：minTopHash。这样就能区分正常的top hash值和表示状态的哈希值- 其余变量是迁移过程中用到的 ，后续说明
-
key定位过程参考文章中说明的很好：
key 经过哈希计算后得到哈希值，共 64 个 bit 位（64位机，32位机就不讨论了，现在主流都是64位机），计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位。还记得前面提到过的 B 吗？如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。
例如，现在有一个 key 经过哈希函数计算后，得到的哈希结果是：
10010111 | 000011110110110010001111001010100010010110010101010 │ 01010用最后的 5 个 bit 位，也就是
01010，值为 10，也就是 10 号桶。这个操作实际上就是取余操作，但是取余开销太大，所以代码实现上用的位操作代替。再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，这是在寻找已有的 key。最开始桶内还没有 key，新加入的 key 会找到第一个空位，放入。
上图中，假定 B = 5，所以 bucket 总数就是 2^5 = 32。首先计算出待查找 key 的哈希，使用低 5 位 00110，找到对应的 6 号 bucket，使用高 8 位 10010111，对应十进制 151，在 6 号 bucket 中寻找 tophash 值（HOB hash）为 151 的 key，找到了 2 号槽位，这样整个查找过程就结束了。
如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。
key与value的定位方法
// key 定位公式
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))// value 定位公式
e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
b 是 bmap 的地址，这里 bmap 还是源码里定义的结构体，只包含一个 tophash 数组，经编译器扩充之后的结构体才包含 key，value，overflow 这些字段。dataOffset 是 key 相对于 bmap 起始地址的偏移， 也就是bmap中key地址开始的位置：
dataOffset = unsafe.Offsetof(struct {b bmapv int64}{}.v)
当定位到一个具体的 bucket 时，里层循环就是遍历这个 bucket 里所有的 cell，或者说所有的槽位，也就是 bucketCnt=8 个槽位。整个循环过程：
遍历过程中会判断每一个cell的状态 ，判断这个bucket是否搬迁完毕，源码中用到的函数
func evacuated(b *bmap) bool {h := b.tophash[0]return h > empty && h < minTopHash
}
只取了 tophash 数组的第一个值，判断它是否在 0-4 之间。对比上面的常量，当 top hash 是 evacuatedEmpty、evacuatedX、evacuatedY 这三个值之一，说明此 bucket 中的 key 全部被搬迁到了新 bucket。
电脑)
