【Go进阶—数据结构】map golang

哈希表是除了数组之外，最常见的数据结构。Go 语言中的 map 底层就是哈希表，可以很方便地提供键值对的映射。
特性
未初始化的 map 的值为 nil，向值为 nil 的 map 添加元素会触发 panic，这是新手容易犯的错误之一。
map 操作不是原子的，多个协程同时操作 map 时有可能产生读写冲突，此时会触发 panic 导致程序退出。如果需要并发读写，可以使用锁来保护 map，也可以使用标准库 sync 包中的 sync.Map。
实现原理
数据结构 map 的底层数据结构由 runtime/map.go/hmap 定义：

type hmap struct { countint// 元素个数，调用 len(map) 时，直接返回此值 flagsuint8 Buint8// buckets 数组长度的对数 noverflow uint16// overflow 的 bucket 近似数 hash0uint32// 哈希种子，为哈希函数的结果引入随机性，在调用哈希函数时作为参数传入bucketsunsafe.Pointer // 指向 buckets 数组，大小为 2^B，元素个数为0时为 nil oldbuckets unsafe.Pointer // 在扩容时用于保存旧 buckets 数组，大小为 buckets 的一半 nevacuateuintptr// 指示扩容进度，小于此地址的 buckets 都已迁移完成 extra *mapextra// 附加项 }

buckets 数组中保存了 bucket 的指针，bucket 很多时候被翻译为桶，它是 map 键值对的真正载体。它的数据结构定义如下：

type bmap struct { tophash [bucketCnt]uint8// 存储键的 hash 值的高 8 位 }

在运行期间，bmap 结构体其实不止包含 tophash 字段，因为哈希表中可能存储不同类型的键值对，而且 Go 语言（1.17之前）也不支持泛型，所以键值对占据的内存空间大小只能在编译时进行推导。bmap 中的其他字段在运行时也都是通过计算内存地址的方式访问的，所以它的定义中就不包含这些字段。在运行时，bmap 摇身一变，成了下面的样子：

type bmap struct { topbits[8]uint8 keys[8]keytype values[8]valuetype paduintptr overflow uintptr }

整体的 map 结构图大致如下所示：

文章图片

bmap 的内部组成类似于下图：

文章图片

HOB Hash 指的就是 top hash。key 和 value 是各自放在一起的，并不是 key/value/key/value/... 这样的形式。这样的好处是在某些情况下可以省略掉 padding 字段，节省内存空间。
每个 bucket 设计成最多只能放 8 个 key-value 对，如果有第 9 个 key-value 落入当前的 bucket，那就需要再构建一个 bucket，通过 overflow 指针连接起来。
相关操作查找 key 经过哈希计算后得到哈希值，共 64 个 bit 位，计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位。还记得前面提到过的 B 吗？B 等于桶的数量，也就是 buckets 数组长度的对数。
例如，现在有一个 key 经过哈希函数计算后，得到的哈希结果是：

10010111 | 000011110110110010001111001010100010010110010101010 │ 00110

用最后的 5 个 bit 位，也就是 00110，定位到 6 号桶。这个操作实际上就是取余操作，但是取余开销太大，所以代码实现上用位操作代替。再用哈希值的高 8 位，找到此 key 在 bucket 中的位置。如下图所示：

文章图片

因为可能存在哈希冲突，所以在定位到 key 在 bucket 中的位置后，还需要获取对应的 key 值与待查询的 key 进行比较，不相等的话则继续上面的定位过程。如果在当前的 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了。如果未找到，也不会返回 nil，而是返回相应类型的零值。
注：如果当前处于搬迁过程（扩容），则优先从 oldbuckets 中查找。
赋值赋值操作最终调用的是 mapassign 函数，它的初始流程和上面介绍的查找类似，也是通过 key 找到对应的 bucket 中的位置。准备两个指针，一个（inserti）指向 key 的 hash 值在 tophash 数组所处的位置，另一个 (insertk) 指向 cell 的位置（也就是 key 最终放置的地址）。在循环的过程中，inserti 和 insertk 分别指向第一个找到的空闲的 cell，如果最终没有找到 key 的话，就在此位置插入。如果当前桶已经满了，会调用 newoverflow 创建新桶或者使用 hmap 预先在 noverflow 中创建好的桶来保存数据，新创建的桶不仅会被追加到已有桶的末尾，还会增加 hmap 的 noverflow 计数器。
如果当前 key 在 map 中存在，那么就会直接返回目标区域的内存地址；如果不存在，则会为新键值对规划存储的内存地址，通过 typedmemmove 将键移动到对应的内存空间中并返回键对应值的地址。map 并不会在 mapassign 这个运行时函数中将值拷贝到桶中，该函数只会返回内存地址，真正的赋值操作是在编译期间插入的。
扩容前面在介绍 map 的写入过程时其实省略了扩容操作，随着 map 中元素的逐渐增加，性能会逐渐恶化，所以需要更多的桶和更大的内存保证 map 的性能。在向 map 插入新 key 的时候，会进行条件检测，符合的话就会触发扩容：

if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) { hashGrow(t, h) goto again }func overLoadFactor(count int, B uint8) bool { return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen) }func tooManyOverflowBuckets(noverflow uint16, B uint8) bool { if B > 15 { B = 15 } return noverflow >= uint16(1)<<(B&15) }

