golang的map数据结构

一、map是一组K/v对的集合。底层支持map数据结构是数组存储方式， 用链表来解决冲突 ，出现冲突时，不是每一个key都申请一个结构通过链表串起来，而是以bmap为最小粒度挂载，一个bmap可以放8个kv。在哈希函数的选择上，会在程序启动时，检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash。每个map的底层结构是hmap，是有若干个结构为bmap的bucket组成的数组。每个bucket底层都采用链表结构。接下来，我们来详细看下map的结构

二、源码在src/runtime/map.go可以找到。(版本为1.19)

下面来分别讲map结构的参数：

• count int //元素个数
•  B         uint8 扩容常量相关字段B是buckets数组的长度的对数 2^B
• noverflow uint16 // 溢出的bucket个数
• buckets    unsafe.Pointer buckets数组的指针
• oldbuckets unsafe.Pointer // 结构扩容的时候用于赋值的buckets数组
• nevacuate uintptr // 搬迁进度
• extra *mapextra // 用于扩容的指针

但这只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创建一个新的结构：

hmap和bmap的结构是这样的 ：

​bmap​

当 map 的 key 和 value 都不是指针，并且 size 都小于 128 字节的情况下，会把 bmap 标记为不含指针，这样可以避免 gc 时扫描整个 hmap。但是，我们看 bmap 其实有一个 overflow 的字段，是指针类型的，破坏了 bmap 不含指针的设想，这时会把 overflow 移动到 hmap的extra 字段来。这部分我们在分析扩容操作的时候再详细说明。下面我们看下bmap的内部组成图：

​HOBHash​​key/value/...​

​map[int64]int8​​key/value...​​key/key/.../value/value/...​​overflow​

二、map操作底层原理分析

1、map初始化：

第一步：入参校验，判断key的类型是否合法，必须为可比较类型。

第二步：底层调用makemap函数，计算得到合适的B，map容量最多可容纳6.5*2^B个元素，6.5为装载因子阈值常量。装载因子的计算公式是：装载因子=填入表中的元素个数/散列表的长度，装载因子越大，说明空闲位置越少，冲突越多，散列表的性能会下降。

​fastrand​​hint​​makeBucketArray​​B​​2^(B-4)​

2、查找操作

Go 语言中读取 map 有两种语法：带 comma 和 不带 comma。当要查询的 key 不在 map 里，带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0，如果 value 是 string 类型，就会返回空字符串。

两种语法对应到底层两个不同的函数，那么在底层是如何定位到key的呢？稍后我们对函数进行源码分析。

key的定位：

key 经过哈希计算后得到哈希值，共 64 个 bit 位（64位机，32位机就不讨论了，现在主流都是64位机），计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位。还记得前面提到过的 B 吗？如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。例如，现在有一个 key 经过哈希函数计算后，得到的哈希结果是：

​01010​

再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，这是在寻找已有的 key。最开始桶内还没有 key，新加入的 key 会找到第一个空位放入。

buckets 编号就是桶编号，当两个不同的 key 落在同一个桶中，也就是发生了哈希冲突。冲突的解决手段是用链表法：在 bucket 中，从前往后找到第一个空位。这样，在查找某个 key 时，先找到对应的桶，再去遍历 bucket 中的 key。

​00110​​10010111​

如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。

接下来我们看下底层函数源码：

这里我们再详细分析下key/value值是如何获取的：

bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 个 key 的地址就要在此基础上跨过 i 个 key 的大小；而我们又知道，value 的地址是在所有 key 之后，因此第 i 个 value 的地址还需要加上所有 key 的偏移。

3、赋值操作

接下来我们将分成几个部分去看看底层在赋值的时候，进行了什么操作：

第一阶段：校验和初始化

第二阶段：寻找可插入位和更新既有值

第三阶段：申请新的插入位和插入新值

第四阶段：写入

​mapassign​​PCDATA​

扩容：

关于上文中一直提到的扩容是怎么回事呢，现在我们来具体分析下：

还记得bucket中的topHash字段吗？现在我们来补充知识点minTopHash：当一个 cell 的 tophash 值小于 minTopHash 时，标志这个 cell 的迁移状态。因为这个状态值是放在 tophash 数组里，为了和正常的哈希值区分开，会给 key 计算出来的哈希值一个增量：minTopHash。这样就能区分正常的 top hash 值和表示状态的哈希值。

