Go 源码之 Map
一、简介
map 是一种非常常见的数据类型，它可以用于快速地检索数据；是一种 key-value 结构的数据类型，key 是唯一的，value 可以重复
●键值对为元素的数据集合
●查询时间复杂度 O (1)，最坏情况下 O (N) ，需要遍历溢出桶
●核心 hmap 和 buckets 数组（bmap） 两个结构实现，bmap 存储了八个元素
●map 读写：通过 hmap 中的 hash0 计算 key 的哈希结果：
○根据哈希值的低 8 位确定 key 所在的 buckets 数组中的位置
○根据哈希值的高 8 位 tophash（高八位）找到 bmap 中 key 和 value 数组中的位置
●map 只能用 len() 不能用 cap()，创建 map 不能指定 len，只能指定 cap，并且 cap 不是实际容量，底层根据 cap 算出实际桶（bmap）数量
●键不重复 并且 键必须可哈希（int / bool / float / string / array / 指针类型），slice / struct / interface / map 等引用类型不可哈希
image.png
image.png
image.png
二、源码
/usr/local/go/src/runtime/map.go
（一）数据结构
hmap
type hmap struct {
count int // map中元素的个数
flags uint8 // Map 的状态标志位，包括迭代器状态和是否是引用类型
// flag的一些状态位
// iterator = 1 // 有遍历器在遍历桶
// oldIterator = 2 // 有遍历器在遍历旧桶
// hashWriting = 4 // 有协程在写map
// sameSizeGrow = 8 // 等量扩容，但不是两倍扩容，而是等量扩容
B uint8 // bucket 数组的大小，即2^B个bmap
noverflow uint16 // 溢出 bucket 的数量，即产生 hash 冲突的 bucket 数量
hash0 uint32 // Map 中的哈希种子，用于 hash 函数
buckets unsafe.Pointer // 指向bucket数组的指针，bucket数组可能会在扩容时被重新分配.
oldbuckets unsafe.Pointer // 表示先前的 bucket 数组的指针，用于 Map 扩容时进行转移元素的操作
nevacuate uintptr // 表示当前正在进行 Map 扩容时的进度计数器，少于这个数字的buckets都会被回收
extra *mapextra // 表示与 Map 相关的额外信息,包括 溢出桶 信息
}
type mapextra struct {
overflow *[]*bmap // 存放的所有溢出桶的地址。
oldoverflow *[]*bmap // 存放的所有老的溢出桶的地址。这个是针对扩容的时候
nextOverflow *bmap // 指向的下一个溢出桶的地址。
}
bmap
// 源码中结构
type bmap struct {
tophash [bucketCnt]uint8
}
// 实际编译后运行时bucket结构
type bmap struct {
tophash [8]uint8 // 存储hash值的前几位，如果小于5，则表示上述的tophash状态码
keys [8]keytype // key数组，隐藏字段
values [8]valuetype // value数组，隐藏字段
overflow uintptr // 溢出buceket指针，隐藏字段
}
（二）创建
// 初始化一个可容纳 10 个元素的map，但不是桶的数量
info = make(map[string]string,10)
底层调用 makemap
● 校验
● 创建一个hmap结构体对象
● 生成一个哈希因子hash0 并赋值到hmap对象中（用于后续为key创建哈希值）
● 根据 hint=10，并根据算法规则来创建 B，当前 B 应该为 1
- hint B
- 0~8 0
- 9~13 1
- 14~26 2
- ...
● 第四步：根据B去创建去创建桶（bmap对象）并存放在buckets数组中，当前bmap的数量应为2. - 当B<4时，根据B创建桶的个数的规则为：2^B（标准桶）
- 当B>=4时，根据B创建桶的个数的规则为：2^B + 2^{B-4}（标准桶+溢出桶）
注意：每个bmap中可以存储8个键值对，当不够存储时需要使用溢出桶，并将当前bmap中的overflow字段指向溢出桶的位置。
// hint 也就是创建 map 时指定的容量，根据 hint 计算出 B，然后创建 2^B 个桶
func makemap(t *maptype, hint int, h *hmap) *hmap {
-------------------- 内存溢出校验 --------------------
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
if overflow || mem > maxAlloc {
hint = 0
}
-------------------- 初始化一个hmap，如果h为nil则重新初始化 --------------------
if h == nil {
h = new(hmap)
}
-------------------- 生成哈希种子 --------------------
h.hash0 = fastrand()
-------------------- 根据 hint 初始化B的大小 --------------------
B := uint8(0)
for overLoadFactor(hint, B) {
B++
}
h.B = B
-------------------- 根据 B 创建 bmap 和 溢出桶 nextOverflow --------------------
if h.B != 0 {
var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
（三）新增
var info=make(map[string]string)
info["name"] = "xj"
底层调用 mapassign
● 校验
● 根据哈希因子 hash0 计算 key 的哈希值； 如计算 name 哈希结果：011011100011111110111011011
● 根据一定条件判断是否进行 扩容 、迁移 操作，也就是 rehash
● 根据哈希值的后 B 位的值来决定将此键值对存放到那个桶中（bmap），实际上计算出来的是 buckets 的下标：
将哈希值和桶掩码（B个为1的二进制）进行 & 运算，最终得到哈希值的后B位的值。假设当B为1时，其结果为 0 ：
哈希值：011011100011111110111011010
桶掩码：000000000000000000000000001
结果： 000000000000000000000000000 = 0
通过示例你会发现，找桶的原则实际上是根据后B为的位运算计算出 索引位置，然后再去buckets数组中根据索引找到目标桶（bmap)
● 确定 bmap 之后，将 tophash、key、value分别写入到桶中的三个数组中，后续会根据 tophash 比较相同则再去比较key
● 如果桶已满，则通过 overflow 找到溢出桶，并在溢出桶中继续写入
● hmap的个数count++（map中的元素个数+1）
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
-------------------- 校验 --------------------
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
if h.flags&hashWriting != 0 { // 并发读写
fatal("concurrent map writes")
}
-------------------- 计算 hash 值 --------------------
hash := t.hasher(key, uintptr(h.hash0))
h.flags ^= hashWriting // 标记为正在写
again:
bucket := hash & bucketMask(h.B)
-------------------- 根据一定条件判断是否需要扩容 --------------------
if h.growing() {
growWork(t, h, bucket)
}
-------- 根据哈希值的后 B 位的值对应 buckets 数组的下标，然后将 tophash、key、value 写入 bmap 中 ---------
-------- 如果桶已满，则通过 overflow 找到溢出桶，并在溢出桶中继续写入 --------
................
-------------------- hmap的个数count++ --------------------
h.count++
return elem
}
（四）查询
var name=info["name"]
● 校验
● 根据哈希因子 hash0 计算 key 的哈希值； 如计算 name 哈希结果：011011100011111110111011011
● 根据哈希值的后 B 位的值来决定将此键值对存放到那个桶中（bmap），实际上计算出来的是 buckets 的下标
● 确定 bmap 后，再根据 key 的哈希值计算 出tophash（高 8 位），快速比较 tophash 确定元素下标，然后再去 key 和 value 中 获取元素
● 当前桶如果没找到，则根据 overflow 再去溢出桶中找，均未找到则表示 key 不存在
（五）扩容
在向 map 中添加数据时，当达到某个条件，则会引发 map 扩容，调用 h.growing() 判断，执行 growWork() 扩容：
● 翻倍扩容：map中数据总个数 / 桶个数 > 6.5
● 等量扩容：使用了太多的溢出桶时（溢出桶使用的太多会导致map处理速度降低）
- B <=15，已使用的溢出桶个数 >= 2^B 时，引发等量扩容
- B > 15，已使用的溢出桶个数 >= 2^{15} 时，引发等量扩容
func hashGrow(t *maptype, h *hmap) {
// If we've hit the load factor, get bigger.
// Otherwise, there are too many overflow buckets,
// so keep the same number of buckets and "grow" laterally.
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow
}
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
...
}
扩容后：
● B会根据扩容后新桶的个数进行增加（翻倍扩容新B=旧B+1，等量扩容 新B=旧B）
● oldbuckets指向原来的桶（旧桶）
● buckets指向新创建的桶（新桶中暂时还没有数据）
● nevacuate设置为0，表示如果数据迁移的话，应该从原桶（旧桶）中的第0个位置开始迁移
● noverflow设置为0，扩容后新桶中已使用的溢出桶为0
● extra.oldoverflow设置为原桶（旧桶）已使用的所有溢出桶。即：h.extra.oldoverflow = h.extra.overflow
● extra.overflow设置为nil，因为新桶中还未使用溢出桶
● extra.nextOverflow设置为新创建的桶中的第一个溢出桶的位置。
image.png
（六）迁移 rehash
增量式 rehash 的策略：
● 将新数组的容量设置为旧数组的两倍或一半，并且将哈希表的增量计数器加一
● 在对哈希表进行操作时，如果发现增量计数器的值达到了一个阈值，就会开始进行增量式 rehash 操作，将一部分元素从旧数组中复制到新数组中，并且重新计算这些元素的哈希值
● 在完成一次增量式 rehash 操作后，会将哈希表的增量计数器清零。
通过增量式 rehash 的策略，Go 标准库中的哈希表实现可以在保证较短的 rehash 时间的同时，避免一次性处理过多元素导致性能下降。
rehash 操作会创建一个新的哈希表，同时保留旧的哈希表不变。然后，它会依次遍历旧哈希表中的每个桶，将桶中的所有键值对复制到新哈希表中对应的桶中。在遍历每个桶时，如果桶中的元素已经被删除，则跳过这些元素。
当遍历到一个桶时，Map 实现会首先获取旧哈希表中该桶的互斥锁，以确保在复制元素时不会有并发访问的问题。然后，它会遍历桶中的所有键值对，对于每个键值对，它会计算键在新哈希表中的位置，并将键值对插入到对应的桶中。插入过程中，如果新哈希表中对应的桶已经存在元素，则会将新元素插入到该桶的链表的尾部。
在整个 rehash 过程中，新哈希表会保持为空，直到所有元素都被复制完毕。复制完成后，Map 实现会用新哈希表替换旧哈希表，并释放旧哈希表占用的内存空间。这样，Map 中的所有元素都被迁移到了新哈希表中。
翻倍扩容
如果是翻倍扩容，那么迁移规就是将旧桶中的数据分流至新的两个桶中（比例不定），并且桶编号的位置为：同编号位置 和 翻倍后对应编号位置。
等量扩容
如果是等量扩容（溢出桶太多引发的扩容），那么数据迁移机制就会比较简单，就是将旧桶（含溢出桶）中的值迁移到新桶中。
这种扩容和迁移的意义在于：当溢出桶比较多而每个桶中的数据又不多时，可以通过等量扩容和迁移让数据更紧凑，从而减少溢出桶
三、常见问题
1.bmap 的数量为什么是 2^B 次方？
方便位运算，bitmap
2.为什么要进行等量扩容？
让元素更加紧凑，刚好利用内存，比如 map 中有 1000 个 元素，但是可能存在一些删除的元素，应该将溢出桶的元素迁移到删除的元素的位置
3.bmap 中的 tophash 是什么有什么作用？
tophash 是 key 哈希值的高八位，主要用来快速比较两个键是否相同
比如现在 插入 key name ，则在确定桶之后， 获取 name 的哈希值的高八位和 bmap 中的 tophash 快速判断比较 key 是否存在，存在的下标
从而到 key 和 value 数组中根据下标获取数据，
不直接比较 key 是因为 key 可能会很大，tophash 比较会快速很多
4.map 的 value 为什么不可寻址？
key 通过 hash 算出具体的 bucket，然后将 key 和 value 复制 到 bucket，不是指针引用，所以不可寻址，
如果用指针寻址的话，在扩容迁移时， map 进行了扩容或者重新分配内存，原来的指针地址无效，发送程序错误，因此设计为不可寻址
5.map 是如何解决哈希冲突的？
哈希冲突碰撞：多个 key 的 hash 结果一致，hash 到同一个 bucket，解决方法：
● 链表法： 将一个 bucket 实现成一个链表，落在同一个 bucket 中的 key 都会插入这个链表
● 开放寻址法： 则是碰撞发生后，通过一定的规律，在数组的后面挑选“空位”，用来放置新的 key
go map 采用的是 链表法，使用 溢出桶 来存放 相同 hash 结果的 value
6.为什么 map 是无序的？
● hash 结果本身就是无序的
● map 扩容之后，key 会发生迁移
● map底层在遍历的时候也是无序遍历的，并不是从第一个桶开始依次遍历
7.map 使用时需要注意哪些问题？
● key 必须是可比较的类型，如整数、字符串和指针等，但是切片、函数和结构体等类型是不可比较的，因此不能用作键
● Map 中的元素是无序的
● 如果使用未初始化的 Map，会导致运行时错误。需要使用 make() 函数来初始化 Map。
● Map 在并发环境下不是安全的
8.map 是如何进行扩容的？
● 当 Map 中的元素数量超过了负载因子（load factor）和哈希表容量的乘积时，map 就会触发扩容操作。在 Go 中，负载因子默认为 6.5。
● Go Map 在扩容时会创建一个新的哈希表，一次性（非渐进式）将原来的键值对重新散列到新的哈希表中。为了减少哈希冲突，新哈希表的容量是原来的两倍，并且容量一定是 2 的幂次方。
● 在重新散列过程中，Go Map 会根据哈希值将原来的键值对分配到新哈希表中的对应位置上。如果两个键值对的哈希值相同，会使用链式哈希表（chained hash table）的方式进行处理，将它们放在同一个桶（bucket）中。
● 一旦所有的键值对都已经重新散列到新的哈希表中，Go Map 就会将原来的哈希表释放掉，将新的哈希表作为 Map 的内部存储结构。
注意： 由于扩容操作可能会导致大量的重新散列操作，因此在扩容时可能会造成一定的性能影响。为了避免频繁扩容，可以在创建 Map 时指定一个较大的容量，或者手动调用 runtime.GC() 来触发垃圾回收操作，以释放未使用的内存。
9.map 的 panic 能被 recover 吗？
● 不能，直接抛出 throw("concurrent map read and map write")
10.并发使用 map 除了加锁还有其他方案吗？
多读少写的情况，建议使用 sync.Map
11.sync.Map 和加锁有什么区别？
● 不需要显式的加锁/解锁
● 降低锁的粒度，适用 多读少写 场景，读是原子操作，不需要加锁
12.Map 的查询时间复杂度？
正常情况下是 O (1)，极端情况下，也就是哈希冲突碰撞严重情况下：O (N)，需要遍历溢出桶
13.Map Rehash 的策略是怎样的？什么时机会发生 Rehash？
rehash 也就是 扩容、迁移；在 map 元素达到一定条件的情况下，发生扩容操作：
image.png
rehash 的策略：增量式 rehash，在新增 key 的情况下逐步将 oldbuckets 元素迁移到 buckets
14.Map rehash 具体会影响什么？哈希结果会受到什么影响？
只会影响 key 在 map 中的存储位置，不会改变哈希结果
15.Map Rehash 过程中存放在旧桶的元素如何迁移？
在 新增 key 时 逐步增量迁移
参考资料
Go Map 的 11 连问，你顶得了嘛? - 掘金 (juejin.cn)
