Go教程

详细解读go语言中的map

本文主要是介绍详细解读go语言中的map,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

Map

map底层是由哈希表实现的

Go使用链地址法来解决键冲突。

map本质上是一个指针,指向hmap

屏幕截图 2021-08-11 105911

这里的buckets就是桶,bmap

每一个bucket最多可以放8个键值对,但是为了让内存排列更加紧凑,8个key放一起,8个value放一起。在8个key前面是8个tophash,每个tophash都是对应哈希值的高8位,最后由一个overflow字段指向下一个bmap,就是溢出桶。溢出桶内存布局和常规桶一样,bmap内存布局如图

屏幕截图 2021-08-11 120155

如果哈希表要分配的桶的数目大于24,就会预分配2(B-4)个溢出桶备用。

这些溢出桶和常规桶在内存中是连续的,前2^B个用作常规桶,后面的用作溢出桶

查找过程
  1. 查找或者操作map时,首先key经过hash函数生成hash值
  2. 通过哈希值的低8位来判断当前数据属于哪个桶(bucket)
  3. 找到bucket以后,通过哈希值的高八位与bucket存储的高位哈希值循环比对
  4. 如果相同就比较刚才找到的底层数组的key值,如果key相同,取出value。
  5. 如果高八位hash值在此bucket没有,或者有,但是key不相同,就去链表中下一个溢出bucket中查找,直到查找到链表的末尾。
  6. 如果查找不到,也不会返回空值,而是返回相应类型的0值。
插入过程

新元素插入过程如下:

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

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

触发扩容的条件有二个:

  1. 负载因子 > 6.5时,也即平均每个bucket存储的键值对达到6.5个。

    负载因子 = 键数量/bucket数量
    
  2. 溢出桶(overflow)数量 > 2^15时,也即overflow数量超过32768时。

  • 增量扩容

​ 如果负载因子>6.5时,进行增量扩容。这时会新建一个桶(bucket),新的bucket长度是原来的2倍,然后旧桶数据搬迁到新桶。每个旧桶的键值对都会分流到两个新桶中

​ 考虑到如果map存储了数以亿计的key-value,一次性搬迁将会造成比较大的延时,Go选择“渐进式扩容”,先分配2倍内存空间的新桶,然后标记当前哈希表正在扩容,每次访问map时都会触发一次搬迁,这样可以把扩容消耗的时间分散到多次操作中。

  • 等量扩容

负载因子没超标,溢出桶较多

  1. ​ 如果常规桶数目不大于2^15,那么使用的溢出桶数目超过常规桶就算是多了;

  2. ​ 如果常规桶数目大于215,那么使用溢出桶数目一旦超过215就算多了。

    所谓等量扩容,就是创建和旧桶数目一样多的新桶,然后把原来的键值对迁移到新桶中,重新做一遍类似增量扩容的搬迁动作。这样做的目的是把松散的键值对重新排列一次,能够存储的更加紧凑,进而减少溢出桶的使用,以使bucket的使用率更高,进而保证更快的存取。

这篇关于详细解读go语言中的map的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!