字节一面, Go语言的Map 的扩容机制是怎样的？

在 Go 语言中，map 是一种内置的数据结构，用于存储键值对。它基于哈希表实现，具有高效的查找、插入和删除操作。当 map 中的元素数量不断增加时，为了保证操作的高效性，Go 语言的 map 会触发扩容机制。以下是关于 Go 语言 map 扩容机制的简单介绍

一、扩容触发条件

Go 语言的 map 使用哈希表来存储键值对，哈希表的性能依赖于负载因子（load factor），即哈希表中已存储的元素数量与哈希表桶（bucket）数量的比值。当负载因子超过一定阈值时，map 会触发扩容操作， 扩容主要有两种触发机制

1. 当 map 的键值对数量达到桶数量的 6.5 倍时，会触发扩容。
2. overflow 中的 bucket 数量过多,

• 当 B < 15 的时候, 如果 overflow 中的 bucket 超过$2^{15}$的时候, 那么就会发生扩容,
• 当 B > 15 的时候, 如果 overflow 中的 bucket 超过$2^{15}$ 的时候, 那么就会扩容

loadFactor := count / (2 ^ B)

tooManyOverflowBuckets 表示当前这个map 中存在比较多的overflow buckets

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	if B > 15 {
		B = 15
	}
	return noverflow >= uint16(1)<<(B&15)
}

二、 扩容过程

2.1 扩容原因

我们首先简单的分析一下造成这两种问题出现的原因是什么?

首先第一种情况出现的原因就是因为每个bucket 都有8 个空位, 在没有溢出, 而且所有的桶都装满的情况下, 装载因子算出来的结果是8，因此当装载因子超过6.5 的时候，表明很多 bucket 都快要装满了, 这样导致的结果就是查找删除的效率变得很低。

扩容的第二点是和overflow 有关， 当装载因子比较小的时候, 但是这个时候 map 的操作速率也比较低，导致出现这种问题的原因是因为 count 的数量比较少。造成这种原因是因为: 不断的插入元素, 导致创建了很多个 bucket, 但是并没有达到第一种的扩容条件, 之后又因为大量的删除, 导致count减小, 然后再次频繁的插入, 正是因为这样导致出现很多的overflow

分析完成这两种症结出现的原因, 下面就是对应的解决办法:

对于条件1, 就是因为出现的元素比较多, 但是bucket 的数量不多: 所以我们的做法是增大对应的bucket 数量，对应的也就是$B+1$。

对于条件2, 其实元素并没有那么多, 但是 overflow bucket数量比较多, 说明很多的bucket 都没有装满, 解决的办法就是开辟一个新的 bucket, 把老的bucket 元素移动到新的 bucket 中, 这样原来在overflow 中的元素都在新的bucket 中排列紧密了。

2.2 扩容机制：

再来看一下扩容具体是怎么做的。由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果有大量的 key/value 需要搬迁，会非常影响性能。因此 Go map 的扩容采取了一种称为“渐进式”，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。

最初的扩容位置是在hashGrow() 这个函数中, 但是这个函数也只是分配新的内存并没有进行搬迁，真正的搬迁过程是发生在growwork() 这个函数中。

func hashGrow(t *maptype, h *hmap);

下面我们可以一下这个函数的具体操作，

bigger := uint8(1) 
// 如果没有超过对应的负载
if !overLoadFactor(h.count+1, h.B) {
	// 表示等 size 进行扩容2
	bigger = 0
	h.flags |= sameSizeGrow
}

// 初始化一个新的 buckets
oldbuckets := h.buckets

//h.B + 1, newbuckets 变成2^b * 2
//h.b + 0, newbuckets 变成 2^b, 也就是数量不变
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

然后就是一堆搬迁flags 标志位, 挂载oldbuckets的操作:

// 初始化 buckets 的 flags 位
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
	flags |= oldIterator
}

// ---初始化---
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
h.nevacuate = 0
h.noverflow = 0

下面我们看一下对应的搬迁操作, 真正的搬迁操作发生在growwork 这个函数中:

func growWork(t *maptype, h *hmap, bucket uintptr) { 
	evacuate(t, h, bucket&h.oldbucketmask())
	if h.growing() {
		evacuate(t, h, h.nevacuate) 
	}
}

bucket&h.oldbucketmask()这一表达式的作用是确定当前待搬迁的新bucket对应的旧bucket编号。
比如，假设现在正在处理某个bucket，比如在扩容的时候，可能原来的bucket数目是$2^5$, 现$2^6=64$个。这时候，搬迁的时候需要把旧的bucket（比如编号为3）的数据搬迁到新的两个bucket中，可能是3和3+32=35的位置？这时候，如果当前的bucket是35，那么和旧的mask（0x1F）相与的话，得到的是3。

下面我们来看一下关于evacuate 这个函数, 它的源码如下:

// 定位到老的bucket 地址
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
newbit := h.noldbuckets()

然后是判断老的bucket 是否被搬迁过, 如果没有搬迁过, 我们就直接进行搬迁,

if !evacuate(b) {
	var xy [2]evacDst
	x := &xy[0] //计算bucket 搬迁的目标地址
	x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize)))
	x.k = add(unsafe.Pointer(x.b), dataOffset)
	x.e = add(x.k, abi.MapBucketCount*uintptr(t.KeySize))
}

因为搬迁有两种方式, 第一种方式是等量扩容, 对应着扩容条件2, 也就是size 不变, 旧 bucket i 的数据会被迁移到新 bucket i，但需要 合并溢出桶，对应上面的代码也就是使用x 来完成这个过程。

