Golang map 的底层实现
在开发过程中，map是必不可少的数据结构，在Golang中，使用map或多或少会遇到与其他语言不一样的体验，比如访问不存在的元素会返回其类型的空值、map的大小究竟是多少，为什么会报"cannot take the address of"错误，遍历map的随机性等等。
本文希望通过研究map的底层实现，以解答这些疑惑。
基于Golang 1.8.3
1. 数据结构及内存管理
hashmap的定义位于 src/runtime/hashmap.go 中，首先我们看下hashmap和bucket的定义：
type hmap struct {
count int // 元素的个数
flags uint8 // 状态标志
B uint8 // 可以最多容纳 6.5 * 2 ^ B 个元素，6.5为装载因子
noverflow uint16 // 溢出的个数
hash0 uint32 // 哈希种子
buckets unsafe.Pointer // 桶的地址
oldbuckets unsafe.Pointer // 旧桶的地址，用于扩容
nevacuate uintptr // 搬迁进度，小于nevacuate的已经搬迁
overflow *[2]*[]*bmap
}
其中，overflow是一个指针，指向一个元素个数为2的数组，数组的类型是一个指针，指向一个slice，slice的元素是桶(bmap)的地址，这些桶都是溢出桶；为什么有两个？因为Go map在hash冲突过多时，会发生扩容操作，为了不全量搬迁数据，使用了增量搬迁，[0]表示当前使用的溢出桶集合，[1]是在发生扩容时，保存了旧的溢出桶集合；overflow存在的意义在于防止溢出桶被gc。
// A bucket for a Go map.
type bmap struct {
// 每个元素hash值的高8位，如果tophash[0] < minTopHash，表示这个桶的搬迁状态
tophash [bucketCnt]uint8
// 接下来是8个key、8个value，但是我们不能直接看到；为了优化对齐，go采用了key放在一起，value放在一起的存储方式，
// 再接下来是hash冲突发生时，下一个溢出桶的地址
}
tophash的存在是为了快速试错，毕竟只有8位，比较起来会快一点。
从定义可以看出，不同于STL中map以红黑树实现的方式，Golang采用了HashTable的实现，解决冲突采用的是链地址法。也就是说，使用数组+链表来实现map。特别的，对于一个key，几个比较重要的计算公式为:
| key | hash | hashtop | bucket index |
|---|---|---|---|
| key | hash := alg.hash(key, uintptr(h.hash0)) | top := uint8(hash >> (sys.PtrSize*8 - 8)) | bucket := hash & (uintptr(1)<<h.B - 1)，即 hash % 2^B |
例如，对于B = 3，当hash(key) = 4时， hashtop = 0， bucket = 4，当hash(key) = 20时，hashtop = 0， bucket = 4；这个例子我们在搬迁过程还会用到。
内存布局类似于这样：
hashmap-buckets
2. 创建 - makemap
map的创建比较简单，在参数校验之后，需要找到合适的B来申请桶的内存空间，接着便是穿件hmap这个结构，以及对它的初始化。
makemap
3. 访问 - mapaccess
对于给定的一个key，可以通过下面的操作找到它是否存在
image.png
方法定义为
// returns key, if not find, returns nil
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
// returns key and exist. if not find, returns nil, false
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
// returns both key and value. if not find, returns nil, nil
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer)
可见在找不到对应key的情况下，会返回nil
4. 分配 - mapassign
为一个key分配空间的逻辑，大致与查找类似；但增加了写保护和扩容的操作；注意，分配过程和删除过程都没有在oldbuckets中查找，这是因为首先要进行扩容判断和操作；如下：
assign
扩容是整个hashmap的核心算法，我们放在第6部分重点研究。
新建一个溢出桶，并将其拼接在当前桶的尾部，实现了类似链表的操作：
// 获取当前桶的溢出桶
func (b *bmap) overflow(t *maptype) *bmap {
return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))
}
// 设置当前桶的溢出桶
func (h *hmap) setoverflow(t *maptype, b, ovf *bmap) {
h.incrnoverflow()
if t.bucket.kind&kindNoPointers != 0 {
h.createOverflow()
//重点，这里讲溢出桶append到overflow[0]的后面
*h.overflow[0] = append(*h.overflow[0], ovf)
}
*(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf
}
5. 删除 - mapdelete
删除某个key的操作与分配类似，由于hashmap的存储结构是数组+链表，所以真正删除key仅仅是将对应的slot设置为empty，并没有减少内存；如下：
mapdelete
6. 扩容 - growWork
首先，判断是否需要扩容的逻辑是
func (h *hmap) growing() bool {
return h.oldbuckets != nil
}
何时h.oldbuckets不为nil呢？在分配assign逻辑中，当没有位置给key使用，而且满足测试条件(装载因子>6.5或有太多溢出通)时，会触发hashGrow逻辑：
func hashGrow(t *maptype, h *hmap) {
//判断是否需要sameSizeGrow，否则"真"扩
bigger := uint8(1)
if !overLoadFactor(int64(h.count), h.B) {
bigger = 0
h.flags |= sameSizeGrow
}
// 下面将buckets复制给oldbuckets
oldbuckets := h.buckets
newbuckets := newarray(t.bucket, 1<<(h.B+bigger))
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// 更新hmap的变量
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
h.nevacuate = 0
h.noverflow = 0
// 设置溢出桶
if h.overflow != nil {
if h.overflow[1] != nil {
throw("overflow is not nil")
}
// 交换溢出桶
h.overflow[1] = h.overflow[0]
h.overflow[0] = nil
}
}
OK，下面正式进入重点，扩容阶段；在assign和delete操作中，都会触发扩容growWork：
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 搬迁旧桶，这样assign和delete都直接在新桶集合中进行
evacuate(t, h, bucket&h.oldbucketmask())
//再搬迁一次搬迁过程中的桶
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
6.1 搬迁过程
一般来说，新桶数组大小是原来的2倍(在!sameSizeGrow()条件下)，新桶数组前半段可以"类比"为旧桶，对于一个key，搬迁后落入哪一个索引中呢？
假设旧桶数组大小为2^B， 新桶数组大小为2*2^B，对于某个hash值X
若 X & (2^B) == 0，说明 X < 2^B，那么它将落入与旧桶集合相同的索引xi中；
否则，它将落入xi + 2^B中。
例如，对于旧B = 3时，hash1 = 4，hash2 = 20，其搬迁结果类似这样。
example.png
源码中有些变量的命名比较简单，容易扰乱思路，我们注明一下便于理解。
| 变量 | 释义 |
|---|---|
| x *bmap | 桶x表示与在旧桶时相同的位置，即位于新桶前半段 |
| y *bmap | 桶y表示与在旧桶时相同的位置+旧桶数组大小，即位于新桶后半段 |
| xi int | 桶x的slot索引 |
| yi int | 桶y的slot索引 |
| xk unsafe.Pointer | 索引xi对应的key地址 |
| yk unsafe.Pointer | 索引yi对应的key地址 |
| xv unsafe.Pointer | 索引xi对应的value地址 |
| yv unsafe.Pointer | 索引yi对应的value地址 |
搬迁过程如下：
evacuate
总结
到目前为止，Golang的map实现细节已经分析完毕，但不包含迭代器相关操作。通过分析，我们了解了map是由数组+链表实现的HashTable，其大小和B息息相关，同时也了解了map的创建、查询、分配、删除以及扩容搬迁原理。总的来说，Golang通过hashtop快速试错加快了查找过程，利用空间换时间的思想解决了扩容的问题，利用将8个key(8个value)依次放置减少了padding空间等等。
