Map map底层是由哈希表实现的
Go使用链地址法来解决键冲突。
当两个key落在了同一个桶中,这时就发生了哈希冲突。go的解决方式是链地址法:在桶中按照顺序寻到第一个空位,若有位置,则将其置于其中;否则,判断是否存在溢出桶,若有溢出桶,则去该桶的溢出桶中寻找空位,如果没有溢出桶,则添加溢出桶,并将其置溢出桶的第一个空位。
底层结构 map本质上是一个指针,指向hmap
这里的buckets就是桶,bmap
每一个bucket最多可以放8个键值对,但是为了让内存排列更加紧凑,8个key放一起,8个value放一起。在8个key前面是8个tophash,每个tophash都是对应哈希值的高8位,最后由一个overflow字段指向下一个bmap,就是溢出桶。溢出桶内存布局和常规桶一样,bmap内存布局如图
如果哈希表要分配的桶的数目大于24,就会预分配2(B-4)个溢出桶备用。
这些溢出桶和常规桶在内存中是连续的,前2^B个用作常规桶,后面的用作溢出桶
查找过程
- 查找或者操作map时,首先key经过hash函数生成hash值
- 通过哈希值的低8位来判断当前数据属于哪个桶(bucket)
- 找到bucket以后,通过哈希值的高八位与bucket存储的高位哈希值循环比对
- 如果相同就比较刚才找到的底层数组的key值,如果key相同,取出value。
- 如果高八位hash值在此bucket没有,或者有,但是key不相同,就去链表中下一个溢出bucket中查找,直到查找到链表的末尾。
- 如果查找不到,也不会返回空值,而是返回相应类型的0值。
插入过程 新元素插入过程如下:
- 根据key值算出哈希值
- 取哈希值低位与hmap.B取模确定bucket位置
- 查找该key是否已经存在,如果存在则直接更新值
- 如果没找到将key,将key插入。
map扩容机制 为了保证访问效率,当新元素将要添加进map时,都会检查是否需要扩容,扩容实际上是以空间换时间的手段。
触发扩容的条件有二个:
- 【golang详解|【Golang详解】深入了解map】负载因子 > 6.5时,也即平均每个bucket存储的键值对达到6.5个。
负载因子 = 键数量/bucket数量
- 溢出桶(overflow)数量 > 2^15时,也即overflow数量超过32768时。
```
- 增量扩容
? 考虑到如果map存储了数以亿计的key-value,一次性搬迁将会造成比较大的延时,Go选择**“渐进式扩容”**,先分配2倍内存空间的新桶,然后标记当前哈希表正在扩容,每次访问map时都会触发一次搬迁,这样可以把扩容消耗的时间分散到多次操作中。
- 等量扩容
- ? 如果常规桶数目不大于2^15,那么使用的溢出桶数目超过常规桶就算是多了;
- ? 如果常规桶数目大于215,那么使用溢出桶数目一旦超过215就算多了。
所谓等量扩容,就是创建和旧桶数目一样多的新桶,然后把原来的键值对迁移到新桶中,重新做一遍类似增量扩容的搬迁动作。这样做的目的是把松散的键值对重新排列一次,能够存储的更加紧凑,进而减少溢出桶的使用,以使bucket的使用率更高,进而保证更快的存取。
为什么map输出是无序的?
遍历map的时候,取随机数,把桶的遍历顺序随机化。原因是golang底层并没有保证这一点,或许(现在/以后)会有特殊情况出现顺序不固定的情况。担心开发者们误解这一点,golang就特意去打乱了这个顺序,让开发者们知道golang底层不保证map每次遍历都是同一个顺序。
Go的Map本质上是“无序的”
- “无序”写入:
- 正常写入(非哈希冲突写入):是hash到某一个bucket上,而不是按buckets顺序写入。
- 哈希冲突写入:如果存在hash冲突,会写到同一个bucket上,更有可能写到溢出桶去
- 正常写入(非哈希冲突写入):是hash到某一个bucket上,而不是按buckets顺序写入。
- 扩容导致无序
- 成倍扩容迫使元素顺序变化,等量扩容并没有改变元素顺序
总结无序原因
- 无序写入
- 成倍扩容迫使元素顺序变化
Map并发问题
原因 go语言中map并不是并发安全的,因为:
map变量为指针类型变量,同时map操作并不是原子操作,并发时多个协程操作同一内存会发生竞争关系,共享资源会遭到破环,因此出于安全考虑,会抛出错误
想要并发安全,可以使用sync.Map,通过互斥锁实现了并发安全
为什么原生map不是并发安全的?
并发安全是有代价的,如果map保证并发安全,那么一些不需要并发的场景,会有不小的性能损耗
推荐阅读
- Golang|深入理解Golang之context
- 深入理解golang map
- Android云音乐|3.Android高仿网易云音乐-首页复杂发现界面布局和功能
- TypeScript|玩转TypeScript对象、对象作为参数进行函数传递、接口和内置对象[无敌态]
- java|基于DoS攻击能量分级的ICPS综合安全控制与通信协同设计
- 图像处理|肺部阴影识别检测 matlab算法技术
- 后端|MySQL 灵魂 16 问,你能撑到第几问()
- 面试|Python大作业——爬虫+可视化+数据分析+数据库(简介篇)
- Python学习笔记|Python | 类基础