对于扩容条件2, 因为并不是等量进行扩容，所以我们需要使用$x+y$来进行扩容,

// 如果不是等量扩容还需要使用对应的y
if !h.sameSizeGrow() {
	y := &xy[1]
	y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize)))
	y.k = add(unsafe.Pointer(y.b), dataOffset)
	y.e = add(y.k, abi.MapBucketCount*uintptr(t.KeySize))
}

因为这种情况下size 改变了, 所以我们需要 rehash，比如原来我们需要看后面5 位，在迁移之后我们可能需要去关注它的后6位。同时这种情况可能会导致出现迁移之后的位置是相同的, 这通常取决于B位是0还是1

介绍完上面两点, 我么接着源码往下看, 依然是比较熟悉的两层循环遍历map 中的元素:

// 遍历当前 bucket b 及其所有溢出桶（overflow buckets）
for ; b != nil; b = b.overflow(t) {
	// k：指向 bucket 内第一个键（key）的起始地址。
	// e：指向 bucket 内第一个值（value）的起始地址。
	k := add(unsafe.Pointer(b), dataOffset)
	e := add(k, abi.MapBucketCount*uintptr(t.KeySize))
	// 每个 bucket 可容纳的键值对数量（默认为 8）。
	for i := 0; i < abi.MapBucketCount; 
		i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) {
}

然后取出对应的 top hash

// 首先取出对应的 top hash 值
top := b.tophash[i]
if isEmpty(top) { // 如果是null, 表示更新过
	b.tophash[i] = evacuatedEmpty
	continue
}

源码里有一个 bool 型变量，useY，其实代表的是落入 X, Y part 的哪个 part。前面说过，如 果是扩容后 B 增加了 1，那么桶的数量是原来的 2 倍。前一半桶被称为 X part，后一半桶被称为 Y part。

var useY uint8
if !h.sameSizeGrow() {
    // 计算哈希值以决定迁移策略（是否需要将此键/值对发送到桶 x 或桶 y）。
    hash := t.Hasher(k2, uintptr(h.hash0))
    // 如果存在协程正在遍历map
    // 并且如果出现相同的 key 值，算出来的 hash 值不同
    if h.flags&iterator != 0 && !t.ReflexiveKey() && !t.Key.Equal(k2, k2) {
        // 这种情况由 useY 和 它对应的hash
        useY = top & 1
        top = tophash(hash)
    } else { // 一般情况下
    	// 取决于新的hash 值oldb+1 位置是0 还是1
        if hash&newbit != 0 {
            useY = 1 //为1
        }
    }
}

一个 bucket 中的 key 可能会分裂到两个桶，一个位于 X part，一个位于 Y part。所以在 搬迁一个 cell 之前，需要知道这个 cell 中的每个 key 具体落到哪个 part。当然也很简单，重新计算 cell 中 key 的 hash，并向前“多看”一位，再决定落入哪个 part，这个前面也说得很详细了。

 if hash&newbit != 0 {
      useY = 1 //为1
 }

但是有一种 key，每次对它计算 hash，得到的结果都不一样。这个 key 就是 $math.NaN()$ 的结果，它的含义是 not a number，类型是 float64。当它作为 map 的 key，在搬迁的 时候，会遇到一个问题: 再次计算它的哈希值和它当初插入 map 时的计算出来的哈希值不一样。

这样带来的一个后果是，这个 key 是永远不会被 Get 操作获取到的。当使 用 m[math.NaN()] 语句的时候，是查不出来结果的。这个 key 只有在遍历整个 map 的时候，才有 机会“现身”。所以，可以向一个 map 插入任意数量的 math.NaN() 作为 key。

对于这个问题, 采用的方式是, 使用它的 tophash 的低位值, 来判断，判断它的低位值是0还是1。

useY = top & 1
top = tophash(hash)

下面我们就来看一下它的具体搬迁过程:

1. 将源 key/value 值复制到目的地相应的位置。
2. 设置 key 在原始 buckets 的 tophash 为 evacuatedX 或是 evacuatedY，表示已经搬迁到
   了新 map 的 xpart 或是 ypart。
3. 新 map 的 tophash 取 key 哈希值的高 8 位。

b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
dst := &xy[useY]                 // evacuation destination

根据 useY 的值（0 或 1），将 tophash 更新为 evacuatedX 或 evacuatedY，标记该槽已被迁移。
dst 是迁移的目标桶，xy[useY] 是一个结构体，包含目标桶的指针、当前槽索引等信息。

然后就是一些条件判断:

if dst.i == abi.MapBucketCount {
    dst.b = h.newoverflow(t, dst.b)
    dst.i = 0
    dst.k = add(unsafe.Pointer(dst.b), dataOffset)
    dst.e = add(dst.k, abi.MapBucketCount*uintptr(t.KeySize))
}

• 如果目标桶的当前槽索引 dst.i 等于 abi.MapBucketCount（即桶已满），则需要创建一个新的溢出桶。
• h.newoverflow(t, dst.b) 创建一个新的溢出桶，并将其链接到目标桶。
• 重置 dst.i 为 0，表示从新桶的第一个槽开始写入。
• 更新 dst.k 和 dst.e，分别指向新桶的键和值的起始位置。

最终写入对应的值:

typedmemmove(t.Key, dst.k, k)
typedmemmove(t.Elem, dst.e, e)

如果没有协程在使用老的 buckets，就把老 buckets 清除掉，帮助 GC

memclrHasPointers(ptr, n)