map的底层是采用哈希表来实现的。

数据结构

底层使用一个数组，数组中的每个位置叫做桶，数组的长度叫做桶的数量。每个键值对要放到一个桶当中。其数据结构为runtime/map.go/hamp

type hmap struct {
	count int // 当前键值对的个数
	B uint8 //bucket数组的大小
	buckets unsafe.Pointer //bucket数组指针，数组的大小为2^B
	....
}

buckets指向的桶数组中，每个桶的定义如下：

type bmap struct {
	tophash [8]uint8 //哈希值的高8位
	data byte[1]
	overflow *bmap //溢出的bucket地址
}

tophash存放哈希值的高8位，可以存储8个，所以一个bmap可以存储8个键值对，当超过8个之后，就需要通过overflow以形如链表的方式组织起来。

从图中可以看到，bucket中键值对是以先存储键，再存储值的方式进行存储的，这样可以节省字节对齐带来的空间浪费。

扩容

使用负载因为来衡量哈希表的冲突情况

负载因子 = 键数量 / bucket数量

Go在负载因子达到6.5的时候才会触发扩容，因为GO的每个bucket可以存8个键值度，所以容忍的负载因子要更高一些。

扩容的过程与redis的类似，都是渐进式扩容。不过这也分两步，增量扩容和等量扩容。

负载因子过大的时候，就新建一个bucket，新的bucket的长度为原来的二倍。将旧的键值对搬移到新的buckets中，不过这个搬移的过程不是一下子就完成的，而是在每次访问map的时候触发一次搬移，每次搬移两个键值对，直到旧的bucket中的键值对搬移结束，扩容结束。

扩容的时候会让buckets指向新申请的更大的bucket，而让oldbuckets指向旧的buckets，搬移结束后oldbuckets删除。

等量扩容是因为可能存在键值对过于集中在某个桶中（大量增删操作后，剩余的键集中在一个桶上），overflow的bucket数量增多，但负载因子又不高，从而无法执行增量搬移的极端情况。这种情况下访问的效率会非常差，所以需要进行一次等量扩容，将键值对分散开来，既节省空间又提高了访问效率。