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
}
golang channel操作情况
golang中切边和数组
标签:

发表我的评论

电子邮件地址不会被公开。 必填项已用*标注

65 + 49 =

ajax-loader