文档章节

Go map实现原理

恋恋美食
 恋恋美食
发布于 2018/09/25 15:31
字数 1854
阅读 920
收藏 2

1. map数据结构

Golang的map使用哈希表作为底层实现,一个哈希表里可以有多个哈希表节点,也即bucket,而每个bucket就保存了map中的一个或一组键值对。

map数据结构由runtime/map.go/hmap定义:

type hmap struct {
	count     int // 当前保存的元素个数
	...
	B         uint8  // 指示bucket数组的大小
	...
	buckets    unsafe.Pointer // bucket数组指针,数组的大小为2^B
	...
}

下图展示一个拥有4个bucket的map:

本例中, hmap.B=2, 而hmap.buckets长度是2^B为4. 元素经过哈希运算后会落到某个bucket中进行存储。查找过程类似。

bucket很多时候被翻译为桶,所谓的哈希桶实际上就是bucket。

2. bucket数据结构

bucket数据结构由runtime/map.go/bmap定义:

type bmap struct {
	tophash [8]uint8 //存储哈希值的高8位
	data    byte[1]  //key value数据:key/key/key/.../value/value/value...
	overflow *bmap   //溢出bucket的地址
}

每个bucket可以存储8个键值对。

  • tophash是个长度为8的数组,哈希值相同的键(准确的说是哈希值低位相同的键)存入当前bucket时会将哈希值的高位存储在该数组中,以方便后续匹配。
  • data区存放的是key-value数据,存放顺序是key/key/key/...value/value/value,如此存放是为了节省字节对齐带来的空间浪费。
  • overflow 指针指向的是下一个bucket,据此将所有冲突的键连接起来。

注意:上述中data和overflow并不是在结构体中显示定义的,而是直接通过指针运算进行访问的。

下图展示bucket存放8个key-value对:

3. 哈希冲突

当有两个或以上数量的键被哈希到了同一个bucket时,我们称这些键发生了冲突。Go使用链地址法来解决键冲突。
由于每个bucket可以存放8个键值对,所以同一个bucket存放超过8个键值对时就会再创建一个键值对,用类似链表的方式将bucket连接起来。

下图展示产生冲突后的map:

bucket数据结构指示下一个bucket的指针称为overflow bucket,意为当前bucket盛不下而溢出的部分。事实上哈希冲突并不是好事情,它降低了存取效率,好的哈希算法可以保证哈希值的随机性,但冲突过多也是要控制的,后面会再详细介绍。

4. 负载因子

负载因子用于衡量一个哈希表冲突情况,公式为:

负载因子 = 键数量/bucket数量

例如,对于一个bucket数量为4,包含4个键值对的哈希表来说,这个哈希表的负载因子为1.

哈希表需要将负载因子控制在合适的大小,超过其阀值需要进行rehash,也即键值对重新组织:

  • 哈希因子过小,说明空间利用率低
  • 哈希因子过大,说明冲突严重,存取效率低

每个哈希表的实现对负载因子容忍程度不同,比如Redis实现中负载因子大于1时就会触发rehash,而Go则在在负载因子达到6.5时才会触发rehash,因为Redis的每个bucket只能存1个键值对,而Go的bucket可能存8个键值对,所以Go可以容忍更高的负载因子。

5. 渐进式扩容

5.1 扩容的前提条件

为了保证访问效率,当新元素将要添加进map时,都会检查是否需要扩容,扩容实际上是以空间换时间的手段。
触发扩容的条件有二个:

  1. 负载因子 > 6.5时,也即平均每个bucket存储的键值对达到6.5个。
  2. overflow数量 > 2^15时,也即overflow数量超过32768时。

5.2 增量扩容

当负载因子过大时,就新建一个bucket,新的bucket长度是原来的2倍,然后旧bucket数据搬迁到新的bucket。
考虑到如果map存储了数以亿计的key-value,一次性搬迁将会造成比较大的延时,Go采用逐步搬迁策略,即每次访问map时都会触发一次搬迁,每次搬迁2个键值对。

