【Golang 面试题】每日 3 题（十五）

✍个人博客：Pandaconda-CSDN博客
📣专栏地址：http://t.csdnimg.cn/UWz06
📚专栏简介：在这个专栏中，我将会分享 Golang 面试中常见的面试题给大家~
❤️如果有收获的话，欢迎点赞👍收藏📁，您的支持就是我创作的最大动力💪

43. Go Map 的扩容条件

1. 条件 1：超过负载

• map 元素个数 > 6.5 * 桶个数

func overLoadFactor(count int, B uint8) bool {return count > bucketCnt && uintptr(count) > loadFactor*bucketShift(B)
}

其中
bucketCnt = 8，一个桶可以装的最大元素个数
loadFactor = 6.5，负载因子，平均每个桶的元素个数
bucketShift(B): 桶的个数

2. 条件 2：溢出桶太多

• 当桶总数 < 2 ^ 15 时，如果溢出桶总数 >= 桶总数，则认为溢出桶过多。
• 当桶总数 >= 2 ^ 15 时，直接与 2 ^ 15 比较，当溢出桶总数 >= 2 ^ 15 时，即认为溢出桶太多了。

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {// If the threshold is too low, we do extraneous work.// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.// "too many" means (approximately) as many overflow buckets as regular buckets.// See incrnoverflow for more details.if B > 15 {B = 15}// The compiler does not see here that B < 16; mask B to generate shorter shift code.return noverflow >= uint16(1)<<(B&15)
}

对于条件 2，其实算是对条件 1 的补充。因为在负载因子比较小的情况下，有可能 map 的查找和插入效率也很低，而第 1 点识别不出来这种情况。

表面现象就是负载因子比较小比较小，即 map 里元素总数少，但是桶数量多（真实分配的桶数量多，包括大量的溢出桶）。比如不断的增删，这样会造成 overflow 的 bucket 数量增多，但负载因子又不高，达不到第 1 点的临界值，就不能触发扩容来缓解这种情况。这样会造成桶的使用率不高，值存储得比较稀疏，查找插入效率会变得非常低，因此有了第 2 扩容条件。

44. Go Map 的扩容机制

• 双倍扩容：针对条件 1，新建一个 buckets 数组，新的 buckets 大小是原来的 2 倍，然后旧 buckets 数据搬迁到新的 buckets。该方法我们称之为双倍扩容.
• 等量扩容：针对条件 2，并不扩大容量，buckets 数量维持不变，重新做一遍类似双倍扩容的搬迁动作，把松散的键值对重新排列一次，使得同一个 bucket 中的 key 排列地更紧密，节省空间，提高 bucket 利用率，进而保证更快的存取。该方法我们称之为等量扩容。

45. Go Map 的扩容函数：

上面说的 hashGrow() 函数实际上并没有真正地 “搬迁”，它只是分配好了新的 buckets，并将老的 buckets 挂到了 oldbuckets 字段上。真正搬迁 buckets 的动作在 growWork() 函数中，而调用 growWork() 函数的动作是在 mapassign 和 mapdelete 函数中。也就是插入或修改、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。先检查 oldbuckets 是否搬迁完毕，具体来说就是检查 oldbuckets 是否为 nil。

func hashGrow(t *maptype, h *hmap) {// 如果达到条件 1，那么将B值加1，相当于是原来的2倍// 否则对应条件 2，进行等量扩容，所以 B 不变bigger := uint8(1)if !overLoadFactor(h.count+1, h.B) {bigger = 0h.flags |= sameSizeGrow}// 记录老的bucketsoldbuckets := h.buckets// 申请新的buckets空间newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)// 注意&^ 运算符，这块代码的逻辑是转移标志位flags := h.flags &^ (iterator | oldIterator)if h.flags&iterator != 0 {flags |= oldIterator}// 提交grow (atomic wrt gc)h.B += biggerh.flags = flagsh.oldbuckets = oldbucketsh.buckets = newbuckets// 搬迁进度为0h.nevacuate = 0// overflow buckets 数为0h.noverflow = 0// 如果发现hmap是通过extra字段 来存储 overflow buckets时if h.extra != nil && h.extra.overflow != nil {if h.extra.oldoverflow != nil {throw("oldoverflow is not nil")}h.extra.oldoverflow = h.extra.overflowh.extra.overflow = nil}if nextOverflow != nil {if h.extra == nil {h.extra = new(mapextra)}h.extra.nextOverflow = nextOverflow}
}

由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果 map 存储了数以亿计的 key-value，一次性搬迁将会造成比较大的延时，因此 Go map 的扩容采取了一种称为 “渐进式” 的方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。

func growWork(t *maptype, h *hmap, bucket uintptr) {// 为了确认搬迁的 bucket 是我们正在使用的 bucket// 即如果当前key映射到老的bucket1，那么就搬迁该bucket1。evacuate(t, h, bucket&h.oldbucketmask())// 如果还未完成扩容工作，则再搬迁一个bucket。if h.growing() {evacuate(t, h, h.nevacuate)}
}

需要注意的是，在 Map 进行扩容时，可能会导致哈希冲突的数量增加，因此扩容后的 Map 的性能可能会有所下降。为了避免这种情况，可以考虑在创建 Map 时指定初始容量，以减少扩容的次数。