摘要
map 通过 hasTable 实现了我们最常见的 key-value 存储，能快速的对数据集增删查改。同时 Go 里的 map 也有很多特殊的地方，比如它的无序性、并发不安全等。今天，就让我们对 map 进行深入研究，看看它是怎么设计的。
map 基本认识
当我们用 dataMap := make(map[int]string)创建一个 map 对象的时候，得到的是一个 hmap 指针结构。通过对 src/runtime/map.go文件分析，我们看到了对应的结构体如下：
type hmap struct {
count int // 当前的元素个数
flags uint8
B uint8 // 字段 buckets 数组的长度关联参数，即 buckets 长度为 2^B
noverflow uint16 // overflow buckets 的近似数
hash0 uint32 // 哈希种子，作 hash 运算用的
buckets unsafe.Pointer // 数组对象，存 key-value的
oldbuckets unsafe.Pointer // 扩容时用到的 buckets，大小是之前 buckets 的一半。
nevacuate uintptr // 扩容进度
extra *mapextra // optional fields
}
在这里面，有一个非常关键的字段： buckets，它就是用来存储 key-value 的。
当 Go 对 key 进行 hash 运算后，会通过一定的规则映射到 buckets 的某个位置，然后就会将 key、value 一起存在这个对应位置的桶里。
而这个桶实际上会指向下面这个结构体：
type bmap struct {
tophash [bucketCnt]uint8
}
之所以会这么简洁，是因为 map 是在编译时才知道对应的 key-value 类型的，所以对于 map[string]int 这样的 map 在编译过后，bmap 最终会变成这样的结构体：
type bmap struct {
tophash [bucketCnt]uint8
keys [bucketCnt]string
values [bucketCnt]int
overflow *bmap
}
在这里，就有一个 keys，values 数组来存储 key-value 了，其中还有个 tophash 数组，可以先认为它是用来定位 key-value 在对应数组里的存储位置，后面会详细说明它的定位过程。
现在我们大概知道了 key-value 在 map 里的存储走向了：
深入认识 map
map 的存储
接下来，我们来看看 map 存储 key-value 时的具体动作。
首先在程序初始化时，Go 会为 hmap 找到一个合适的 B 值，以创建合适大小的 buckets 数组。
假设 B = 5，则此时 hmap 的 buckets 桶数量为 2^5 = 32。
当我们往 map 添加一个 key 时，Go 会对 key 进行 hash 计算，得到一个 hash 值。
在得到这个 hash 值后，会取它的低 5 位，作为定位到 buckets 数组里某个 bucket 的索引位置。
这里解释下为何取低 5 位，这里的 5 即是 hmap 的 B 值。 假设低 5 位都是 11111，那么最大值也只会是 31，不超过桶的数量，有点类似取余的操作，这样就不会有越界行为了。
hashCode := hash(key, h.hash0) // 获取 key 的 hash 值
bucketIndex := hashCode & 0x1F // 利用位运算取低 B 位，定位到桶的位置
当我们定位到桶的位置后，后面就是存放 key-value 了。
Go 会继续对 hash 值 取高 8 位，得到一个 top hash 值。然后遍历 bmap 里的 tophash 数组，找到一个空的位置存放。
这里之所以要存储 top hash 值，除了下次找 key 时会先对比下 top hash，还添加了一些扩容进度的状态位，辅助 map 的扩容。
需要注意的是，bmap 的 tophash 数组也是有固定大小的，即 bucketCnt = 8，最多存放 8 个元素。
一旦超过这个数量，则会再创建一个 bmap 对象，通过 overflow 字段指向新的 bmap，这样就又可以存放 8 个元素了。
当确定好在 tophash 的位置后，就可以用这个索引位置也作为 key，value 在 keys，values 数组的位置了，此时 key、value 就存储起来了。
map 的读取
map 的读取基本上也是按上面的流程来进行。同样的对 key 进行 hash 运算，然后取低 B 位，以确定 key 在桶里的位置。
当得到桶的位置后，会继续取 hash 值的高 8 位得到 top hash，然后遍历 tophash 数组，寻找到 top hash 元素的 index 位置。
如果当前找不到，但 overflow 不为空，则继续到 overflow 里寻找 index 位置。
当找到 top hash 的 index 位置后，也就确定了 key 在 keys 数组里的索引位置了，此时会再比较一下是否跟想寻找的 key 相等。
如果相等，则说明找到 key 了，就可以到 values 数组上的相同 index 位置提取 value 了。
如果不一样，则说明还得继续遍历寻找，直到没有元素，也没有 overflow 可继续遍历。
总的存取流程如下：
深入认识 map
上面提到一个 key 的比较过程，所以这里注定了 key 是一个可比较类型，像 int，string 等基础类型是可以作为 key 的。如果是 slice，map，channel 这种不可比较类型，则不能作为 key 来使用了。
map 的扩容
map 之所以能快速的存取元素，是因为用 hash table 快速的进行数组位置的映射。
然而如果出现过多的 hash 冲突，即有多个 key 映射到同一个桶里，就得在读取时进行遍历 bmap 的动作，最差的情况下时间复杂度将达到 O(n)。
因此当 map 的元素过多，超过一定的阈值后，就应该对 map 的数据元素进行重整，平衡数据的读取速度。
Go 通过扩容来实现了数据的读取平衡，在添加或删除数据时，会先判断装载因子的值是否达到扩容要求，达到了则进行扩容动作。
装载因子的计算方式如下：
loadFactor := count / (2^B)
count 指的是当前 map 里的元素个数，2^B 是指当前 map 里 buckets 数组长度，从这可以看出元素越来越多，即 count 越来越大，则越可能触发扩容。
map 除了判断装载因子来进行扩容外，还有另外一种情况也会进行数据重整：overflow 数量过多，但元素很少。这种情况的产生，是因为出现了大量数据的插入和删除，导致 overflow 不能回收，所以也要进行数据重整。
我们重点来看看第一种情况的扩容过程。首先，hmap 会先增加 B 的值，也就是 buckets 数组的数量。然后，重新计算 key 所需要迁移的桶的位置，以便让数据能均衡的分布在新老 buckets 桶里。
当然，Go 并不会一下子就把所有的数据都迁移完毕，而是等到用到某个 key 时，检查此时 key 的迁移状态，再作出迁移动作。
从上面的扩容过程我们也可以看出为什么 map 是无序的了，因为原本在一个 bucket 上的数据有可能被迁移到其他的 bucket 上了，会被打乱顺序。
当然，Go 官方也可以将 key 全部获取到后做排序动作，但显然 Go 官方不想这么做，想明明白白的告诉开发者，map 的实现就是 hash 无序的。
对于第二种情况的数据重整，就比较简单了。只要在当前 bucket 里收缩各个 overflow 到空位上即可。
其他特性
1）并发不安全：map 在进行读取 key 的时候会检查当前的 hmap.flags 字段，如果发现该值是一个写状态值的话，则会直接 panic。
2）当使用 float 作为 map 的 key 时，由于 float 精度问题，会出现获取不到 float key 对应 value 的情况，所以应该慎用 float 作为 key。
总结
Go 里的 map 设计的比较精巧，通过获取 hash 值，并且对 hash 值进行低位运算来找到对应的 bucket，接着再利用 hash 值的高几位，来确定 key 在 bucket 里的具体位置。
而且 map 在扩容时也是懒扩容的，并不会一次性阻塞在迁移过程。
当然，map 的并发不安全也是我们需要注意的，以免程序 pannic。
以上大概就是 map 的精髓所在了！
感兴趣的朋友可以搜一搜公众号「 阅新技术 」，关注更多的推送文章。
可以的话，就顺便点个赞、留个言、分享下，感谢各位支持！
阅新技术，阅读更多的新知识。
网友评论