Golang 底层实现系列——map 的底层实现

本文基于 golang 1.14.13

map 的底层数据结构

map 的底层实现是一个散列表，map 的实现过程实际上就是实现散列表的过程。map 次要蕴含两个构造：hmap和bmap。

hmap 构造：

bmap 构造：

map 的创立

map 的创立通过生成汇编码能够晓得，调用的时 runtime.makemap 创立的。

ps:如果你的 map 初始容量小于等于 8 会发现走的是 runtime.fastrand 是因为容量小于 8 时不须要生成多个桶，一个桶的容量就能够满足（单桶容量通过 bucketCnt 常量定义）。

这里次要阐明 overLoadFactor 这个计算 B 的函数。

func overLoadFactor(count int, B uint8) bool {return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

参数含意：

count：以后 map 容量

B：以后 B 的值

bucketCnt：单个桶数量（默认为 8）

loadFactorNum：13

bucketShift : 1<<B

loadFactorDen：2

当 overLoadFactor 返回 true 时则代表须要扩容,B++。初始时在晓得容量的状况下会间断减少 B 直到 overLoadFactore 返回false。

在申请桶空间时用到的函数是makeBucketArry，这个函数会返回指向多个桶空间数组的第一个元素的指针（buckets）和第一个移除桶的指针（nextOverflow）。

<center> 桶及溢出桶的散布 </center>

如上图（桶及溢出桶的分布图），makeBucketArry实际上就是从内存中申请了一个间断的空间内存，内存大小为bucket.size * buckets 总数（根底桶和溢出桶），其中前局部是根底桶（baseBucket）而后是溢出桶。

map 的赋值

map 的赋值会附带着 map 的扩容和迁徙，这两局部是 map 底层实现的要害，会在前面来独自说，除去这两局部的话，map 赋值绝对简略，次要是一个 hash 分为两局部（低位 bash 和高位 hash）低位用于查找 bucket，而后 tophash 疾速判断 bucket 中各个地位是为空。找到 key 对应的地位，而后设置 key 及 elem（如果 key 曾经存在则会间接返回 elem 的地位，汇编底层会将值赋值到 elem 对应地位）。

有一点须要特地留神，bmap 中的 key/value 是如下图这样散布的：

其中 dataOffset 为 bmap 构造的大小。

漏了一个问题：当查找到所有桶发现没有可插入地位时，阐明所有的桶都满了，须要申请一个溢出桶（可能是事后申请好的，也可能须要从新申请），并且将溢出桶接到以后 bucket 的前面（如果已有溢出桶则为最初一个溢出桶的前面）

map 的删除

map 的删除调用的时 mapdelete 函数。

删除的逻辑绝对比较简单，大多函数在赋值操作中曾经用到过，所以这里只列除了一些特有的代码（删除数据）。

map 的查问

map 的查问调用的是 mapaccess 函数。

查问这里次要有一个在扩容过程中查问时须要确认以后 key 是否曾经迁徙到新的 bucket 中。次要是通过 bmap.tophash 来确认。

map 的扩容

map 的扩容有量中状况：

第一种：容量有余，“以后容量 +1”之后计算出来扩容因子超出了规定值，即 overLoadFactr 函数返回 true；

第二种：溢出桶过多。溢出桶数量 ≥（B&15）。

注：这里的扩容因子的规定值是一个定值，是通过教训得出的论断，咱们不做探讨。

当是第一种扩容时，会将 map 容量扩充一倍。如果是第二种状况则代表可能是空的 kv 占用的空间过多，这次的扩容不会拓展空间，buckets 的数量和原来是一样的然而会对 map 中的 kv 进行整顿，去除空的 kv。

map 的扩容只是将底层数组扩充了一倍，并没有进行数据的转移，数据的转移是在扩容后逐渐进行的，在迁徙的过程中每进行一次赋值（access 或者 delete）会至多做一次迁徙工作。

map 的迁徙

在 map 的赋值与删除中咱们都有说道迁徙，这是扩容后的一部分，迁徙的根底构造是 evacDst 数据结构如下：

整个迁徙的流程如下：

注：这里只是简略的举例子，理论中 hash 值不能够小于 5，因为小于 5 的 hash 都被用于 tophash 的标识。

总结

1. map 的赋值难点在于数据的扩容和数据的迁徙操作
2. bucket 迁徙是逐渐进行的，在迁徙的过程中每进行一次赋值，会做至多一次迁徙工作。
3. 扩容不肯定会减少空间，也可能只是做了内存整理
4. tophash 的标记即能够判断是否为空也能够半段是否搬迁，以及搬迁的地位。
5. 从 map 中删除 key，有可能导致呈现很多空的 kv，这会导致迁徙操作，如果能够防止，尽量避免。

参考文章

深刻了解 Go map：赋值和扩容迁徙
Golang map 底层实现原理解析
Golang Map 实现
golang map 的底层实现
Go 语言 map 底层实现