map 实现原理

map并发不安全

# map数据结构

map使用哈希表作为底层实现，一个哈希表里可以有多个哈希表节点，也即bucket，而每个bucket就保存了map中的一个或一组键值对。
bucket很多时候被翻译为桶，所谓的哈希桶实际上就是bucket。

runtime/map.go:hmap

type hmap struct {
    count     int // 当前保存的元素个数
    ...
    B         uint8
    ...
    buckets    unsafe.Pointer // bucket数组指针，数组的大小为2^B
    ...
}

1
2
3
4
5
6
7
8

hmap.B=2，而hmap.buckets长度是2^B为4. 元素经过哈希运算后会落到某个bucket中进行存储。

# bucket 数据结构

bucket很多时候被翻译为桶，所谓的哈希桶实际上就是bucket。
runtime/map.go:bmap
每个bucket可以存储8个键值对。
tophash是个长度为8的数组，哈希值相同的键（准确的说是哈希值低位相同的键）存入当前bucket时会将哈希值的高位存储在该数组中，以方便后续匹配。
data区存放的是key-value数据，存放顺序是key/key/key/…value/value/value，如此存放是为了节省字节对齐带来的空间浪费。
overflow 指针指向的是下一个bucket，据此将所有冲突的键连接起来。
注意：上述中data和overflow并不是在结构体中显示定义的，而是直接通过指针运算进行访问

# hash 冲突

**Hash叫做”*散列表*“，就是把**任意长度**的输入，通过散列算法，变成*固定长度*输出，该输出结果是散列值。
根据key（键）即经过一个函数f(key)得到的结果的作为地址去存放当前的key value键值对(这个是hashmap的存值方式)，但是却发现算出来的地址上已经被占用了。这就是hash冲突。

# 1. hash冲突解决办法

再散列法 (开放定址法)
- 该方法也叫做再散列法，其基本原理是：当关键字key的哈希地址p=H（key）出现冲突时，以p为基础，产生另一个哈希地址p1，如果p1仍然冲突，再以p为基础，产生另一个哈希地址p2，…，直到找出一个不冲突的哈希地址pi 。
再hash法
- 这种方法就是同时构造多个不同的哈希函数： Hi=RH1（key） i=1，2，…，k。当哈希地址Hi=RH1（key）发生冲突时，再计算Hi=RH2（key）……，直到冲突不再产生。这种方法不易产生聚集，但增加了计算时间。
链地址法
- 将所有哈希地址为i的元素构成一个称为同义词链的单链表，并将单链表的头指针存在哈希表的第i个单元中，因而查找、插入和删除主要在同义词链中进行。链地址法适用于经常进行插入和删除的情况。
建立公共溢出区
- 将哈希表分为基本表和溢出表两部分，凡是和基本表发生冲突的元素，一律填入溢出表。

# 2. go map解决hash冲突

Go使用链地址法来解决键冲突
由于每个bucket可以存放8个键值对，所以同一个bucket存放超过8个键值对时就会再创建一个键值对，用类似链表的方式将bucket连接起来。
bucket数据结构指示下一个bucket的指针称为overflow bucket，意为当前bucket盛不下而溢出的部分。

# hash表负载因子

负载因子用于衡量一个哈希表冲突情况，公式为：
```
负载因子 = 键数量/bucket数量
```
1
例如，对于一个bucket数量为4，包含4个键值对的哈希表来说，这个哈希表的负载因子为1.
哈希表需要将负载因子控制在合适的大小，超过其阀值需要进行rehash，也即键值对重新组织：
- 哈希因子过小，说明空间利用率低
- 哈希因子过大，说明冲突严重，存取效率低
每个哈希表的实现对负载因子容忍程度不同，比如Redis实现中负载因子大于1时就会触发rehash，而Go则在在负载因子达到6.5时才会触发rehash，因为Redis的每个bucket只能存1个键值对，而Go的bucket可能存8个键值对，所以Go可以容忍更高的负载因子。

# 渐进式扩容

扩容的前提条件:

负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。

overflow数量 > 2^15时，也即overflow数量超过32768时。

# 1. 增量扩容

