golang map扩容

golang map 操作，是map 实现中较复杂的逻辑。因为当赋值时，为了减少hash 冲突链的长度过长问题，会做map 的扩容以及数据的迁移。

map的数据结构

go语言中的map与Java中的map实现还是有些不同，go的map底层实现方式是hash表（哈希桶+数组）
hmap是map的数据结构，bmap是真正用来存放数据的地方，一个bmap内能够存放8个键值对。

const ( 
  bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits  // 一个桶最多存储8个key-value对
    loadFactorNum = 13 // 扩散因子：loadFactorNum / loadFactorDen = 6.5。触发扩容
    loadFactorDen = 2  
)
type hmap struct {
    count     int     
    flags     uint8  // 记录几个特殊的位标记，如当前是否有别的线程正在写map、当前是否为相同大小的增长（扩容/缩容？）
    B         uint8  // hash桶buckets的数量为2^B个
    noverflow uint16 
    hash0     uint32 // hash种子

    buckets    unsafe.Pointer // 指向2^B个桶组成的数组的指针，数据存在这里
    oldbuckets unsafe.Pointer 
    nevacuate  uintptr        // 计数器，标示扩容后搬迁的进度

    extra *mapextra // 保存溢出桶的链表和未使用的溢出桶数组的首地址
}
type mapextra struct {

    overflow    *[]*bmap
    oldoverflow *[]*bmap

    nextOverflow *bmap //保存为使用的数组桶地址
}
type bmap struct { 
  tophash [8]uint8 //存储哈希值的高8位 
  data byte[1] //key value数据:key/key/key/.../value/value/value... 如此存放是为了节省 字节对齐带来的空间浪费。
  overflow *bmap //溢出bucket的地址 
}

hmap的B为1，那么进行初始化的时候会生成2^B个桶（bucket1，bucket2）

map查找逻辑

① 在查找key之前，会做异常检测，校验map是否未初始化，或正在并发写操作，如果存在，则抛出异常：（这就是为什么map 并发写回panic的原因）
② 需要计算key 对应的hash 值，如果buckets 为空（初始化的时候小于一定长度的map 不会初始化数据）还需要初始化一个bucket
③ 通过hash 值，获取对应的bucket。如果map 还在迁移数据，还需要在oldbuckets中找对应的bucket，并搬迁到新的bucket。
④ 拿到bucket之后，还需要按照链表方式一个一个查，找到对应的key， 可能是已经存在的key，也可能需要新增。
⑤ 插入数据前，会先检查数据太多了，需要扩容，如果需要扩容，那就从第③开始拿到新的bucket，并查找对应的位置。

map扩容

在向 map 插入新 key 的时候，会进行条件检测，符合下面这 2 个条件，就会触发扩容：

• 装载因子超过阈值，源码里定义的阈值是 6.5。
• overflow 的 bucket 数量过多：
  当 B < 15，如果 overflow 的 bucket 数量超过 2^B；
  当 B >= 15，如果 overflow 的 bucket 数量超过 2^15。

扩容的源码：

// src/runtime/hashmap.go/mapassign
// 触发扩容时机
if !h.growing() && (overLoadFactor(int64(h.count), h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
    }
// 装载因子超过 6.5
func overLoadFactor(count int64, B uint8) bool {
    return count >= bucketCnt && float32(count) >= loadFactor*float32((uint64(1)<<B))
}
// overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    if B < 16 {
        return noverflow >= uint16(1)<<B
    }
    return noverflow >= 1<<15
}