Go语言修炼（三）：Go语言中的Map到底是怎么实现的
前言
在编程的世界里，数据结构是构建高效、可维护软件大厦的基石。而在众多数据结构中，Map（哈希表）因其能够快速存取键值对的能力而备受青睐。对于使用Go语言进行开发的程序员来说，Map更是日常编码中不可或缺的一部分。它允许我们以近乎常数的时间复杂度（O(1)）来查找、插入或删除元素，极大地提升了程序的性能。
本文我们将深入探索Go语言中Map到底是如何被实现的，以及它背后的设计哲学与机制。
实现Map的基本方案
一般来讲，实现Map（哈希表）的基本方式有两种（严格来讲是处理哈希冲突的方式）：开放寻址法和拉链法。（PS：本文主要讲解Go语言中Map的实现，因此不会重新讲述像哈希函数等基础知识。）
开放寻址法的核心思想是依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表中，当我们向当前哈希表写入新的数据时，如果发生了冲突，就会将键值对写入到下一个索引不为空的位置。开放寻址法实现中，哈希表用一个数组进行实现。
拉链法是哈希表最常见的实现方法，大多数的编程语言都用拉链法实现哈希表，实现拉链法一般会使用数组加上链表（如下图），不过一些编程语言会在拉链法的哈希中引入红黑树以优化性能（如Java的HashMap），拉链法会使用链表数组作为哈希底层的数据结构，我们可以将它看成可以扩展的二维数组：
Go语言Map的底层结构
Map的底层在runtime/map.go中，代码如下：
type hmap struct {
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
其中mapextra的结构如下：
// mapextra holds fields that are not present on all maps.
type mapextra struct {
overflow *[]*bmap
oldoverflow *[]*bmap
// nextOverflow holds a pointer to a free overflow bucket.
nextOverflow *bmap
}
bmap的结构如下，每个bmap表示一个桶，里面存放8个数据：
- tophash：哈希值的前8位
- key：键（没在代码中，在编译时候加入）
- elem：值（没在代码中，在编译时候加入）
- overflow：溢出指针（没在代码中，在编译时候加入）
type bmap struct {
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
tophash [bucketCnt]uint8
// Followed by bucketCnt keys and then bucketCnt elems.
// NOTE: packing all the keys together and then all the elems together makes the
// code a bit more complicated than alternating key/elem/key/elem/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
hmap中的关键字段如下，我们可以画个图表示map的结构。
- count：key的数量
- B：桶数量的以2为底的对数，后面的算法要用到。
- hash0：哈希种子，用于计算哈希值。
- oldbuckets：指向旧桶的数据，用于扩容。
- buckets：桶的数组。
Map的创建
make初始化
map的创建是在makemap函数中。函数的大致执行过程如下：
- 初始化一个hmap
- 计算hash0、B
- 使用
makeBucketArray创建桶数组和一些溢出桶。存放到extra结构体。- nextOverflow指针指向下一个可用的溢出桶
字面量初始化
字面量初始化写法：
hash := map[string]int {
"1" : 2,
"2" : 3,
}
字面量初始化时，当元素个数小于25，会转化为简单赋值。相当于先用make创建map，然后使用赋值语句写入对应的键值对。当元素个数大于25，会转化为循环赋值。
Map的访问
前面说过，Golang用链表法来实现hashmap。每一个桶存储了哈希的前8位，也就是tophash，如果桶超出8个数据，就会存储到溢出桶中。基于此，我们来看map的访问流程：
map的访问流程为：
- 先根据hash0和key哈希值。
- 然后取哈希值二进制的后B位作为桶号，取哈希值前8位作为tophash号进行匹配。
- 如果是匹配上了（tophash和key都对的上），就访问。
- 如果发生哈希碰撞，就继续匹配下一个。
map的写入
也是先算出桶号和tophash，然后去匹配tophash和key，如果匹配到了就修改，如果没有就插入一个新的key、tophash和elem。
Map的扩容
为何需要扩容
我们回到上面那张hmap结构体的图。假设B=2，此时buckets中有4个bmap是正常桶，同时还会创建一定数量的溢出桶。
当我们的哈希碰撞频率很高时，正常桶bmap存放的数据可能会超过8个，此时这个bmap的数据需要放到溢出桶，也就是其overflow指针指向的下一个bmap。
当溢出桶接着溢出的时候，会继续指向后面的溢出桶，以此类推......当溢出桶的个数过多的时候，我们的查找变成了一个链表，操作效率大大降低，性能下降。此时就需要map的扩容。
扩容步骤
在runtime.mapassign()方法中，我们可以知道以下触发扩容的情况：
- 装载因子超过6.5（平均每个哈希槽6.5key）
- 使用了太多的溢出桶，导致溢出桶数量超过普通桶
扩容类型
map扩容有两种类型：
- 等量扩容：整理。
- 原因：溢出桶很多，但是数据没有很多。（曾经很多，后面被删了，导致溢出桶很稀疏）
- 翻倍扩容：增加普通桶的数量。
扩容步骤
扩容的函数在runtime/map.go中的hashgrow()方法，我们总结一下扩容的步骤：
第一步：创建一组新桶。
将oldbuckets指针指向原来的桶数组。buckets指向新的桶。（这里也会更改extra为新的）同时将map标记为扩容状态。
第二步：将所有数据从旧桶驱逐到新桶。
Go采用渐进式驱逐到方法，即每次操作一个旧桶的时候，将旧桶数据驱逐到新桶。
需要注意的是，读取的时候是不驱逐数据的，只判断是读旧桶还是新桶。当mapassign方法中判断出当前map是扩容状态，就会进入evacuate()方法（意思是驱逐），将老桶的数据驱逐到新桶。
具体来说，会计算出新的B，假设原来B=2，经过扩容后B=3，那么倒数第三位是0还是1就决定了把桶的数据放到010还是110号桶（见下图），**这就实现了把旧桶数据平均分到两个新桶**。
第三步：当所有旧桶的数据驱逐完毕，则可以回收oldbuckets
完成这三步，就是完整的map扩容过程。
小结
本文介绍了实现Map的基本方案、Go语言中Map的底层结构、Map的访问和Map的扩容等内容。
- Go 语言使用拉链法来解决哈希碰撞的问题实现了哈希表。
- 哈希在每一个桶中存储键对应哈希的前 8 位，当对哈希进行操作时，这些
tophash就成为可以帮助哈希快速遍历桶中元素的缓存。 - 哈希表的每个桶都只能存储 8 个键值对，一旦当前哈希的某个桶超出 8 个，新的键值对就会存储到哈希的溢出桶中。
- 随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围就会触发扩容。
- 扩容采用的是渐进式扩容，即元素再分配的过程也是在调用写操作时增量进行的，不会造成性能的瞬时巨大抖动。
