内容简介:[TOC]笼统的来说,go的map底层是一个hash表,通过键值对进行映射。 键通过哈希函数生成哈希值,然后go底层的map数据结构就存储相应的hash值,进行索引,最终是在底层使用的数组存储key,和value。稍微详细的说,就设计到go map 的结构。hmap 和bmap。哈希表就不得不说hash函数。hash函数,有加密型和非加密型。加密型的一般用于加密数据、数字摘要等,典型代表就是md5、sha1、sha256、aes256这种;非加密型的一般就是查找。在map的应用场景中,用的是查找。选择has
Go语言map底层浅析
[TOC]
笼统的来说,go的map底层是一个hash表,通过键值对进行映射。 键通过哈希函数生成哈希值,然后 go 底层的map数据结构就存储相应的hash值,进行索引,最终是在底层使用的数组存储key,和value。稍微详细的说,就设计到go map 的结构。hmap 和bmap。
1、Hash函数
哈希表就不得不说hash函数。hash函数,有加密型和非加密型。加密型的一般用于加密数据、数字摘要等,典型代表就是md5、sha1、sha256、aes256这种;非加密型的一般就是查找。在map的应用场景中,用的是查找。选择hash函数主要考察的是两点:性能、碰撞概率。 golang使用的hash算法根据硬件选择,如果cpu支持aes,那么使用aes hash,否则使用memhash ,memhash是参考xxhash、cityhash实现的,性能非常好。
具体hash函数的性能比较可以看: http://aras-p.info/blog/2016/...
哈希函数会将传入的key值进行哈希运算,得到一个唯一的值。go语言把生成的哈希值一分为二,比如一个key经过哈希函数,生成的哈希值为: 8423452987653321
,go语言会这它拆分为 84234529
,和 87653321
。那么,前半部分就叫做 高位哈希值 ,后半部分就叫做 低位哈希值 。后面会说高位哈希值和低位哈希值是做什么用的。
高位哈希值:是用来确定当前的bucket(桶)有没有所存储的数据的。
低位哈希值:是用来确定,当前的数据存在了哪个bucket(桶)
2、map 源码
2.1hmap(a header of map)
// Go map的一个header结构 type hmap struct { count int // map的大小. len()函数就取的这个值 flags uint8 //map状态标识 B uint8 // 可以最多容纳 6.5 * 2 ^ B 个元素,6.5为装载因子即:map长度=6.5*2^B //B可以理解为已扩容的次数 noverflow uint16 // 溢出buckets的数量 hash0 uint32 // hash 种子 buckets unsafe.Pointer //指向最大2^B个Buckets数组的指针. count==0时为nil. oldbuckets unsafe.Pointer //指向扩容之前的buckets数组,并且容量是现在一半.不增长就为nil nevacuate uintptr // 搬迁进度,小于nevacuate的已经搬迁 extra *mapextra // 可选字段,额外信息 }
hmap是map的最外层的一个数据结构,包括了map的各种基础信息、如大小、bucket。首先说一下,buckets这个参数,它存储的是指向buckets数组的一个指针,当bucket(桶为0时)为nil。 我们可以理解为,hmap指向了一个bucket数组 ,并且当bucket数组需要扩容时,它会开辟一倍的内存空间,并且hi渐进式的把原数组拷贝,即用到旧数组的时候就拷贝到新数组。
2.2 bmap(a bucket of map)
// Go map 的 buckets结构 type bmap struct { // 每个元素hash值的高8位,如果tophash[0] < minTopHash,表示这个桶的搬迁状态 tophash [bucketCnt]uint8 // 第二个是8个key、8个value,但是我们不能直接看到;为了优化对齐,go采用了key放在一起,value放在一起的存储方式, // 第三个是hash冲突发生时,下一个溢出桶的地址 }
bucket(桶),每一个bucket最多放8个key和value,最后由一个overflow字段指向下一个bmap,注意key、value、overflow字段都不显示定义,而是通过maptype计算偏移获取的。
bucket这三部分内容决定了它是怎么工作的:
- 它的tophash 存储的是哈希函数算出的哈希值的高八位。是用来加快索引的。 因为把高八位存储起来,这样不用完整比较key就能过滤掉不符合的key,加快查询速度 当一个哈希值的高8位和存储的高8位相符合,再去比较完整的key值,进而取出value。
- 第二部分,存储的是key 和value,就是我们传入的key和value,注意,它的底层排列方式是,key全部放在一起,value全部放在一起。 当key大于128字节时,bucket的key字段存储的会是指针,指向key的实际内容;value也是一样。
- 这样排列好处是在key和value的长度不同的时候,可以消除padding带来的空间浪费。并且每个bucket 最多存放8个键值对 。
- 第三部分,存储的是当bucket溢出时,指向的下一个bucket的指针
bucket的设计细节:
在golang map中出现冲突时,不是每一个key都申请一个结构通过链表串起来, 而是以bmap为最小粒度挂载,一个bmap可以放8个key和value。这样减少对象数量,减轻管理内存的负担,利于gc。
如果插入时,bmap中key超过8,那么就会申请一个新的bmap(overflow bucket)挂在这个bmap的后面形成链表, 优先用预分配的overflow bucket,如果预分配的用完了,那么就malloc一个挂上去。注意golang的map不会shrink,内存只会越用越多,overflow bucket中的key全删了也不会释放
3、hmap和bmap结构图
如图所示:
- hmap存储了一个指向底层bucket数组的指针。
- 我们存入的key和value是存储在bucket里面中,如果key和value大于128字节,那么bucket里面存储的是指向我们key和value的指针,如果不是则存储的是值。
- 每个bucket 存储8个key和value,如果超过就重新创建一个bucket挂在在元bucket上,持续挂接形成链表。
- 高位哈希值:是用来确定当前的bucket(桶)有没有所存储的数据的。
-
低位哈希值:是用来确定,当前的数据存在了哪个bucket(桶)
简单结构为图:
工作流程:
查找或者操作map时,首先key经过hash函数生成hash值,通过哈希值的低8位来判断当前数据属于哪个桶(bucket),找到bucket以后,通过哈希值的高八位与bucket存储的高位哈希值循环比对,如果相同就将完整的哈希值和刚才找到的底层数组的key值进行比对,如果相同,取出value。
4、map的扩容
- 当链表越来越长,bucket的扩容次数达到一定值,其实是bmap扩容的加载因数达到6.5,bmap就会进行扩容,将原来bucket数组数量扩充一倍,产生一个新的bucket数组,也就是bmap的buckets属性指向的数组。这样bmap中的oldbuckets属性指向的就是旧bucket数组。
- 这里的加载因子LoadFactor是一个阈值,计算方式为(map长度/2^B )如果超过6.5,将会进行扩容,这个是经过测试才得出的合理的一个阈值。因为,加载因子越小,空间利用率就小,加载因子越大,产生冲突的几率就大。所以6.5是一个平衡的值。
- map的扩容不会立马全部复制,而是渐进式扩容,即首先开辟2倍的内存空间,创建一个新的bucket数组。只有当访问原来就的bucket数组时,才会将就得bucket拷贝到新的bucket数组,进行渐进式的扩容。当然旧的数据不会删除,而是去掉引用,等待gc回收。
5、结语
这篇文章,只是对map底层的结构进行了说明,具体创建、查找、删除等的流程是差不多,但是具体的细节还是有很多。所以,我就不一一写出了,贴一下其他博主写的文章,很详细。
5.1 剖析golang map的实现
地址: https://www.jianshu.com/p/092...
5.2 Golang map 的底层实现
地址: https://www.jianshu.com/p/aa0...
参考:
https://www.jianshu.com/p/092...
https://www.jianshu.com/p/aa0...
以上所述就是小编给大家介绍的《12 Go语言map底层浅析》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!
猜你喜欢:- Docker 底层原理浅析
- avue 1.5.2 优化大量底层代码,crud 和 form 底层公用
- Synchronized 关键字使用、底层原理、JDK1.6 之后的底层优化以及 和ReenTrantLock 的对比
- NSDictionary底层实现原理
- PHP 数组底层实现
- NSObject 底层本质
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。
高性能JavaScript
【美】Nicholas C. Zakas(尼古拉斯.泽卡斯) / 丁琛 / 电子工业出版社 / 2015-8-1 / 65
如果你使用 JavaScript 构建交互丰富的 Web 应用,那么 JavaScript 代码可能是造成你的Web应用速度变慢的主要原因。《高性能JavaScript》揭示的技术和策略能帮助你在开发过程中消除性能瓶颈。你将会了解如何提升各方面的性能,包括代码的加载、运行、DOM 交互、页面生存周期等。雅虎的前端工程师 Nicholas C. Zakas 和其他五位 JavaScript 专家介绍......一起来看看 《高性能JavaScript》 这本书的介绍吧!