Golang Map

用人话解释Map的工作方式

Golang Map是一个非常复杂的概念,在这篇文章中参考了大量的《Go 语言设计与实现》1中的内容,虽然内容很完整,但是该文章展示了大量源码,对于初学者来说还是太过难以理解,而且忽略了很多细节,这些细节对于理解整个运作原理是非常重要的,所以在这篇文章中加以补充。另外,这篇文章是基于Go 1.16

综述

Golang中的map本质上是由多个桶(bucket)组成的,换句话说map本质上是一个桶数组,一个桶最多可以存储8个键值对。一个键(key)通过哈希函数后可以固定的映射到一个桶中,然后在桶内通过遍历桶内8个键的方式来寻找正确的键值对位置。

如果有多个键通过哈希函数后总是被固定的映射到一个桶中,导致一个桶需要存储多于8个元素,那么就需要分配一个溢出桶来帮忙存储,每一个桶都保留一个指针用于指向溢出桶,最后的结果就是一个正常桶通过链表的方法指向下一个溢出桶。

map基础结构-2IdqIi
fig.1 map基础结构

数据结构

与map有关的数据结构主要包括hmapbmap,他们分别表示map的数据结构和桶的数据结构。

上面是hmap的数据结构,各个字段表示的含义是:

  • count: map当前元素的个数
  • flags: map状态标识,其包含的主要状态为(这里面牵扯到很多概念还没有涉及,可以先大致的了解一下各自的含义)
    • iterator(0b0001): 当前map可能正在被遍历
    • oldIterator(0b0010): 当前map的旧桶可能正在被遍历
    • hashWrting(0b0100): 一个goroutine正在向map中写入数据
    • sameSizeGrow(0b1000): 等量扩容标志字段
  • B: 二进制桶序号的长度,比如B=3,那么桶序号可以用3位二进制数表示(最小0b000,最大0b111,共计8个),可以看到这是一个无符号的8bit的整数,所以一个map的最大桶数量为$2^{255}$
  • noverflow: 溢出桶的数量
  • hash0: 哈希因子
  • buckets: 指向正常桶数组的指针
  • oldbuckets: 在map扩容期间指向旧正常桶数组的指针
  • nevacuate: 已迁移的桶序号
  • extra: 记录溢出桶的数据结构

上面是mapextra的数据结构,各个字段表示的含义是:

  • overflow: 溢出桶数组的起始位置
  • oldoverflow: 旧溢出桶数组的起始位置
  • nextOverflow: 下一个可用的溢出桶地址
正常桶和溢出桶-x50l4s
fig.2 正常桶和溢出桶物理存储关系

这个数据结构牵扯到了溢出桶的问题。在map初始化时会根据初始数据量的不同,自动创建不同数量的溢出桶(具体的细节在map初始化中介绍)。在物理结构上初始的正常桶和溢出桶是连续存放的,正常桶和溢出桶之间的关系是靠链表来维护的,如fig.2所示(在上面这张图中我们只需要关注新桶即可)。

上面的代码是bmap的原始数据结构,但是需要注意的是因为Golang不支持泛形,而bmap需要存储未知长度的键值对,所以需要在编译期间根据类型动态决定bmap的类型,因此完整的bmap的数据结构为:

bmap结构-TPrZj4
fig.3 bmap结构

在bmap中有一个tophash数组,长度为8,tophash和key值是一一对应的。在bmap中tophash有两个作用:存储key的哈希高8位和键值对标记。前者是为了加速查找key(将在map读取中详细介绍),这里主要来说一下键值对标记。它主要包含的状态为:

  • emptyRest(0): 当前键值对为空且该序号之后的键值对都为空
  • emptyOne(1): 当前键值对为空
  • evacuateX(2): 已迁移到新桶的前一部分
  • evacuateY(3): 已迁移到新桶的后一部分(仅使用于双倍扩容)
  • evacuateEmpty(4): 当前键值对为空且已经迁移
  • minTopHash(5): tophash数组元素的最低值