下图展示了包含一个bucket满载的map(为了描述方便,图中bucket省略了value区域):
当前map存储了7个键值对,只有1个bucket。此地负载因子为7。再次插入数据时将会触发扩容操作,扩容之后再将新插入键写入新的bucket。

当第8个键值对插入时,将会触发扩容,扩容后示意图如下:
hmap数据结构中oldbuckets成员指身原bucket,而buckets指向了新申请的bucket。新的键值对被插入新的bucket中。 后续对map的访问操作会触发迁移,将oldbuckets中的键值对逐步的搬迁过来。当oldbuckets中的键值对全部搬迁完毕后,删除oldbuckets。

搬迁完成后的示意图如下:

数据搬迁过程中原bucket中的键值对将存在于新bucket的前面,新插入的键值对将存在于新bucket的后面。 实际搬迁过程中比较复杂,将在后续源码分析中详细介绍。

5.3 等量扩容

所谓等量扩容,实际上并不是扩大容量,buckets数量不变,重新做一遍类似增量扩容的搬迁动作,把松散的键值对重新排列一次,以使bucket的使用率更高,进而保证更快的存取。
在极端场景下,比如不断的增删,而键值对正好集中在一小部分的bucket,这样会造成overflow的bucket数量增多,但负载因子又不高,从而无法执行增量搬迁的情况,如下图所示:

上图可见,overflow的buckt中大部分是空的,访问效率会很差。此时进行一次等量扩容,即buckets数量不变,经过重新组织后overflow的bucket数量会减少,即节省了空间又会提高访问效率。

6. 查找过程

查找过程如下:

  1. 跟据key值算出哈希值
  2. 取哈希值低位与hmpa.B取模确定bucket位置
  3. 取哈希值高位在tophash数组中查询
  4. 如果tophash[i]中存储值也哈希值相等,则去找到该bucket中的key值进行比较
  5. 当前bucket没有找到,则继续从下个overflow的bucket中查找。
  6. 如果当前处于搬迁过程,则优先从oldbuckets查找

注:如果查找不到,也不会返回空值,而是返回相应类型的0值。

7. 插入过程

新员素插入过程如下:

  1. 跟据key值算出哈希值
  2. 取哈希值低位与hmap.B取模确定bucket位置
  3. 查找该key是否已经存在,如果存在则直接更新值
  4. 如果没找到将key,将key插入

赠人玫瑰手留余香,如果觉得不错请给个赞~

本篇文章已归档到GitHub项目,求星~ 点我即达

© 著作权归作者所有

恋恋美食

恋恋美食

粉丝 110
博文 155
码字总数 140004
作品 0
杭州
高级程序员
私信 提问
加载中

评论(5)

恋恋美食
恋恋美食 博主

引用来自“小白鼠_”的评论

func make(t Type, size ...IntegerType) Type

对map来说, 第二个参数是设置 B的大小吗?
不是的。第二个参数只是指定能存放多少个元素。
小白鼠_
小白鼠_
func make(t Type, size ...IntegerType) Type

对map来说, 第二个参数是设置 B的大小吗?
LittleJian
LittleJian

引用来自“LittleJian”的评论

data区存放的是key-value数据,存放顺序是key/key/key/...value/value/value,如此存放是为了节省字节对齐带来的空间浪费。 这句话怎么理解?

引用来自“恋恋美食”的评论

举个例子,假如map类型为[int64]int8。
如果存放顺序是key/value/key/value...那么对应的存储空间是8B/8B/8B/8B...(为了寻址速度,int8对应的也会用8字节)
如果存放顺序是key/key/value/value...那么对应的存储空间是8B/8B/1B/1B...
懂了,谢谢谢谢!
恋恋美食
恋恋美食 博主

引用来自“LittleJian”的评论

