go+语言+map+操作 go的map实现

Go语言使用 map 时尽量不要在 big map 中保存指针

不知道你有没有听过这么一句：在使用 map 时尽量不要在 big map 中保存指针。好吧，你现在已经听过了：）为什么呢？原因在于 Go 语言的垃圾回收器会扫描标记 map 中的所有元素，GC 开销相当大，直接GG。

成都创新互联公司主要业务有网站营销策划、成都网站设计、做网站、微信公众号开发、小程序开发、H5建站、程序开发等业务。一次合作终身朋友，是我们奉行的宗旨；我们不仅仅把客户当客户，还把客户视为我们的合作伙伴，在开展业务的过程中，公司还积累了丰富的行业经验、成都全网营销推广资源和合作伙伴关系资源，并逐渐建立起规范的客户服务和保障体系。 

这两天在《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 语言中很多模块设计得太精妙了。

差不多说清楚了，能力有限，有不对的地方欢迎留言讨论，源码位置还是问的群里大佬 _

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两个部key 1 B == 0 分配到x部分，key 1 B == 1 分配到y部分

注意： 当前只对双倍扩容描述， 等量扩容只是重新填充了一下元素， 相对位置没有改变。

假设当前map 的B == 5，原本元素经过hash函数计算的 hash 值为：

因为双倍扩容之后 B = B + 1，此时B == 6。key 1 B == 1, 即 当前元素rehash到高位，新buckets中 y 部分. 否则 key 1 B == 0 则rehash到低位，即x 部分。

使用方式：

可以看到，每一遍历生成迭代器的时候，会随机选取一个bucket 以及 一个cell开始。 从前往后遍历，再次遍历到起始位置时，遍历完成。

Go语言——sync.Map详解

sync.Map是1.9才推荐的并发安全的map，除了互斥量以外，还运用了原子操作，所以在这之前，有必要了解下 Go语言——原子操作

go1.10\src\sync\map.go

entry分为三种情况：

从read中读取key，如果key存在就tryStore。

注意这里开始需要加锁，因为需要操作dirty。

条目在read中，首先取消标记，然后将条目保存到dirty里。（因为标记的数据不在dirty里）

最后原子保存value到条目里面，这里注意read和dirty都有条目。

总结一下Store：

这里可以看到dirty保存了数据的修改，除非可以直接原子更新read，继续保持read clean。

有了之前的经验，可以猜测下load流程：

与猜测的 区别 ：

由于数据保存两份，所以删除考虑：

先看第二种情况。加锁直接删除dirty数据。思考下貌似没什么问题，本身就是脏数据。

第一种和第三种情况唯一的区别就是条目是否被标记。标记代表删除，所以直接返回。否则CAS操作置为nil。这里总感觉少点什么，因为条目其实还是存在的，虽然指针nil。

看了一圈貌似没找到标记的逻辑，因为删除只是将他变成nil。

之前以为这个逻辑就是简单的将为标记的条目拷贝给dirty，现在看来大有文章。

p == nil，说明条目已经被delete了，CAS将他置为标记删除。然后这个条目就不会保存在dirty里面。

这里其实就跟miss逻辑串起来了，因为miss达到阈值之后，dirty会全量变成read，也就是说标记删除在这一步最终删除。这个还是很巧妙的。

真正的删除逻辑：

很绕。。。。

golang hashmap的使用及实现

由于go语言是一个强类型的语言，因此hashmap也是有类型的，具体体现在key和value都必须指定类型，比如声明一个key为string，value也是string的map，

需要这样做

大部分类型都能做key，某些类型是不能的，共同的特点是： 不能使用== 来比较，包括: slice, map, function

在迭代的过程中是可以对map进行删除和更新操作的，规则如下：

golang的map是hash结构的，意味着平均访问时间是O(1)的。同传统的hashmap一样，由一个个bucket组成:

那我们怎么访问到对应的bucket呢，我们需要得到对应key的hash值

各个参数的意思：

目前采用的是这一行:

| 6.50 | 20.90 | 10.79 | 4.25 | 6.50 |

标题名称：go+语言+map+操作 go的map实现
标题路径：http://mswzjz.cn/article/doidide.html