由此可以知道key的哈希高8位的值必须要大于5(minTopHash),通过这些状态位可以快速了解对应的键值对的状态,特别是带有evacuate前缀的状态在扩容时起到了非常重要的作用。

初始化

对于Map的初始化主要包含两种方式:字面量和运行时。

由于map需要在编译期间动态获取键值对的尺寸,字面量最终也是通过make函数来进行初始化的。

字面量

字面量的初始化方式都调用了make函数创建一个数组,然后根据字面量提供的数据一个个的赋值,这里以25个元素为界限,分为硬赋值和切片赋值两种情况。

硬赋值

切片赋值

这里的vstatk和vstatv会通过slice字面量初始方法被编译器进一步展开。

运行时

如果键值对的数量小于8,则说明一个桶可以容纳所有的数据,因此在编译阶段会对这种小容量的数据做优化:不调用runtime.makemap而直接创建一个hmap和一个bmap结构。

剩下的情况都会在类型检查期间将make函数转换成runtime.makemap方法。这个方法传入的参数包括:键值对的类型t、键值对的数量hint以及指向hmap的指针h。在这个函数中,首先根据元素类型和键值对的数量确定需要申请的内存空间,然后获取一个随机种子hash0(含义参见hmap的数据结构),然后根据hint的值计算所需要的最少的B值,确定B值就是通过一个循环,如果装载因子不满足条件则B加1,直到满足装载因子的条件,最后调用runtime.makeBucketArray方法来真正的创建桶。

runtime.makeBucketArray方法接受的参数包括:键值对的类型t、二进制桶序号的长度b和dirtyalloc。这个函数会根据b的值创建正常桶和溢出桶,其策略为:

  • 如果$b<4$则仅创建$2^b$个正常桶
  • 如果$b\geq4$则创建$2^b$个正常桶和$2^{b-4}$个溢出桶

在runtime.makeBucketArray方法的最后,将溢出桶的第一个元素指向overflow和nextoverflow。需要注意的是runtime.makeBucketArray方法仅仅完成了内存预分配,实际的内存初始化工作是在写操作中完成的。

扩容

扩容要放到访问、写入和删除内容之前来介绍,因为上述操作均和扩容有千丝万缕的联系。正常扩容是申请新空间,然后将旧桶的内容复制到新桶中,最后释放旧桶内存空间,但是这样带来了性能问题,试想一个很大的map进行这样的复制操作会非常的消耗时间,特别是在高并发的场景下。Golang Map的扩容方式是增量扩容,它的主旨是将耗时的复制操作分摊到每一次的map读写操作中,并同时把新桶和旧桶一起保存起来,直到整个迁移全部完成后才释放旧桶。虽然总复制时间不变,但是通过分散策略让map在扩容期间显得不是那么的慢。因此完整的扩容步骤包括“申请新内容空间”和“迁移”两个部分。

Map的扩容类型分为双倍扩容和等量扩容。从容量上来说,双倍扩容相比原来的容量翻倍,而等量扩容和原来的空间保持一致。从触发条件来说,双倍扩容是因为当前装载因子高于阈值,我们知道装载因子越大导致哈希表性能越差,也就是说双倍扩容是因为键值对太多导致的,而等量扩容的触发条件是溢出桶太多导致的。

那等量扩容的意义何在?是为了解决慢性内存泄漏的问题2。按照之前所说,一个正常桶只能存储8个键值对,如果超出了这个限制,那么只能通过拉链法链接一个溢出桶。假设一个非常极限的场景:当前的map被反复新增和删除键,而且这些键恰好又被映射到同一个桶中,导致这个桶链接的溢出桶非常多,频繁的删除导致溢出桶变得稀疏(fig.4),因为内存释放以桶为单位,溢出桶里哪怕有一个元素也必须不能被回收,所以在这种场景下就会导致缓慢的内存溢出问题。Golang map的解决方案就是执行一次等量扩容,重新复制原来桶的所有数据,让溢出桶的数据变得稠密。

内存泄漏图例-CWwV1O
fig.4 内存泄漏图例

