深读 golang 中 map 后思考和借鉴
简介
Golang 的 Map 概念不做过多解释,与 Python 的字典,Java 中的 Map 类似,都是 K、V 键值对的方式存储,其中键值是不可以重复,而且是无序的。Golang 中 Map 相对其他语言的一个特点就是:键值对支持 array 数组。
声明
常用操作
底层剖析
Map 核心由 hmap 和 bmap 组成
结构类型
最外面是 hmap 结构体,用 buckets 存放一些名字叫 bmap 的桶(数量不定,是 2 的指数倍)
bmap 是一种有 8 个格子的桶(一定只有 8 个格子),每个格子存放一对 key-value
bmap 有一个 overflow,用于连接下一个 bmap(溢出桶)
hmap 还有 oldbuckets,用于存放老数据(用于扩容时)
mapextra 用于存放非指针数据(用于优化存储和访问),内部的 overflow 和 oldoverflow 实际还是 bmap 的数组。
对应源码
初始化
剖析初始化(结合上图)
创建一个 hmap 结构体对象
上传一个哈希因子 hash0 并赋值给 hmap 对象中,由于后期给 key 创建哈希值
根据 hint=10,根据算法规则来创建 B
根据 B 创建桶,并存放在 buckets 数组中:
当 B<4 的时候,创建桶的个数规则为:2^B 次方;
当 B>=4 的时候,创建桶的数量是:2^B+2^(B-4)(标准桶+益处桶)
注意:每个 bmap 可以存储 8 个键值对,当不够存储的时候,则需要使用益处桶,并将当前 bmap 中的 overflow 字段指向一个溢出桶的位置
对应源码
写入数据
结合哈希因子与 key 生成一个哈希值(二进制)
根据哈希值的后 B 位,并根据后 B 为的值来决定此键值对存放到哪个桶中(bmap);(哈希值的高 8 位存储到 tophash 里面;)
确定后写入数据,将 tophash,key,value 分部写入 bmap 的三个数组中,如果桶已经满,则通过 overflow 找到溢出桶,并在益处桶继续写入
hmap 中的个数 count++
对应源码
读取数据
结合哈希因子和 key 生成哈希值
获取哈希值后 B 位来确定落在哪个桶(bmap)
确定桶之后,再根据可以的哈希值的高 8 位来确定 tophash,最后根据 tophash 中和 key 查找的数据
如果桶和溢出桶都不存在的时候,即数据不存在
对应源码(由于 golang 会对应到具体类型的函数,这里以一个为例)
扩容
map 中的总数/桶个数 >6.5 ,引发翻倍扩容
使用太多的益处桶
B <=15 ,引发等量扩容
B > 15 引发等量扩容
扩容时候,新数据写入新桶
迁移
翻倍扩容(B+1)
遍历旧桶中每个元素包括溢出桶的键,重新计算哈希值,找到新桶中的索引位
等量扩容(B)
循环所有的数据,将原来的数据移动到新的桶中
对应源码
思考
结构设计
Golang 基本数据结构是:数组+数组+链表;由于在 bmap 中 golang 使用了高低位来快速定位到元素的位置,而不是像 Java 一样需要遍历链表,另外如果 golang 超过桶的个数后会通过指针指向下一个溢出桶,整体看是放弃了链表转红黑树的方式,这样在冲突过多的情况下,采用了使用空间换时间方式。
扩容方式
扩容过程中不会全部迁移,而是每次迁移的方式,这样保障了 map 的性能。这里才我们实际项目中如果存在数据的写操作,可以参考 Map 的设计思想(这里有点类似 Redis 的 hash 扩容,采用一个单线程,在后台逐步迁移数据),这样大大可以提升我们的系统容量
版权声明: 本文为 InfoQ 作者【ninetyhe】的原创文章。
原文链接:【http://xie.infoq.cn/article/de96ea7c3aae10aa3d33c81fb】。文章转载请联系作者。
评论