一、map 简介

1、map 特性

• 基于 key-val 存储

• 基于 key 的维度的存储去重

• 读写和删除，复杂度 o(1)

2、go map 基本操作

myMap1 := make(map[string]string, 10)	myMap2 := make(map[string]string)	myMap3 := map[string]string{		"key1": "val1",		"key2": "val2",	}	fmt.Println(len(myMap1)) //len=0,cap=10	fmt.Println(len(myMap2)) //len=0,cap=0	fmt.Println(len(myMap3)) //len=2,cap=2
	fmt.Println(myMap3["key3"]) //读取不存在的key，返回类型零值	delete(myMap3, "key3")      //删除不存在的key，不会报错	//对未初始化的map操作会直接panic
	//map的遍历,无顺序的，每次打印key的顺序可能不同	for k, v := range myMap3 {		fmt.Println(fmt.Sprintf("k=%v,v=%v", k, v)) //读取不存在的key，返回类型零值	}

3、map 中 key 的类型

• key 类型必须为可比较类型，例如：

布尔值、数字、字符串、指针、通道（待考究）、接口类型、结构体、只包含上述类型的数组。

• 例如切片、map、func 等不能是 key 的类型

4、并发读写

• map 不支持并发读写（写操作包括广义的更新和删除操作）

• go 检测到在读的同时，有并发写，会抛出 ：fatal("concurrent map read and map write")（fatal error 是很严重的错误，无法被 recover）

• go 检测到在写的同时，有并发写，会抛出 ：fatal("concurrent map writes")

5、go map 底层结构

• 底层是一个 hmap 结构体，结构体各字段定义如下:

type hmap struct {    count     int //k-v总数    flags     uint8 //状态位，标记是否并发读写    B         uint8  //桶数组长度指数，表示桶数组长度为 2^B    noverflow uint16 //map中溢出桶的数量    hash0     uint32 //随机hash因子，生产key hash的时候用到    buckets    unsafe.Pointer //桶数组    oldbuckets unsafe.Pointer //扩容时，老桶数组    nevacuate  uintptr //扩容时的进度标识，index 小于 nevacuate 的桶都已经由老桶转移到新桶中；    extra *mapextra //预申请的溢出桶}

• hmap 结构图

、

二、map 各流程剖析

1、初始化流程

1. 基于预分配容量 hint 预估空间大小

2. 判断 map 容量是否过大，是则将 hint 设置为 0，B 也是 0，否则按照 hint 计算出 B 大小

3. 根据 B 初始化桶数组，如果太长会预先初始化溢出桶，最后返回 map

4. 在初始化桶数组的时候，会保证：

• 若预分配容量小于 8，则 B 取 0，桶数为 1

• 保证预分配容量小于桶数组*6.5

• kv 数量、桶数组长度关系表：

2、读流程

1. 判断 map 是否已初始化或者 count 是否为 0，是则提前返回零值

2. 判断 flags 字段，是否存在并发写，是则返回 fatal error

3. 根据 key 计算出 hash，根据 hash 定位到 key 对应哪号桶

4. 在取桶的时候，会额外判断 map 是否在扩容，如是，会额外调用 evacuated 方法判断数据是否已完全迁移到新桶（oldbuckets 不是 nil 则证明 map 在发生迁移）

5. 确认桶后，根据 tophash 去匹配遍历桶内的所有 key，找到 key 则提前返回，若找到是一个空位，则额外判断 emptyRest 标记位是否成立，是则代码这个位置后面的所有桶凹槽都是空的，可以提前返回 key 不存在，返回零值

6. emptyRest 是在删除流程维护的一个特殊标记位，目的是加速读写检索判断

3、写流程

1. 判断 map 是否被初始化，否则 panic

2. 判断是否有并发写，有则 fatal error，无则添加 flag 写标记

3. 根据 key 求出 hash，根据 hash 找到对应的桶

4. 判断 map 是否在扩容，是则辅助命中的 bucket 进行迁移

5. 辅助扩容完后，继续遍历桶找到对应 key（在遍历的时候会标记找到的第一个桶空槽），有找到则更新，并清楚写标记，结束返回

6. 遍历完没找到对应 key，遍历过程中有找到空巢，直接插入，清楚写标记并返回，没找到空巢，则新增溢出桶中插入，判断是否需要扩容，不需要则清楚写标记并返回

7. 若上述需要扩容，则进入扩容流程，扩容后返回第 3 步

4、删除流程

1. 判断 map 是否被初始化，否则直接返回，是则继续

2. 判断 map 是否在并发写，是则直接 fatal erro，否则继续

3. 根据 key 计算 hash，根据 hash 定位桶（和读写操作一下），判断 map 是否在库容

4. 若是在扩容，则辅助扩容迁移，完成后台重复第 3 步

5. 若不是在扩容，则遍历桶找到对应 k-v 则删除，当前位置的 tophash 置为 emptyOne。若当前为末位或者下一位的 tophash 为 emptyRest，则置当前 tophash 置为 emptyRest，并沿路往前遍历，把相邻的 emptyOne 置为 emptyRest（为了读写加速 key 匹配而设置的一个标志位）

5、遍历流程

1. map 遍历开始时，随机选择桶数组中的随机 key 开始遍历

2. 遍历中遇到 oldbuckets，也会映射按照迁移后新桶的顺序遍历

3. map 每次遍历 key 的顺序是乱序的，这个是因为:

• 遍历起点是随机的

• 扩容后 key 存在的位置会发生一定的变化

6、扩容流程

扩容流程

渐进式迁移

1. 扩容时分 2 种，一个增量扩容，一个等量扩容

2. 增量扩容：kv 对大于 8 且数量大于桶数组的 6.5 倍触发，目的是降低每个桶数组的桶数量，提高 map 操作时间复杂度

3. 等量扩容：溢出桶数量大于等于桶数组时触发，目的是整理内部空闲的桶凹槽，提高填充率，减少溢出桶数量，避免内存泄漏

4. 只有写操作才可能触发扩容

5. 渐进式扩容：每次写操作/删除操作会辅助迁移当前 bucket 和未迁移桶中 index 最少的桶

三、map 总结

1. map 的遍历是无序的

2. map 删除 key 的时候并不会回收内存空间，所以在应用大 map 的时候要特别注意维护，否则很容易出现内存涨满等问题

3. map 不是并发安全的