#### go map 底层结构 ####
转自 图解golang map 底层实现 - 掘金
仅做个人备份
目录
#### 整体结构 ####
整体结构的剖析——主要结构:hmap、bucket
key的定位
扩容
#### 整体结构 ####
整体结构的剖析——主要结构:hmap、bucket
（1）hmap
其中标红的【buckets数组(即bmap)】字段为主要字段。
（2）bucket
主要有俩字段：
（1）红色的字节数组，存储map中的key和value，详细结构如下：
并不是key0/value0/key1/value1的形式，这样做的好处是在key和value的长度不同的时候，可以消除padding带来的空间浪费。
（2）蓝色的扩容指针，指向扩容后的bucket的指针，使得bucket会形成一个链表结构，例如下图：
所以，hmap和bucket的关系是这样的：
所以，整体的结构应该是这样的：
key的定位
根据key算出hash值，然后hash值的低位用于寻找当前key属于hmap中的哪个bucket，而hash值的高位用于寻找bucket中的哪个key。
扩容
当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中。注意并不是立刻把旧的数组中的元素转义到新的bucket当中，而是只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中。
【加载因子】
加载因子是一个阈值，表示散列包含的元素数 除以 位置总数。是一种“产生冲突机会”和“空间使用”的平衡与折中。
加载因子越小，说明空间空置率高，空间使用率小，但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了。每种哈希表的都会有一个
加载因子，数值超过加载因子就会为哈希表扩容。 Golang的map的加载因子的公式是：map长度 / 2^B阈值是6.5。其中B可以理解为已扩容的次数。
如下图所示，当扩容的时候，Go的map结构体中，会保存旧的数据，和新生成的数组。
上面部分代表旧的有数据的bucket，下面部分代表新生成的新的bucket。蓝色代表存有数据的bucket，橘黄色代表空的bucket。 扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候，才把旧数据做迁移，如下图：
注意：这里并不会直接删除旧的bucket，而是把原来的引用去掉，利用GC清除内存。