锐客网

  1. 首页 > 生活百科 > it技术 > >

go语言中的map go语言中的nil

哈希IT技术

goland map底层原理map 是Go语言中基础的数据结构，在日常的使用中经常被用到 。但是它底层是如何实现的呢？
总体来说golang的map是hashmap，是使用数组 链表的形式实现的，使用拉链法消除hash冲突 。
golang的map由两种重要的结构，hmap和bmap(下文中都有解释)，主要就是hmap中包含一个指向bmap数组的指针，key经过hash函数之后得到一个数，这个数低位用于选择bmap(当作bmap数组指针的下表) ， 高位用于放在bmap的[8]uint8数组中，用于快速试错 。然后一个bmap可以指向下一个bmap(拉链) 。
Golang中map的底层实现是一个散列表，因此实现map的过程实际上就是实现散表的过程 。在这个散列表中，主要出现的结构体有两个，一个叫 hmap (a header for a go map) ， 一个叫 bmap (a bucket for a Go map，通常叫其bucket) 。这两种结构的样子分别如下所示：
hmap :
图中有很多字段，但是便于理解map的架构，go语言中的map你只需要关心的只有一个，就是标红的字段： buckets数组。Golang的map中用于存储的结构是bucket数组 。而bucket(即bmap)的结构是怎样的呢？
bucket ：
相比于hmap，bucket的结构显得简单一些，标红的字段依然是“核心”，go语言中的map我们使用的map中的key和value就存储在这里 。“高位哈希值”数组记录的是当前bucket中key相关的“索引”，稍后会详细叙述 。还有一个字段是一个指向扩容后的bucket的指针，使得bucket会形成一个链表结构 。例如下图：
由此看出hmap和bucket的关系是这样的：
而bucket又是一个链表 ， 所以，整体的结构应该是这样的：
哈希表的特点是会有一个哈希函数，对你传来的key进行哈希运算，得到唯一的值，一般情况下都是一个数值 。Golang的map中也有这么一个哈希函数，也会算出唯一的值，对于这个值的使用，Golang也是很有意思 。
Golang把求得的值按照用途一分为二：高位和低位 。
如图所示，蓝色为高位，红色为低位 。然后低位用于寻找当前key属于hmap中的哪个bucket，而高位用于寻找bucket中的哪个key 。上文中提到：bucket中有个属性字段是“高位哈希值”数组，这里存的就是蓝色的高位值 ， 用来声明当前bucket中有哪些“key” ， 便于搜索查找 。需要特别指出的一点是：我们map中的key/value值都是存到同一个数组中的 。数组中的顺序是这样的:
并不是key0/value0/key1/value1的形式 ， 这样做的好处是：在key和value的长度不同的时候，可 以消除padding(内存对齐)带来的空间浪费。
现在，我们可以得到Go语言map的整个的结构图了：(hash结果的低位用于选择把KV放在bmap数组中的哪一个bmap中，高位用于key的快速预览，用于快速试错)
map的扩容
【go语言中的map go语言中的nil】 当以上的哈希表增长的时候，Go语言会将bucket数组的数量扩充一倍 ， 产生一个新的bucket数组，并将旧数组的数据迁移至新数组 。
加载因子
判断扩充的条件，就是哈希表中的加载因子(即loadFactor) 。
加载因子是一个阈值，一般表示为：散列包含的元素数 除以 位置总数 。是一种“产生冲突机会”和“空间使用”的平衡与折中：加载因子越?。?说明空间空置率高 ， 空间使用率小 ， 但是加载因子越大，说明空间利用率上去了，但是“产生冲突机会”高了 。
每种哈希表的都会有一个加载因子，数值超过加载因子就会为哈希表扩容 。
Golang的map的加载因子的公式是：map长度 / 2^B(这是代表bmap数组的长度，B是取的低位的位数)阈值是6.5 。其中B可以理解为已扩容的次数 。
当Go的map长度增长到大于加载因子所需的map长度时，Go语言就会将产生一个新的bucket数组，然后把旧的bucket数组移到一个属性字段oldbucket中 。注意：并不是立刻把旧的数组中的元素转义到新的bucket当中 ， 而是，只有当访问到具体的某个bucket的时候，会把bucket中的数据转移到新的bucket中 。
如下图所示：当扩容的时候，Go的map结构体中 ， 会保存旧的数据，和新生成的数组
上面部分代表旧的有数据的bucket，下面部分代表新生成的新的bucket 。蓝色代表存有数据的bucket，橘黄色代表空的bucket 。
扩容时map并不会立即把新数据做迁移，而是当访问原来旧bucket的数据的时候 ， 才把旧数据做迁移，如下图：
注意：这里并不会直接删除旧的bucket，而是把原来的引用去掉，利用GC清除内存 。
map中数据的删除
如果理解了map的整体结构 ， 那么查找、更新、删除的基本步骤应该都很清楚了 。这里不再赘述 。
值得注意的是，找到了map中的数据之后，针对key和value分别做如下操作：
1
2
3
4
1、如果``key``是一个指针类型的 ， 则直接将其置为空，等待GC清除；
2、如果是值类型的，则清除相关内存 。
3、同理，对``value``做相同的操作 。
4、最后把key对应的高位值对应的数组index置为空 。
golang map源码浅析 golang 中 map的实现结构为： 哈希表链表 。其中链表 ， 作用是当发生hash冲突时，拉链法生成的结点 。
可以看到，[]bmap是一个hash table，每一个 bmap是我们常说的“桶” 。经过hash 函数计算出来相同的hash值 ， 放到相同的桶中 。一个 bmap中可以存放 8个 元素， 如果多出8个，则生成新的结点，尾接到队尾 。
以上是只是静态文件 src/runtime/map.go 中的定义 。实际上编译期间会给它加料，动态地创建一个新的结构：
上图就是 bmap的内存模型，HOB Hash指的就是 top hash 。注意到 key 和 value 是各自放在一起的 ， 并不是key/value/key/value/...这样的形式 。源码里说明这样的好处是在某些情况下可以省略掉 padding 字段，节省内存空间 。
每个 bmap设计成 最多只能放 8 个 key-value 对 ， 如果有第 9 个 key-value 落入当前的 bmap，那就需要再构建一个 bmap，通过overflow指针连接起来 。
map创建方法:
我们实际上是通过调用的makemap ， 来创建map的 。实际工作只是初始化了hmap中的各种字段，如：设置B的大小，设置hash 种子 hash 0.
注意 :
makemap返回是*hmap指针，即map 是引用对象， 对map的操作会影响到结构体内部。
使用方式
对应的是下面两种方法
map的key的类型，实现了自己的hash 方式 。每种类型实现hash函数方式不一样 。
key 经过哈希计算后得到hash值，共 64 个 bit 位 。其中后B 个bit位置， 用来定位当前元素落在哪一个桶里，高8个bit 为当前 hash 值的top hash 。实际上定位key的过程是一个双重循环的过程， 外层循环遍历 所有的overflow，内层循环遍历 当前bmap 中的 8个元素。
举例说明： 如果当前 B 的值为 5 ， 那么buckets 的长度 为 2^5 = 32 。假设有个key 经过hash函数计算后，得到的hash结果为：
外层遍历bucket 中的链表
内层循环遍历 bmap中的8个 cell
建议先不看此部分内容，看完后续修改 map中元素 - 扩容操作后 再回头看此部分内容 。
扩容前的数据：
等量扩容后的数据：
等量扩容后 ， 查找方式和原本相同，不多做赘述 。
两倍扩容后的数据
两倍扩容后，oldbuckets 的元素，可能被分配成了两部分 。查找顺序如下：
此处只分析mapaccess1 , 。mapaccess2相比mapaccess1 多添加了是否找到的bool值，有兴趣可自行看一下 。
使用方式：
步骤如下：
扩容条件 ：
扩容的标识 ： h.oldbuckets ！= nil
假设当前定位到了新的buckets的3号桶中，首先会判断oldbuckets中的对应的桶有没有被搬迁过 。如果搬迁过了，不需要看原来的桶了，直接遍历新的buckets的3号桶 。
扩容前：
等量扩容结果
双倍扩容会将old buckets上的元素分配到x， y两个部key1B == 0 分配到x部分，key1B == 1 分配到y部分
注意： 当前只对双倍扩容描述，等量扩容只是重新填充了一下元素 ， 相对位置没有改变 。
假设当前map 的B == 5，原本元素经过hash函数计算的 hash 值为：
因为双倍扩容之后 B = B1，此时B == 6 。key1B == 1, 即 当前元素rehash到高位，新buckets中 y 部分. 否则 key1B == 0 则rehash到低位，即x 部分 。
使用方式：
可以看到 ， 每一遍历生成迭代器的时候，会随机选取一个bucket 以及 一个cell开始 。从前往后遍历，再次遍历到起始位置时，遍历完成 。
Go语言使用 map 时尽量不要在 big map 中保存指针 不知道你有没有听过这么一句：在使用 map 时尽量不要在 big map 中保存指针 。好吧，你现在已经听过了：）为什么呢？原因在于 Go 语言的垃圾回收器会扫描标记 map 中的所有元素，GC 开销相当大，直接GG 。
这两天在《Mastering Go》中看到 GC 这一章节里面对比 map 和 slice 在垃圾回收中的效率对比，书中只给出结论没有说明理由 ， 这我是不能忍的，于是有了这篇学习笔记 。扯那么多，Show Your Code
这是一个简单的测试程序，保存字符串的 map 和 保存整形的 map GC 的效率相差几十倍，是不是有同学会说明明保存的是 string 哪有指针？这个要说到 Go 语言中 string 的底层实现了 ， 源码在 src/runtime/string.go里，可以看到 string 其实包含一个指向数据的指针和一个长度字段 。注意这里的是否包含指针，包括底层的实现 。
Go 语言的 GC 会递归遍历并标记所有可触达的对象，标记完成之后将所有没有引用的对象进行清理 。扫描到指针就会往下接着寻找，一直到结束 。
Go 语言中 map 是基于 数组和链表 的数据结构实现的，通过 优化的拉链法 解决哈希冲突，每个 bucket 可以保存8对键值，在8个键值对数据后面有一个 overflow 指针，因为桶中最多只能装8个键值对，如果有多余的键值对落到了当前桶，那么就需要再构建一个桶（称为溢出桶） ， 通过 overflow 指针链接起来 。
因为 overflow 指针的缘故，所以无论 map 保存的是什么 ， GC 的时候就会把所有的 bmap 扫描一遍，带来巨大的 GC 开销 。官方 issues 就有关于这个问题的讨论，runtime: Large maps cause significant GC pauses #9477
无脑机翻如下：
如果我们有一个map [k] v ， 其中k和v都不包含指针，并且我们想提高扫描性能，则可以执行以下操作 。
将“ allOverflow [] unsafe.Pointer”添加到 hmap 并将所有溢出存储桶存储在其中 。然后将 bmap 标记为noScan 。这将使扫描非常快，因为我们不会扫描任何用户数据 。
实际上，它将有些复杂，因为我们需要从allOverflow中删除旧的溢出桶 。而且它还会增加 hmap 的大小 ， 因此也可能需要重新整理数据 。
最终官方在 hmap 中增加了overflow相关字段完成了上面的优化，这是具体的commit地址 。
下面看下具体是如何实现的，源码基于 go1.15，src/cmd/compile/internal/gc/reflect.go 中
通过注释可以看出，如果 map 中保存的键值都不包含指针（通过 Haspointers 判断） ， 就使用一个 uintptr 类型代替 bucket 的指针用于溢出桶 overflow 字段，uintptr 类型在 GO 语言中就是个大小可以保存得下指针的整数，不是指针 ， 就相当于实现了 将 bmap 标记为 noScan，GC 的时候就不会遍历完整个 map 了 。随着不断的学习，愈发感慨 GO 语言中很多模块设计得太精妙了 。
差不多说清楚了，能力有限，有不对的地方欢迎留言讨论，源码位置还是问的群里大佬 _
关于go语言中的map和go语言中的nil的介绍到此就结束了，不知道你从中找到你需要的信息了吗 ？如果你还想了解更多这方面的信息 ， 记得收藏关注本站 。

    推荐阅读


    上一篇：python截取字符串dataframe，python截取字符串第一位

    下一篇：如何将网站源码上传至服务器？ 网站源码怎么放进服务器