golang map扩容机制

map的扩容是在给map赋值和删除的时候完成的，具体源码是在runtime/map.go文件里面，这里默认看官了解了map的结构，如果看官不了解的话，推荐左大的《go语言设计与实现》一书中map章节可以使用GoLand，按两次shift键，输入要查找的函数名，或者结构体名，就可以跳转到对应的源码位置，这里以map赋值函数map_assign为例，注意是runtime/map.go

何时触发扩容？

在赋值过程中，会判断是否需要扩容，主要有两个函数：overLoadFactory和tooManyOverflowBuckets（如下图所示）overLoadFactory用于判断负载因子是否超过了6.5，代码如下所示，如中的bucketCnt，loadFactorNum，loadFactorDen均为常数，其值分别为8，13，2tooManyOverflowBuckets用于判断是否有太多的溢出桶，代码如下，当B<=15时，溢出桶的数量不能超过正常桶的数量，当B>15时，溢出桶的数量不能超过2^15个小结一下：map扩容有两种情况，一种是map的负载因子超过了6.5，一种是溢出桶太多了

如何扩容？

扩容需要处理的问题是，扩容后，map中原本的数据重新放到扩容后的map中，即数据迁移问题，golang中map扩容时核心函数有如下几个

1. hashGrow：负责初始化新的桶，以及设置扩容后的map的各个字段
2. growWork：每调用一次growWork函数，都至多会迁移两个桶的数据
3. evacuate：真正负责迁移数据的函数，会负责迁移指定桶中的数据
4. advanceEvacuationMark：收尾工作，增加nevacuate，如果所有的oldbuckets都迁移完成了，会摘除oldbuckets

hashGrow

golang的map数据迁移是渐进式的迁移，不是一次性的，在判断需要扩容之后，会调用hashGrow函数，hashGrow函数并没有做实际的迁移操作，它只是根据扩容类型创建新的桶，并将原来的桶挂载在map的指定位置，设置了hmap的各个字段，经过hashGrow函数处理后，新的hmap结构如下所示真正迁移数据的操作会散布在后续的map修改操作中，即mapassign和mapdelete函数，在两个函数中都会有下列的代码片段，会判断当前map是否处在扩容阶段，如果是，则会调用growWork函数进行数据迁移

growWork

growWork函数并不会真正进行数据迁移，它会调用evacuate函数来完成迁移工作，growWork函数每次会迁移至多两个桶的数据，一个是目前需要使用的桶，一个是h.nevacuate桶（这里很重要，在后面判断是否迁移过程中有很大的作用），h.nevacuate记录的是目前迁移的桶的个数（这个说法并不准确，h.nevacute是滞后的，即有可能会出现当前迁移了x个桶，但是h.nevacute却少于x的情况，后面会讨论），growWork中会将需要迁移的桶下标与旧桶数量做与运算，保证只会迁移旧桶的数据

evacuate

在讨论evacuate前，先讨论bmap.tophash的几个特殊值，在扩容过程中会使用到。tophash中会有以下几个特殊值，其中evacuateX，evacuateY，evacuateEmpty就是与扩容相关的几个特殊值

emptyRest      = 0 // 表明该位置及其以后的位置都没有数据
emptyOne       = 1 // 表明该位置没有数据
evacuatedX     = 2 // key/elem是有效的，它已经在扩容过程中被迁移到了更大表的前半部分
evacuatedY     = 3 // key/elem是有效的，它已经在扩容过程中被迁移到了更大表的后半部分
evacuatedEmpty = 4 // 该位置没有数据，且已被扩容
minTopHash     = 5 // 一个被正常填充的tophash的最小值

evacuate是真正进行数据迁移的函数，它每次会迁移一个bmap中的数据，简单说，就是遍历旧有buckets中bmap中的数据，将其放到新bmap的对应位置即可，下面讲讲详细的过程

1. 首先会判断这个桶是否已经被迁移过了，或者正在迁移中，如果没有被迁移，才会进行迁移工作。该判断是通过evacuated函数完成的，该函数很简单，只需要判断tophash[0]是否是evacuatedX，evacuatedY，evacuateEmpty即可

1. 初始化evacDst结构，如果是等量扩容，则只会初始化一个，如果是普通扩容，则会初始化两个，一个是前半部分，一个是后半部分。evacDst结构体如下所示

type evacDst struct {
	b *bmap          // 目标桶
	i int            // 每个桶有8个位置可以塞数据，这个i可以理解为当前塞了多少个数据
	k unsafe.Pointer // 目标桶中key的位置
	e unsafe.Pointer // 目标桶中elem的位置
}

1. 接下来就是遍历oldbuckets中bmap的数据，计算hash值，判断是放在buckets的哪个bmap中，然后迁移数据，同时还会修改旧bmap中的tophash值，如果没有goroutine在遍历oldbuckets，还会直接将旧bmap的数据清空

下面看一个大概的扩容例子，oldbuckets中bmap0有三个有效数据，tophash3，tophash4，tophash5，经过迁移后tophash3和tophash4被迁入到前半部分（evacutedX），tophash5被迁入到后半部分（evacuatedY）

advanceEvacuationMark

advanceEvacuationMark函数的作用即循环判断桶是否被迁移，然后增加h.nevacuate值，当h.evacuate等于newbit时，表明迁移已经完成了，newbit就是oldbuckets中bmap的数量，此时将oldbuckets摘除

nevacuate

前面提到过nevacuate会有滞后性，下面来看看相关的代码。在迁移完bmap后，通过判断此次迁移的oldbucket是否等于nevacuate，然后调用advanceEvacuationMark函数

可以看到上面的判断，当目前清理的bucket下标等于h.nevacuate时，才会调用advanceEvacuationMark函数来增加nevacuate的值，这里演示一个场景，初始情况有8个桶待迁移，h.nevacuate为0，每调用一次growWork，会至多迁移两个桶，假设第一次迁移时，迁移7号桶，第二次迁移时迁移5号桶，以下时迁移的情况，迁移过的桶用-1表示。所以在advanceEvacuationMark函数中会遍历桶的情况，如果已经迁移过了会增加h.nevacuate