共计 3297 个字符，预计需要花费 9 分钟才能阅读完成。
摘要
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 存储 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 可持续遍历。
总的存取流程如下：
下面提到一个 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 的精华所在了！
感兴趣的敌人能够搜一搜公众号「阅新技术」，关注更多的推送文章。
能够的话，就顺便点个赞、留个言、分享下，感激各位反对！
阅新技术，浏览更多的新常识。
