Go 语言的map 使用 hash 表作为底层实现，一个 Hash 表可以有多个 bucket，而每个 bucket 保存了 map 中的一个或一组键值对。
map的内存模型
map.jpg
type hmap struct {
count i nt // 元素个数
flags uint8
B uint8 // buckets 数组的长度就是 2^B
hash0 uint32
buckets unsafe.Pointer // 指向 buckets 数组，大小为 2^B，如果元素个数为0，就为 nil
oldbuckets unsafe.Pointer // 老旧的 buckets 数据，用来扩容
nevacuate uintptr
extra *mapextra
}
buckets 是一个指针，最终它指向的是一个结构体：
type bmap struct {
tophash [bucketCnt]uint8
}
但这只是表面(src/runtime/hashmap.go)的结构，编译期间会给它加料，动态地创建一个新的结构：
type bmap struct {
topbits [8]uint8
keys [8]keytype
values [8]valuetype
pad uintptr
overflow uintptr // 溢出buckets
}
bmap 就是我们常说的 bucket，元素经过 hash 运算后就会落到某个 bucket 中存储。
image.png
注意到 key-value 不是 ke/value key/value 这样放在一起的，是 key/key/.../value/value/的形式，源码解释是为了可以省掉paddding，节省内存空间。
hash 冲突
-
解决 hash 冲突
当有两个或以上数量的健被 hash 到同一个 bucket 时，就发生了键冲突，Go 用链地址法来解决键冲突，由于每一个bucekt 可以存放8个键值对，所以同一个 bucket 存放超过 8个键值对时就会再创建一个 bucket，用类似的链表的方式将 bucket 连接起来。
image.png
在bucket 的数据结构中使用指针指向溢出的 bucket，意为当前的 bucket 盛不下而溢出的部分，这并不是一件好事，因为它降低了存取效率。
-
负载因子
负载因子用于衡量一个 Hash 表冲突的情况，公式为：对于一个 bucket 数量为4，包含4个键值对的 Hash 表来说，这个 hash 表的负载因子为1，负载因子过小或者过大都不理想：
- 负载因子过小，说明空间利用率低。
- 负载因子过大，说明冲突严重，存取效率低。
当 hash 表负载因子过大时，需要申请更多的 bucket，并对所有键值对重新组织，使其均匀分布到这些 bucket 中，这个过程称为 rehash。每个 hash 表的实现对负载因子容忍程度不同，比如 Redis 的map 实现中负载因子为1 就会触发rehash，而 go 是 6.5，因为 Redis 每个 bucket 只能存1个键值对，而 go 的bucket 可以存 8个键值对。
扩容
-
扩容条件
降低负载因子常用的手段是扩容，为了保证访问效率，当新元素将要添加进 map 时。都会检查是否需要扩容，扩容实际上是以空间换时间的手段。
触发扩容需要满足下列的条件：- 负载因子大于6.5时，即平均每个 bucket 存储的键值对达到 6.5 个以上。
- overflow 的数量达到 2^min(15, B) 时。
-
增量扩容
当负载因子过大时，就新建一个 bucket 数组，新的 bucket 数组的长度是原来的2倍，然后旧的 bucket 数组中的数据搬迁到新的 bucket 数组中。
考虑到如果 map 存储了数以亿计的键值对，那么一次性搬迁会造成比较大的延时，所以 Go 采用逐渐搬迁策略，即每次访问 map 时都会触发一次搬迁，每次搬迁2个键值对。
比如现在有一map，存储了 7个键值对，只有1个bucket，此时负载因子为7，再次添加时会触发扩容操作，扩容之后再将新的键值对写入新的 bucket 中。当添加第8个键值对时，将触发扩容：
image.png
扩容时，先让
hmap中的oldbuckets指向原buckets数组，然后申请新的buckets数组，并将数组指针保存到hmap数据结构的buckets成员中，这样就完成了新老buckets数组的交接，后续的迁移工作将是从oldbuckets数组逐步搬迁键值对到新的buckets数组中，待oldbuckets数组中的所有键值对搬迁完毕后，就可以安全的释放oldbuckets数组。 -
等量扩容
等量扩容，并不是扩大容量，而是 bucket 数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使 bucket 的使用率更高，进而保证更快的存取效率。
key 的查找
查找过程如下：
- 根据 key 值 计算 hash 值
- 取 hash 值低位 与 hmap.B 取模来确定 bucket 的值
- 取 hash 值高位，在 tophash 数组中查询
- 如果 tophash[i] 中存储的 hash值 与当前的 key 的 hash 值相等，则获取 tophash[i] 的 key 值进行比较
- 当前bucket 中没有找到，则从溢出的bucket继续查找
如果当前 map 处于搬迁过程中，那么查找时优先从 oldbuckets 数组中查找。然后再从新的buckets 数组中查找。
key 的添加
新元素添加过程如下：
- 根据 key 的值计算 hash 值
- 取 hash 值低位 与 hmap.B 取模来确定 bucket 的值
- 查找该 key 是否已经存在，如果存在则直接更新值
- 如果该 key 不存在，则从该 bucket 中寻找空余位置并插入
如果当前 map 处于搬迁过程中，那么新元素会直接添加到新的buckets 数组中。
key 的删除
删除元素实际上先查找元素，如果元素存在则把元素从相应的 bucket 中清除，如果不存在则什么都不做。
网友评论