data区存放的是key-value数据,存放顺序是key/key/key/...value/value/value,如此存放是为了节省字节对齐带来的空间浪费。 这句话怎么理解?
举个例子,假如map类型为[int64]int8。
如果存放顺序是key/value/key/value...那么对应的存储空间是8B/8B/8B/8B...(为了寻址速度,int8对应的也会用8字节)
如果存放顺序是key/key/value/value...那么对应的存储空间是8B/8B/1B/1B...
LittleJian
LittleJian
data区存放的是key-value数据,存放顺序是key/key/key/...value/value/value,如此存放是为了节省字节对齐带来的空间浪费。 这句话怎么理解?
TreeMap实现原理

在用TreeMap之前我们要对TreeMap有个整体的认识。 1、TreeMap介绍 TreeMap是一个通过红黑树实现有序的key-value集合。 TreeMap继承AbstractMap,也即实现了Map,它是一个Map集合 TreeMap实现...

kukudeku
2016/08/24
3.9K
2
TreeMap实现原理

在用TreeMap之前我们要对TreeMap有个整体的认识。 1、TreeMap介绍 TreeMap是一个通过红黑树实现有序的key-value集合。 TreeMap继承AbstractMap,也即实现了Map,它是一个Map集合 TreeMap实现...

kukudeku
2016/08/24
147
0
Web开发系列 - GIS

Google Maps JQuery Maps google map是怎样工作的 Google Maps API编程资源大全 google map限制地图缩放级别和显示范围 WebGIS近来学习小结,GoogleMap影像在线矢量化简述 google map v3 ap...

长征2号
2017/08/09
0
0
对Array.prototype.map的一些认识

前言 写博客真是一项技术活,经常逛掘金看大佬写的文章。我觉得我也应该尝试的写点东西,加深自己对它的认识,也方便以后查阅。 map方法的基本用法 MDN上对map方法的介绍是:map() 方法创建一...

嘿_该学习了
04/17
0
0
Java基础-----集合工具类Collections

Collections类是Java提供的对集合进行操作的工具类;这个类不能生成实例,因为构造器是private;提供的方法都是static方法; 1、提供空的List、Set、Map,不能够进行任何操作,因为它们都是C...

baibuxiha
2016/03/23
168
0

没有更多内容

加载失败,请刷新页面

加载更多

spring cloud

一、从面试题入手 1.1、什么事微服务 1.2、微服务之间如何独立通讯的 1.3、springCloud和Dubbo有哪些区别 1.通信机制:DUbbo基于RPC远程过程调用;微服务cloud基于http restFUL API 1.4、spr...

榴莲黑芝麻糊
50分钟前
2
0
Executor线程池原理与源码解读

线程池为线程生命周期的开销和资源不足问题提供了解决方 案。通过对多个任务重用线程,线程创建的开销被分摊到了多个任务上。 线程实现方式 Thread、Runnable、Callable //实现Runnable接口的...

小强的进阶之路
昨天
6
0
maven 环境隔离

解决问题 即 在 resource 文件夹下面 ,新增对应的资源配置文件夹,对应 开发,测试,生产的不同的配置内容 <resources> <resource> <directory>src/main/resources.${deplo......

之渊
昨天
8
0
详解箭头函数和普通函数的区别以及箭头函数的注意事项、不适用场景

箭头函数是ES6的API,相信很多人都知道,因为其语法上相对于普通函数更简洁,深受大家的喜爱。就是这种我们日常开发中一直在使用的API,大部分同学却对它的了解程度还是不够深... 普通函数和...

OBKoro1
昨天
7
0
轻量级 HTTP(s) 代理 TinyProxy

CentOS 下安装 TinyProxy yum install -y tinyproxy 启动、停止、重启 # 启动service tinyproxy start# 停止service tinyproxy stop# 重启service tinyproxy restart 相关配置 默认...

Anoyi
昨天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部