12 Go语言map底层浅析

栏目: Go · 发布时间: 5年前

内容简介:[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计算偏移获取的。

12 Go语言map底层浅析

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的指针

    12 Go语言map底层浅析

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结构图

12 Go语言map底层浅析

如图所示:

  • 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...

https://tiancaiamao.gitbooks....

https://blog.csdn.net/i644803...


以上所述就是小编给大家介绍的《12 Go语言map底层浅析》,希望对大家有所帮助,如果大家有任何疑问请给我留言,小编会及时回复大家的。在此也非常感谢大家对 码农网 的支持!

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

How to Build a Billion Dollar App

How to Build a Billion Dollar App

George Berkowski / Little, Brown Book Group / 2015-4-1 / USD 24.95

Apps have changed the way we communicate, shop, play, interact and travel and their phenomenal popularity has presented possibly the biggest business opportunity in history. In How to Build a Billi......一起来看看 《How to Build a Billion Dollar App》 这本书的介绍吧!

随机密码生成器
随机密码生成器

多种字符组合密码

Base64 编码/解码
Base64 编码/解码

Base64 编码/解码

URL 编码/解码
URL 编码/解码

URL 编码/解码