由源码可以看出，触发扩容的条件为下面二者之一：

装载因子超过阈值，源码里定义的阈值是 6.5；
overflow 的 bucket 数量过多：当 B 小于 15，也即 bucket 总数小于 2^15 时，overflow 的 bucket 数量超过 2^B；当 B >= 15，也即 bucket 总数大于等于 2^15时，overflow 的 bucket 数量超过 2^15。

对于条件一，说明 bucket 数量太少，此时需要扩充 bucket 的数量，称之为增量扩容；对于条件二，说明 bucket 里面键值对太稀疏，此时并不需要扩充 bucket 的数量，称之为等量扩容。无论是那种情况，都需要开辟一个新的 bucket 数组，将旧的 bucket 数组中的键值对移动到新的中来，只不过增量扩容时 bucket 的数量变为了之前的 2 倍。我们来看下扩容的入口 hashGrow 函数的核心代码：

func hashGrow(t *maptype, h *hmap) { bigger := uint8(1) if !overLoadFactor(h.count+1, h.B) { bigger = 0 h.flags |= sameSizeGrow } oldbuckets := h.buckets newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)h.B += bigger h.flags = flags h.oldbuckets = oldbuckets h.buckets = newbuckets h.nevacuate = 0 h.noverflow = 0... }

我们可以看到，hashGrow 函数只是分配好了新的 buckets，并将老的 buckets 挂到了 oldbuckets 字段上，并没有真正地迁移数据。这是因为如果有大量的键值对需要迁移，会非常影响性能。因此 map 的扩容采取了一种“渐进式”的方式，原有的 key 并不会一次性迁移完毕，每次最多只会迁移 2 个 bucket。在插入或修改、删除 key 的时候，都会先检查 oldbuckets 是否迁移完毕，具体来说就是检查 oldbuckets 是否为 nil。如果为假则执行迁移，也即调用 growWork 函数。growWork 函数的代码如下：

func growWork(t *maptype, h *hmap, bucket uintptr) { evacuate(t, h, bucket&h.oldbucketmask())if h.growing() { evacuate(t, h, h.nevacuate) } }

【【Go进阶—数据结构】map】evacuate 函数就是执行迁移的函数，它会对传入桶中的元素进行再分配，大致逻辑如下：该函数会创建用于保存分配上下文的 evacDst 结构体，等量扩容只会创建一个，增量扩容则会创建两个，每个 evacDst 分别指向一个新桶。等量扩容的话，每个 key 都迁移到和之前同一序号的桶中；增量扩容的话，会根据哈希值和新的掩码分流到两个桶中。最后会增加 map 的 nevacuate 计数器并在所有的旧桶都被分流后清空 map 的 oldbuckets 和 oldoverflow。