golang map底层原理

stevenyeahnet · · 368 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

映射是一个集合,可以使用类似处理数组和切片的方式迭代映射中的元素。但映射是无序的集合,意味着没有办法预测键值对被返回的顺序。即便使用同样的顺序保存键值对,每次迭代映射的时候顺序也可能不一样。无序的原因是映射的实现使用了散列表。go语言中的map采用的是哈希查找表,由一个key通过哈希函数得到哈希值,64位系统中就生成一个64bit的哈希值,由这个哈希值将key对应到不同的桶(bucket)中,当有多个哈希映射到相同的的桶中时,使用链表解决哈希冲突。
hash函数
golang中的map使用hash查找,就是将key做hash运算得到一个哈希值,根据哈希值确定key-value落在哪个bucket的哪个cell。hash算法和CPU有关,如果cpu支持aes,那么使用aes hash,否则使用memhash。
数据结构

// A header for a Go map.
type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count     int // # live cells == size of map.  Must be first (used by len() builtin)
    flags     uint8  //map状态标识,比如是否在被写或迁移等
    B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
    noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
    hash0     uint32 // hash seed随机hash种子

    buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
    oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
    nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)

    extra *mapextra // optional fields
}
//用**mapextra**来存储key和value都不是指针类型的map,并且大小都小于128字节,这样可以避免GC扫描整个map
// mapextra holds fields that are not present on all maps.
type mapextra struct {
    // If both key and elem do not contain pointers and are inline, then we mark bucket
    // type as containing no pointers. This avoids scanning such maps.
    // However, bmap.overflow is a pointer. In order to keep overflow buckets
    // alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
    // overflow and oldoverflow are only used if key and elem do not contain pointers.
    // overflow contains overflow buckets for hmap.buckets.
    // oldoverflow contains overflow buckets for hmap.oldbuckets.
    // The indirection allows to store a pointer to the slice in hiter.
    overflow    *[]*bmap
    oldoverflow *[]*bmap

    // nextOverflow holds a pointer to a free overflow bucket.
    nextOverflow *bmap
}
// A bucket for a Go map.
//**bmap**可以理解为buckets of map的缩写,它就是map中bucket的本体,即存key和value数据的“桶”
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    tophash [bucketCnt]uint8
    // Followed by bucketCnt keys and then bucketCnt elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

根据哈希函数将key生成一个hash值,其中低位hash用来判断桶的位置,高位hash确定在桶中的哪个cell。低位哈希就是哈希值的低B位,hmap结构体中的B,比如B为5,2^5=32,即该map有32个桶,只需要取哈希值的低5位就可以确定当前key-value落在哪个桶(bucket)中;高位哈希即tophash,是指哈希值的高8bits,根据tophash来确定key在桶中的位置。每个桶可以存储8对key-value,存储结构不是key/value/key/value...,而是key/key..value/value,这样可以避免字节对齐时的padding,节省内存空间。
当不同的key根据哈希得到的tophash和低位hash都一样,发生哈希碰撞,这个时候就体现overflow pointer字段的作用了。桶溢出时,就需要把key-value对存储在overflow bucket(溢出桶),overflow pointer就是指向overflow bucket的指针。如果overflow bucket也溢出了呢?那就再给overflow bucket新建一个overflow bucket,用指针串起来就形成了链式结构,map本身有2^B个bucket,只有当发生哈希碰撞后才会在bucket后链式增加overflow bucket。
map内存布局
扩容

装填因子是否大于6.5
装填因子 = 元素个数/桶个数,大于6.5时,说明桶快要装满,需要扩容

overflow bucket是否太多
当bucket的数量 < 2^15,但overflow bucket的数量大于桶数量
当bucket的数量 >= 2^15,但overflow bucket的数量大于2^15

双倍扩容:装载因子多大,直接翻倍,B+1;扩容也不是申请一块内存,立马开始拷贝,每一次访问旧的buckets时,就迁移一部分,直到完成,旧bucket被GC回收。

等量扩容:重新排列,极端情况下,重新排列也解决不了,map成了链表,性能大大降低,此时哈希种子hash0的设置,可以降低此类极端场景的发生。
查找
根据key计算出哈希值
根据哈希值低位确定所在bucket
根据哈希值高8位确定在bucket中的存储位置
当前bucket未找到则查找对应的overflow bucket。
对应位置有数据则对比完整的哈希值,确定是否是要查找的数据
如果当前处于map进行了扩容,处于数据搬移状态,则优先从oldbuckets查找。
插入
根据key计算出哈希值
根据哈希值低位确定所在bucket
根据哈希值高8位确定在bucket中的存储位置
查找该key是否存在,已存在则更新,不存在则插入
map无序
map的本质是散列表,而map的增长扩容会导致重新进行散列,这就可能使map的遍历结果在扩容前后变得不可靠,Go设计者为了让大家不依赖遍历的顺序,故意在实现map遍历时加入了随机数,让每次遍历的起点--即起始bucket的位置不一样,即不让遍历都从bucket0开始,所以即使未扩容时我们遍历出来的map也总是无序的。


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:stevenyeahnet

查看原文:golang map底层原理

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:1006366459

368 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传