扩容过程的函数主要逻辑在runtime.hashGrow中。如果是双倍扩容,那么直接将hmap.B+1即可,如果是等量扩容,则hmap.B不变,hmap.flags的sameSizeGrow标志位置1。然后调用runtime.makeBucketArray在内存中申请内存,然后分别赋值buckets, oldbuckets和nextoverflow,这个与初始化的内存创建方式几乎一致,可以参见初始化>运行时。

迁移过程是整个map扩容的核心。与迁移相关的函数主要包括runtime.growWork和runtime.evacuate。按照之前所说,迁移是附加在读写和删除操作之上的,每一次迁移操作将迁移一个桶以及该桶的全部溢出桶。runtime.growWork方法是调用runtime.evacuate的迁移入口,迁移的核心内容主要位于runtime.evacuate中。

首先让我们聚焦runtime.growWork的函数。它需要的参数有三个:键值对的类型t、hmap指针h和桶序号bucket。桶序号是如何确定的?按照之前所说,桶迁移发生在写入和删除操作的时候,因此bucket是通过写入和删除操作传入的key进行的哈希计算,换句话说bucket指向的是新桶序号。如果当前是等量扩容,那么旧桶序号等于新桶序号,如果当前是双倍扩容,那么旧桶序号应该去掉新桶序号的最高位,比如bucket=0b10010(序号为18),那么处于双倍扩容时,旧桶序号应该为0b0010(序号为2)。bucket&h.oldbucketmask()这个方法的作用就是根据hmap.flags标志位(sameSizeGrow)识别当前扩容类型,然后返回对应的旧桶序号。runtime.growWork函数还有一步是判断当前是否为双倍扩容,如果是则还需要额外对hmap.nevacuate指向的桶序号进行迁移,这里hmap.nevacuate的序号是旧桶序号,所以无需再进行多余的计算。总结来说,等量扩容只进行当前key对应的旧桶迁移,如果是双倍扩容,则除了对当前key对应的旧桶迁移,还需要对hmap.nevacuate指向的旧桶序号做迁移。

runtime.evacuate是整个map迁移的核心。它接收的参数与runtime.growWork相同:键值对的类型t、hmap指针h和桶序号bucket。在这个函数中首先创建了一个长度为2的evacDst结构的数组。

evacDst的定义如上面的代码所示:

  • b: 指向的是当前桶,如果超过8个键值对则指向的是溢出桶
  • i: 当前桶存放的键值对数量
  • k: 指向下一个空的key数组
  • v: 指向下一个空的value数组

evacDst的作用是暂存当前桶的迁移进度。试想如果没有evacDst则每迁移一个键值对需要重新计算桶指针,遍历正常桶和溢出桶直到找到最后一个空位,这样的效率太低了。这两个evacDst结构体被命名为x和y,回顾tophash的状态编码可以很清楚的看到有一个evacuateX和evacuateY,他们都是一一对应的。如果当前是等量扩容,则只创建x,如果是双倍扩容,则x和y都将被创建。本质上 x.b指向的是新桶序号的前半段(新桶序号的最高位为0),y.b指向的是新桶序号的后半段(新桶序号的最高位为1)。

迁移的核心实际上就是遍历旧桶的正常桶以及链接的全部溢出桶,并对每个桶的键值对进行遍历和迁移。然后根据旧桶的键值对状态和迁移状态将tophash置为相应的状态(evacuateX, evacuateY或evacuateEmpty),这是为了方便读操作了解当前桶的状态,参见后面的读操作。

当一个桶以及它的溢出桶都被迁移完成,则map会释放除正常桶的tophash数组以外全部数据,包括正常桶的键值对数组和全部的溢出桶数据。保留tophash是因为tophash保留了桶的状态。

最后的最后执行runtime.advanceEvacuationMark方法,更新h.nevacuate,如果全部旧桶已经迁移(h.nevacute等于旧桶的数量),则删除oldbuckets和extra.oldoverflow中的全部数据。

访问

一般读操作可以包括两种方式:用Key访问和遍历访问。

使用Key访问

