Golang Map

Table of Contents

• 综述
• 数据结构
• 初始化
  • 字面量
  • 运行时
• 扩容
• 访问
  • 使用Key访问
  • 遍历访问
• 写入
• 删除
• 总结

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

综述

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

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

数据结构

与map有关的数据结构主要包括hmap和bmap，他们分别表示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: 下一个可用的溢出桶地址

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

上面的代码是bmap的原始数据结构，但是需要注意的是因为Golang不支持泛形，而bmap需要存储未知长度的键值对，所以需要在编译期间根据类型动态决定bmap的类型，因此完整的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的扩容类型分为双倍扩容和等量扩容。从容量上来说，双倍扩容相比原来的容量翻倍，而等量扩容和原来的空间保持一致。从触发条件来说，双倍扩容是因为当前装载因子高于阈值，我们知道装载因子越大导致哈希表性能越差，也就是说双倍扩容是因为键值对太多导致的，而等量扩容的触发条件是溢出桶太多导致的。

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

扩容过程的函数主要逻辑在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，进一步提升查询效率。

在执行读取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被赋值后被清零（图中没有表示出）。

删除

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

总结

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

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

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