go map 数据结构

Go map实现原理
深入Go的Map使用和实现原理

go 中的 map 也是 hashmap，由哈和(bucket)数组组成，每个 bucket 可以存放若干元素(默认8个)，当超过 8 个元素后，hmap会使用extra中的overflow指向新的 bucket 来拓展该bucket；

bucket 数组 tophash 数组 data字节数组 overflow 链表

1. hashmap 的数据结构：

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

image.png

2. bucket 的数据结构：

type bmap struct {
    tophash [8]uint8 //存储哈希值的高8位
    data    byte[1]  //key value数据:key/key/key/.../value/value/value...
    overflow *bmap   //溢出bucket的地址
}

• tophash 数组长度为 8，哈希值相同的 key 存入 bucket 时，将哈希值高位存储在该数组中；
  查找时，tophash 用来快速查找key值是否在该bucket中，而不用每次都通过真值全量进行比较；
• data 区存放实际 key/value，存储方式是 k1k2k3k4...v1v2v3v4...，节省字节对齐带来的空间浪费；
  比如：map[int64]int8，key 是 int64（8个字节），value是int8（一个字节），kv的长度不同，如果按照kv格式存放，则考虑内存对齐v也会占用int64，而按照后者存储时，8个v刚好占用一个int64。
• overflow 指向的是下一个 bucket；
  如果 bucket 已经存储了 8 个值，bucket 会使用 overflow 指向新的 bucket 来存储新的碰撞值；

image.png

哈希冲突后的数据结构：
overflow 表示溢出的意思

image.png

3. 负载因子

负载因子用于表示哈希冲突的情况 = 键数量 / bucket 的数量
哈希因子需要控制在合适的大小，超过阙值后需要 rehash
* 哈希因子过小，说明空间利用率低
* 哈希因子过大，说明冲突严重，存取效率低

每个 hash 表的实现对负载因子的容忍程度不同，redis 中负载因子为 1 时就会触发 rehash，因为 redis 的每个 bucket 只能存储一个键值对。而 go 的能存储 8 个，负载因子为 6.5；

4. rehash

4.1 扩容的前提条件
为保证访问效率，当新元素要添加时，都会检查是否需要扩容，扩容实际是空间换时间；

• 触发扩容的条件
  负载因子达到了 6.5
  overflow 数量 > 2^15

4.2 增量扩容
负载因子超过阙值后，新建一个 buckets，长度为原来的2倍，旧 buckets 的数量逐渐搬迁至新的 buckets 中。
如果数据量较大，采取渐进式hash，每次访问 map 都会触发一次搬迁，每次搬迁2个键值对，搬迁完成后将会删除 oldbuckets；

即将搬迁.png 搬迁中.png 搬迁完成.png

4.3 缩容

image.png

通过不断地删除，键值对集中在一小部分地 bucket 中，overflow 中大部分是空的，经过重新组织后 bucket 的数量会减少，提高访问效率；

5 查找过程

1. 根据 key 算出哈希值
2. 取 hash 值的低位和 hmap.B 取模确定 bucket 的位置
3. 取 hash 值高位在 tophash 数组中查询
4. 如果有，则去 bucket 中找该 key
5. 如果当前 bucket 中没有，则从 overflow 指向的 bucket 中找
6. 如果当前处于搬迁过程中，则优先从 oldbucket 中查找

6 更新过程

1. 根据 key 算出 hash 值
2. hash 值对 hmap.B 取模确定 bucket 的位置
3. 如果 key 存在，则更新值，如果不存在则插入