Golang的Map

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

https://www.jianshu.com/p/aa0d4808cbb8

1、底层数据结构

    hashmap的定义位于src/runtime/hashmap.go 中,

struct hmap struct {

    count int // 元素个数

    flags uint8 // 状态标志

    B uint8 // 可以最多容纳 6.5 * 2 ^ B 个元素,6.5为装载因子

    noverflow uint16 // 溢出的个数

    hash0 uint32 // 哈希种子

    buckets unsafe.Pointer // 桶的地址

    oldbuckets unsafe.Pointer // 旧桶的地址,用于扩容

    nevacuate uintptr // 搬迁进度,小于nevacuate的已经搬迁

    overflow *[2]*[]*bmap

}

1、overflow是一个指针,指向一个元素个数为2的数组,数组的类型是一个指针,指向一个slice,slice的元素是桶(bmap)的地址,这些桶都是溢出桶;因为Go map在hash冲突过多时,会发生扩容操作,为了不全量搬迁数据,使用了增量搬迁,[0]表示当前使用的溢出桶集合,[1]是在发生扩容时,保存了旧的溢出桶集合;overflow存在的意义在于防止溢出桶被gc。

type bmap struct {

    // 每个元素hash值的高8位,如果tophash[0] < minTopHash,表示这个桶的搬迁状态 
     tophash [bucketCnt]uint8
     // 接下来是8个key、8个value,但是我们不能直接看到;为了优化对齐,go采用了key放在一起,value放在一起的存储方式,
     // 再接下来是hash冲突发生时,下一个溢出桶的地址

}

2、实现原理

        不同于STL中map以红黑树实现的方式,Golang采用了HashTable的实现,解决冲突采用的是链地址法。也就是说,使用数组+链表来实现map。

hashmap-buckets

    map是由数组+链表实现的HashTable,Golang通过hashtop快速试错加快了查找过程,利用空间换时间的思想解决了扩容的问题,利用将8个key(8个value)依次放置减少了padding空间等等。

3、扩容

    在分配assign逻辑中,当没有位置给key使用,而且满足测试条件(装载因子>6.5或有太多溢出通)时,会触发hashGrow逻辑。

    扩容阶段;在assign和delete操作中,都会触发扩容growWork。

    扩容策略:第一个大于count的2^B的B值。


example


4、并发安全

    并发操作,会看到读的时候会检查hashWriting标志, 如果有这个标志,就会报并发错误。

    h.flags |= hashWriting

    如果想在并发情况下使用,就要加锁,而且是加一把大锁。 加大锁大概率都不是最优解,一般都会有效率问题。 通俗说就是加大锁影响其他的元素操作了。

    解决思路:减少加锁时间。

    方法: 1.空间换时间。  2.降低影响范围。

    

sync.Map的使用:


       说白了,维护了两个字典。写的时候直接写dirty字典,读的时候先读read字典,然后再读dirty字典。

        type Map struct {

            mu Mutex

            read atomic.Value // readOnly

            dirty map[interface{}]*entry

            misses int

        } 

    mu:加锁作用。保护后文的dirty字段

    read:存读的数据。因为是atomic.Value类型,只读,所以并发是安全的。实际存的是readOnly的数据结构。

    misses:计数作用。每次从read中读失败,则计数+1。

    dirty:map[interface{}]*entry。包含最新写入的数据。当misses计数达到一定值,将其赋值给read。

    sync.Map的优缺点:优点:是官方出的,是亲儿子;通过读写分离,降低锁时间来提高效率; 缺点:不适用于大量写的场景,这样会导致read map读不到数据而进一步加锁读取,同时dirty map也会一直晋升为read map,整体性能较差。 适用场景:大量读,少量写


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

本文来自:简书

感谢作者:rookie_yuqi

查看原文:Golang的Map

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

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