当有两个或以上数量的键被哈希到了同一个bucket时，我们称这些键发生了冲突。Go使用链地址法来解决键冲突。
由于每个bucket可以存放8个键值对，所以同一个bucket存放超过8个键值对时就会再创建一个键值对，用类似链表的方式将bucket连接起来。
一个bucket满载的map(为了描述方便，图中bucket省略了value区域):
当前map存储了7个键值对，只有1个bucket。此地负载因子为7。再次插入数据时将会触发扩容操作，扩容之后再将新插入键写入新的bucket。
hmap数据结构中oldbuckets成员指身原bucket，而buckets指向了新申请的bucket。新的键值对被插入新的bucket中。后续对map的访问操作会触发迁移，将oldbuckets中的键值对逐步的搬迁过来。当oldbuckets中的键值对全部搬迁完毕后，删除oldbuckets。

# 2. 等量扩容

所谓等量扩容，实际上并不是扩大容量，buckets数量不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使bucket的使用率更高，进而保证更快的存取。
在极端场景下，比如不断地增删，而键值对正好集中在一小部分的bucket，这样会造成overflow的bucket数量增多，但负载因子又不高，从而无法执行增量搬迁的情况
overflow的bucket中大部分是空的，访问效率会很差。此时进行一次等量扩容，即buckets数量不变，经过重新组织后overflow的bucket数量会减少，即节省了空间又会提高访问效率。

# map 查找过程

根据key值算出哈希值
取哈希值低位与hmap.B取模确定bucket位置
取哈希值高位在tophash数组中查询
如果tophash[i]中存储值也哈希值相等，则去找到该bucket中的key值进行比较
当前bucket没有找到，则继续从下个overflow的bucket中查找。
如果当前处于搬迁过程，则优先从oldbuckets查找
如果查找不到，也不会返回空值，而是返回相应类型的0值。

# map 插入过程

根据key值算出哈希值
取哈希值低位与hmap.B取模确定bucket位置
查找该key是否已经存在，如果存在则直接更新值
如果没找到将key，将key插入

# map 删除

在 Golang 中的 map 结构，在删除键值对的时候，并不会真正的删除，而是标记。那么随着键值对越来越多，会不会造成大量内存浪费？首先答案是会的，很有可能导致 OOM，而且针对这个还有一个讨论：github.com/golang/go/issues/20135。大致的意思就是在很大的 map 中，delete 操作没有真正释放内存而可能导致内存 OOM。
解决办法: 重建map,将map置为nil
原因: 和mysql 的标记删除类似，防止后续会有相同的 key 插入，省去了扩缩容的操作。但是这个对有些场景是不妥的，如果开发者在未来时间内都不会再插入相同的 key ，很可能会导致 OOM。

# map并发安全

map是并发不安全的.
map 在扩缩容时，需要进行数据迁移，迁移的过程并没有采用锁机制防止并发操作，而是会对某个标识位标记为 1，表示此时正在迁移数据。如果有其他 goroutine 对 map 也进行写操作，当它检测到标识位为 1 时，将会直接 panic。

# map 的 key 必须可比较

map的key必须可比较
map 的 key、value 是存在 buckets 数组里的，每个 bucket 又可以容纳 8 个 key 和 8 个 value。当要插入一个新的 key - value 时，会对 key 进行 hash 运算得到一个 hash 值，然后根据 hash 值的低几位(取几位取决于桶的数量，比如一开始桶的数量是 5，则取低 5 位)来决定命中哪个 bucket。
在命中某个 bucket 后，又会根据 hash 值的高 8 位来决定是 8 个 key 里的哪个位置。如果不巧，发生了 hash 冲突，即该位置上已经有其他 key 存在了，则会去其他空位置寻找插入。如果全都满了，则使用 overflow 指针指向一个新的 bucket，重复刚刚的寻找步骤。
从上面的流程可以看出，在判断 hash 冲突，即该位置是否已有其他 key 时，肯定是要进行比较的，所以 key 必须得是可比较类型的。像 slice、map、function 就不能作为 key。

#Go #

上次更新: 2023/04/16, 18:35:33

← slice 实现原理 sync.Map 实现原理→