数据结构

type hmap struct {
	count     int // 当前hash表中的元素数量
	flags     uint8
	B         uint8 // B 表示当前哈希表持有的 buckets 数量，但是因为哈希表中桶的数量都 2 的倍数，所以该字段会存储对数，也就是 len(buckets) == 2^B
	noverflow uint16
	hash0     uint32 // 是哈希的种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入

	buckets    unsafe.Pointer
	oldbuckets unsafe.Pointer // 是哈希在扩容时用于保存之前 buckets 的字段，它的大小是当前 buckets 的一半
	nevacuate  uintptr

	extra *mapextra
}

type mapextra struct {
	overflow     *[]*bmap
	oldoverflow  *[]*bmap
	nextOverflow *bmap
}

hmap 字段说明

• count：键值对的数量
• B：表示当前哈希表持有的 buckets 数量，但是因为哈希表中桶的数量都 2 的倍数，所以该字段会存储对数，也就是 len(buckets) == 2^B
• hash0：是哈希的种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入
• buckets：指向数组，类型为[]bmap，正常桶
• oldbuckets：是哈希在扩容时用于保存之前 buckets 的字段，它的大小是当前 buckets 的一半
• extra：溢出桶结构，正常桶里面 bmap 存满了，会使用里面的内存空间存放键值对
• noverflow：溢出桶里面 bmap 大致的数量
• nevacuate：分流次数，成倍扩容分流操作计数的字段(Map 扩容相关字段)
• flags：状态标识，比如正在被写、buckets 和 oldbuckets 在被遍历、等量扩容(Map 扩容相关字段)

核心结构图

bmap 字段说明

• topbits：长度为 8 的数组，[]uint8，元素为：key 获取的 hash 的高 8 位，遍历时对比使用，提高性能
• keys：长度为 8 的数组，[]keytype，元素为：具体的 key 值
• elems：长度为 8 的数组，[]elemtype，元素为：键值对的 key 对应的值
• pad：对齐内存使用的，不是每个 bmap 都有会这个字段，需要满足一定条件
• overflow：指向的 hmap.extra.overflow 溢出桶里的 bmap，上面的字段 topbits、keys、elems 长度为 8，最多存 8 组键值对，存满了就往指向的这个 bmap 里存

==注：每个 bmap 最多存放 8 组键值对==

hmap.extra 字段说明

• overflow：和 hmap.buckets 的类型一样也是数组 []bmap，当正常桶 bmap 存满了的时候就使用 hmap.extra.overflow 的 bmap。
• oldoverflow：扩容时存放之前的 overflow(Map 扩容相关字段)
• nextoverflow：指向溢出桶里下一个可以使用的 bmap

整体结构图

查询

我们结合上面的整体机构图，分析下 map 的查询流程：

1. 当查询 map["name"]的时候，通过 hash 函数获取当前 key 的哈希，通过当前 key 的哈希获取到对应的正常桶 bmap 结构的 b
2. 如果正常桶没找到，找关联的溢出桶，如果没有关联直接返回 nil，如果有关联了还是没找到，直接返回 nil
3. 如果正常桶找到了，对比 key，并返回
4. 如果正常桶没找到，溢出桶找到了，对比 key，并返回

分配

1. 通过 hash 找到对应的 bmap
2. 遍历 bmap，如果已经存在 key 就替换。不存在就找到第一个可以插入的位置
3. 如果正常桶满了，就到溢出桶（没有就创建）重复 2
4. 如果 map 处在扩容的过程中，那么当 key 定位到了某个 bucket 后，需要确保这个 bucket 对应的老 bucket 完成了迁移过程。即老 bucket 里的 key 都要迁移到新的 bucket 中来（分裂到 2 个新 bucket），才能在新的 bucket 中进行插入或者更新的操作。

删除

1. 查找到对应的 key
2. 清除 key。只是修改了当前 key 的标记，而不是直接删除了内存里面的数据。
3. 如果满足扩容的条件，就主动触发一次扩容操作。这之后，整个之前的查找定位 key 的过程，还得再重新走一次。因为扩容之后，key 的分布都发生了变化

扩容

等量扩容

由于 map 中不断的 put 和 delete key，桶中可能会出现很多断断续续的空位，这些空位会导致连接的 bmap 溢出桶很长，导致扫描时间边长。这种扩容实际上是一种整理，把后置位的数据整理到前面。这种情况下，元素会发生重排，但不会换桶

2 倍扩容

这种 2 倍扩容是由于当前桶数组确实不够用了，发生这种扩容时，元素会重排，可能会发生桶迁移。

扩容时机

1. 当分配和删除 key 时会触发 rehash
2. 原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。

map 遍历无序

1. map 在扩容后，会发生 key 的搬迁，原来落在同一个 bucket 中的 key，搬迁后，有些 key 就要远走高飞了（bucket 序号加上了 2^B）。而遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key。搬迁后，key 的位置发生了重大的变化
2. 当我们在遍历 map 时，并不是固定地从 0 号 bucket 开始遍历，每次都是从一个随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个随机序号的 cell 开始遍历

map 并发

1. 由于 map 存在扩容等操作，并发读写会导致 panic
2. 解决办法就是使用锁或者 sync.Map