map 是如何扩容的？

提示

题眼： 扩容时机和迁移策略

渐进式迁移是哈希结构扩容时非常常见的一种思路。

map 的底层是哈希表。扩容一般会在两种情况下触发：装载因子超过阈值，或者溢出桶过多。

扩容规则大致分成两类：

1. 等量扩容：当溢出桶过多时，申请同样数量的新桶，把旧数据重新整理后搬过去。它更像一次内存整理，目的是提升查询效率。
2. 增量扩容：当元素数量增长较多时，会分配更多的新桶，通常是原来的两倍，然后把旧桶中的数据渐进式迁移到新桶中。

渐进式迁移主要有两个特点：

1. 扩容不会一次性把所有数据全部搬完，而是把迁移成本分摊到后续的读写操作中。
2. 当程序继续操作 map 时，运行时会顺带推进一部分桶迁移，直到整个扩容过程完成。

重要

参考答案：
map 扩容的核心点有两个：什么时候扩，扩了以后怎么搬。
先说时机。常见触发条件主要是两个：一个是装载因子太高，另一个是溢出桶太多。前者说明元素太密了，后者说明虽然元素不一定很多，但哈希冲突已经把查询效率拖下来了。
再说策略。Go 的 map 扩容并不是一次性把所有元素全部搬过去，而是采用渐进式迁移。扩容开始后，底层会同时保留新旧两套桶结构，后续每次对 map 做读写操作时，运行时都会顺带搬一部分数据。
这样做的好处是不会把一次扩容的成本全集中到某一个时刻，而是把它分摊到后续操作里，避免单次操作卡顿太明显。面试时把“等量扩容、增量扩容、渐进式迁移”这三个关键词答出来，基本就够了。