下面的这几种状态就表征了 bucket 的情况：

为了避免计算出的topHash与minTopHash 冲突，底层做了相关操作：

​O(1)​​装载因子​

​loadFactor := count/(2^B)​

count 就是 map 的元素个数，2^B 表示 bucket 数量。

再来说触发 map 扩容的时机：在向 map 插入新 key 的时候，会进行条件检测，符合下面这 2 个条件，就会触发扩容：

1、装载因子超过阈值，源码里定义的阈值是 6.5

2、overflow 的 bucket 数量过多

​mapassign​

第 1 点：我们知道，每个 bucket 有 8 个空位，在没有溢出，且所有的桶都装满了的情况下，装载因子算出来的结果是 8。因此当装载因子超过 6.5 时，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。

第 2 点：是对第 1 点的补充。就是说在装载因子比较小的情况下，这时候 map 的查找和插入效率也很低，而第 1 点识别不出来这种情况。表面现象就是计算装载因子的分子比较小，即 map 里元素总数少，但是 bucket 数量多（真实分配的 bucket 数量多，包括大量的 overflow bucket）。

不难想像造成这种情况的原因：不停地插入、删除元素。先插入很多元素，导致创建了很多 bucket，但是装载因子达不到第 1 点的临界值，未触发扩容来缓解这种情况。之后，删除元素降低元素总数量，再插入很多元素，导致创建很多的 overflow bucket，但就是不会触犯第 1 点的规定，你能拿我怎么办？overflow bucket 数量太多，导致 key 会很分散，查找插入效率低得吓人，因此出台第 2 点规定。这就像是一座空城，房子很多，但是住户很少，都分散了，找起人来很困难。

对于命中条件 1，2 的限制，都会发生扩容。但是扩容的策略并不相同，毕竟两种条件应对的场景不同。

​2^B​​2^B*2​

对于条件 2，其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。这样，原来，在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间，提高 bucket 利用率，map 的查找和插入效率自然就会提升。

由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果有大量的 key/value 需要搬迁，会非常影响性能。因此 Go map 的扩容采取了一种称为“渐进式”的方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。

​hashGrow()​​growWork()​​growWork()​

几个标志位如下：

再来看看真正执行搬迁工作的 growWork() 函数

搬迁过程evacuate源码：

扩容后，B 增加了 1，意味着 buckets 总数是原来的 2 倍，原来 1 号的桶“裂变”到两个桶，某个 key 在搬迁前后 bucket 序号可能和原来相等，也可能是相比原来加上 2^B（原来的 B 值），取决于 hash 值 第 6 bit 位是 0 还是 1。原理看下图：

4、遍历操作：

理解了上面 bucket 序号的变化，我们就可以回答另一个问题了：为什么遍历 map 是无序的？

遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key。搬迁后，key 的位置发生了重大的变化，有些 key 飞上高枝，有些 key 则原地不动。这样，遍历 map 的结果就不可能按原来的顺序了。当然，如果我就一个 hard code 的 map，我也不会向 map 进行插入删除的操作，按理说每次遍历这样的 map 都会返回一个固定顺序的 key/value 序列吧。的确是这样，但是 Go 杜绝了这种做法，因为这样会给新手程序员带来误解，以为这是一定会发生的事情，在某些情况下，可能会酿成大错。

当然，Go 做得更绝，当我们在遍历 map 时，并不是固定地从 0 号 bucket 开始遍历，每次都是从一个随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个随机序号的 cell 开始遍历。这样，即使你是一个写死的 map，仅仅只是遍历它，也不太可能会返回一个固定序列的 key/value 对了。

​fastrand​​for range map​

5、更新操作：

底层操作原理参考上文

6、删除操作：

​mapdelete​

*func mapdelete(t *maptype, h hmap, key unsafe.Pointer)

​Empty​

7、并发操作

map 并不是一个线程安全的数据结构。同时读写一个 map 是不安全的，如果被检测到，会直接 panic。

​sync.RWMutex。​

解决方法2：使用golang提供的 sync.Map

参考文献：

【2】《解剖Go语言map底层实现》