go底层系列-map底层实现

map

map

  • 使用哈希表作为底层实现
  • 一个哈希表里可以有多个哈希表节点,也即bucket
  • 每个bucket就保存 了map中的一个或一组键值对

go底层系列-map底层实现

示例

下图展示一个拥有4个bucket的map:

go底层系列-map底层实现

  • 本例中, hmap.B=2 , 而hmap.buckets长度是2^B为4.
  • 元素经过哈希运算后会落到某个bucket中进行存储
  • 查找过程类似
  • bucket 很多时候被翻译为桶,所谓的 哈希桶 实际上就是bucket

数据结构

go底层系列-map底层实现

  • 每个bucket可以存储8个键值对

  • tophash是个长度为8的数组,**哈希值相同的键(准确的说是哈希值低位相同的键)**存入当前bucket时会将哈希值的高位存储在该数组中,以方便后续匹配

  • data区存放的是key-value数据,存放顺序是key/key/key/…value/value/value,如此存放是为了节省字节对齐带来的空间浪费

  • overflow 指针指向的是下一个bucket,据此将所有冲突的键连接起来

注意:上述中data和overflow并不是在结构体中显示定义的,而是直接通过指针运算进行访问的

示例

下图展示bucket存放8个key-value对:

go底层系列-map底层实现

哈希冲突

  • 当有两个或以上数量的键被哈希到了同一个bucket时,我们称这些键发生了冲突
  • Go使用链地址法来解决键冲突
  • 由于每个bucket可以存放8个键值对,所以同一个bucket存放超过8个键值对时就会再创建一个键值对,用类似链表的方式将bucket连接起来

示例

下图展示产生冲突后的map:

go底层系列-map底层实现

  • bucket数据结构指示下一个bucket的指针称为overflow bucket,意为当前bucket盛不下而溢出的部分
  • 哈希冲突并不是好事情,它降低了存取效率
  • 好的哈希算法可以保证哈希值的随机性
  • 冲突过多也是要控制

负载因子

用于衡量一个哈希表冲突情况,公式为:

// 负载因子 = 键数量/bucket数量

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

渐进式扩容

扩容的前提条件

  • 当新元素将要添加进map时,都会检查是否需要扩容
  • 扩容实际上是以空间换时间的手段
  • 触发扩容的二条件:
    • 负载因子 > 6.5时,也即平均每个bucket存储的键值对达到6.5个
    • overflow数量 > 2^15时,也即overflow数量超过32768时

增量扩容

​ 新建一个bucket,长度是原来的2倍,然后旧bucket数据搬迁到新的bucket。一次性搬迁将会造成比较大的延时,Go采用逐步搬迁策略:即每次访问map时都会触发一次搬迁,每次搬迁2个键值对

示例

go底层系列-map底层实现

当前map存储了7个键值对,只有1个bucket。此负载因子为7。再次插入数据时将会触发扩容操作,扩容之后再将 新插入键写入新的bucket

当第8个键值对插入时,将会触发扩容,扩容后示意图如下:

go底层系列-map底层实现

  • hmap数据结构中oldbuckets成员指原bucket
  • buckets指向了新申请的bucket
  • 新的键值对被插入新的 bucket中
  • 后续对map的访问操作会触发迁移,将oldbuckets中的键值对逐步的搬迁过来
  • 当oldbuckets中的键 值对全部搬迁完毕后,删除oldbuckets

搬迁完成后的示意图如下:

go底层系列-map底层实现

  • 数据搬迁过程中
    • 原bucket中的键值对将存在于新bucket的前面
    • 新插入的键值对将存在于新bucket的后面

实际搬迁过程中比较复杂

等量扩容

  • 所谓等量扩容,实际上并不是扩大容量
  • buckets数量不变,重新做一遍类似增量扩容的搬迁动作
  • 把松散的键值对重新排列一次,以使bucket的使用率更高,进而保证更快的存取
  • 在极端场景下
    • 比如不断的增删,而键值对正好集中在一小部分的bucket
    • 这样会造成overflow的bucket数量增多,但负载因子又不高
    • 从而无法执行增量搬迁的情况

如下图所示:

go底层系列-map底层实现

上图可见

  • overflow的buckt中大部分是空的,访问效率会很差。
  • 此时进行一次等量扩容,即buckets数量不变
  • 经过重新组织后
  • overflow的bucket数量会减少,即节省了空间又会提高访问效率

查找过程

查找过程如下:

  • 跟据key值算出哈希值
  • 取哈希值低位与hmpa.B取模确定bucket位置
  • 取哈希值高位,在tophash数组中查询
  • 如果tophash[i]中存储值也哈希值相等,则去找到该bucket中的key值进行比较
  • 当前bucket没有找到,则继续从下个overflow的bucket中查找
  • 如果当前处于搬迁过程,则优先从oldbuckets查找

注:如果查找不到,也不会返回空值,而是返回相应类型的0值

插入过程

新员素插入过程如下:

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

参考

map的整体结构图

  • Golang中map的底层实现是一个散列表
    • 因此实现map的过程实际上就是实现散表的过程
  • 在这个散列表中
    • 主要出现的结构体有两个
      • 一个叫hmap(a header for a go map)
      • 一个叫bucket
  • 这两种结构的样子分别如下所示:

hmap

go底层系列-map底层实现

  • 图中有很多字段
  • 但是便于理解map的架构
    • 你只需要关心的只有一个
    • 就是标红的字段:buckets数组
  • Golang的map中用于存储的结构是bucket数组
  • 而bucket(即bmap)的结构是怎样的呢?

bucket

go底层系列-map底层实现

  • 相比于hmap
  • bucket的结构显得简单一些
    • 我们使用的map中的key和value就存储在这里(中间)。
    • “高位哈希值”数组记录的是当前bucket中key相关的“索引”
      • 稍后会详细叙述
    • 还有一个字段是一个指向扩容后的bucket的指针
      • 使得bucket会形成一个链表结构
      • 例如下图:

go底层系列-map底层实现

  • 由此看出hmapbucket的关系是这样的:

go底层系列-map底层实现

  • 而bucket又是一个链表
  • 所以
  • 整体的结构应该是这样的:

go底层系列-map底层实现

  • 哈希表的特点是会有一个哈希函数

    • 对你传来的key进行哈希运算
    • 得到唯一的值
      • 一般情况下都是一个数值
  • Golang的map中也有这么一个哈希函数

    • 也会算出唯一的值
    • 对于这个值的使用
    • Golang也是很有意思
  • Golang把求得的值按照用途一分为二:

    • 高位和低位

go底层系列-map底层实现

  • 如图所示
    • 蓝色为高位
    • 红色为低位
  • 然后
    • 低位用于寻找当前key属于hmap中的哪个bucket
    • 而高位用于寻找bucket中的哪个key
  • 上文中提到:
    • bucket中有个属性字段是“高位哈希值”数组
    • 这里存的就是蓝色的高位值
      • 用来声明当前bucket中有哪些“key”
      • 便于搜索查找
  • 需要特别指出的一点是:
    • 我们map中的key/value值都是存到同一个数组中的
    • 并不是key0/value0/key1/value1的形式
    • 这样做的好处是:
      • 在key和value的长度不同的时候
      • 可以消除padding带来的空间浪费。
  • 现在
    • 我们可以得到Go语言map的整个的结构图了:

go底层系列-map底层实现

上一篇:设置禁止网络连接后,jdbc如何连接到数据库


下一篇:极光笔记丨Spark SQL 在极光的建设实践