go map 数据结构

2021-05-17  本文已影响0人  马梦里

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的地址
}
image.png

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

image.png
3. 负载因子

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

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

4. rehash

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

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 存在,则更新值,如果不存在则插入
上一篇 下一篇

猜你喜欢

热点阅读