使用Key访问Map时,会根据赋值语句的不同在中间代码生成阶段生成不同的函数,如果返回值只有一个的情况下(v := hash[k]),会对应v := mapaccess1(maptype, hash, &k),如果有两个返回值(v, ok := hash[k]),则对应v, ok := mapaccess2(maptype, hash, &k)。这两种方法在原理上基本差不多。

那么给定一个key时,golang map是如何确定桶序号以及桶内位置的呢?假设我们现在有一个key值,我们使用哈希函数可以获得一个对应的hash值,比如0b01100100......0100。在这里高8位0b01100100表示的是这个key值,它出现的目的是为了查找加速,因为往往key的值长度要高于8位,在桶中搜索时先比较tophash,如果相等之后再比较key的值,这样在搜索过程中可以起到很好的加速效果。低位就是代表桶的序号,上面的例子中我们使用的是低4位0b0100,所以可以推断出在当前的map中最多可以有16个正常桶,如果map后期根据需要扩容1倍,那么我们将使用低5位作为桶序号,也就是说低位的位数是要根据正常桶的容量来定的。而且使用低位作为桶序号,可以有效防止一个桶内含有大量的相同的tophash,进一步提升查询效率。

扩容时桶选择流程-OdRDP7
fig.5 扩容时桶选择流程

在执行读取map之前,会检查hmap.flags中的hashWriting标志位是否为1,如果是则说明该map正在被写入,那么就会导致程序crash。然后基于上述策略,分别计算key的hash值,然后去高8位作为tophash,取低位作为桶序号。如果当前处于扩容状态,那么检查oldbuckets中的对应桶的状态,如果对应桶已经迁移完成(检查tophash状态),则直接访问新桶的数据,反之访问旧桶数据,选择流程如fig.5所示。在这里扩容中的判断方式是hmap.oldbuckets指向的值不为nil,旧桶已迁移的判断方式是根据topbash的状态标识,参见上文的bmap数据结构。

遍历访问

暂略

写入

在了解了扩容过程之后写入过程就比较简单了,主要的逻辑在runtime.mapassign方法中。与读操作一样,首先检查hmap.flags的hashWriting标志位是否置1,如果是则crash,否则则设置hashWriting标志位。

之前提到过runtime.makeBucketArray只是执行了内存预分配,所以在写入时会检查h.buckets是否已经初始化,如果没有则执行初始化操作,这样才能再做进一步的读写操作。随后会检查当前是否处于扩容状态,如果是则执行当前桶的迁移工作,详细内容参见前面的扩容章节。完成迁移后,可以保证全部的数据已经全部迁移到buckets指向的新桶中。遍历正常桶和全部溢出桶的所有键值对,并记录第一个键值对空缺位置的地址,如果key已存在则直接修改value,如果不存在,则检查记录第一个键值对空缺位置的地址是否为空,如果为空则说明桶已经满了,需要新建一个溢出桶,如果不为空,则将新key保存到第一个键值对空缺位置。整个流程如fig.6所示,在图中b的初始值表示的是指向当前正常桶的指针,inserti表示的是当前桶中第一个键值对空缺位置的指针,i指的是当前桶内遍历键值对序号,在每次b被赋值后被清零(图中没有表示出)。

写操作流程图-BQP1mj
fig.6 写操作流程图

删除

和写入差不多,如果是扩容状态需要先迁移,之后再删除。唯一需要注意的是在删除时需要判断删除的key是否是整个桶(包括溢出桶)的最后一个key,如果是则需要将tophash位置为emptyRest,如果不是则置为emptyOne。

总结

Golang map的工作机制非常复杂,首先由于不支持范型很多工作需要在编译器中完成,其次是为了保证性能采用了增量扩容的模式,将map的迁移工作分摊到每一次的写操作和删除操作中。但是了解这些内容是非常值得的,能帮助你写出更高性能的程序。

  1. https://draveness.me/golang/

  2. https://github.com/golang/go/commit/9980b70cb460f27907a003674ab1b9bea24a847c

All rights reserved
Except where otherwise noted, content on this page is copyrighted.