map源码解读

1 前言

map 是在 Go 中经常使用的一个数据结构，它通过键值对的方式在 O(1) 的时间复杂度的情况下通过 key 找到 value 。本篇文章就是深入解读 Go 的 map 的源码，走读的源码版本为 go v1.22.5。

2 基本使用

2.1 概述

map 是一个 key - value 数据结构，也被称为字典，核心特点包含下面三点：

是基于 key -value 关系映射的模式。
基于 key 维度实现存储数据的去重。
读、写、删操作的时间复杂度是 O(1) 。

2.2 初始化

通过 make 关键字进行初始化操作，不声明 map 的容量。

m := make(map[int]int)

通过 make 关键字进行初始化操作，同时指定 map 预分配的容量。

m := make(map[int]int, 2)

在初始化的时候也进行赋值操作。

m := map[int]int{1: 1, 2: 2}

map 中，key 的数据类型必须为可比较类型，像 slice 、map 、func 就不可以作为 map 的 key 的类型。

2.3 读

直接读取，如果 key 存在，则返回对应的 value ；如果 key 不存在，则会返回 value 的零值。

m := make(map[int]int)
v := m[1]

在读取的时候添加一个 bool 类型作为 flag 表示是否读取成功，如果 flag == false ，则说明读取失败、key 不存在、map 未初始化。

此处同一种语法能够实现不同返回值类型的适配，是由于代码在汇编时，会根据返回参数类型的区别，映射到不同的实现方法。

2.4 写

可以通过下面的方法实现 map 的写操作：

m[1] = 1

如果在未初始化的情况下直接对 map 进行写操作，会导致 panic 。

显示运行结果

panic: assignment to entry in nil map

2.5 删除

执行 delete 方法时，如果 key 存在，则会从 map 中将对应的 key-value 对删除；如果 key 不存在或者 map 未初始化，则方法直接返回，不会产生任何输出。

delete(m, 2)

2.6 遍历

遍历 map 中的 key-value 对：

for k, v := range m {
    ...
}

只是遍历 map 中的 key ，不关注 value 的取值。

在执行 map 的遍历操作的时候时，获取的 key-value 并没有固定的顺序，所以前后两次遍历的得到的结果可能会存在差异。

2.7 清空

可以使用 clear 系统调用清空 map 中的所有元素。

clear(m)

2.8 并发冲突

map 不是并发安全的数据结构，如果会发生并发读写的行为，则会抛出 fatal error 。

具体规则是：

并发读没有问题。
并发读写的写包含多种：写入、更新、删除等操作。
读的时候发现其他 goroutine 在并发写，抛出 fatal error 。
写的时候发现其他 goroutine 在并发写，抛出 fatal error。

fatal error: concurrent map read and map write
fatal error: concurrent map writes

此处的并发读写会引发：fatal error ，这是一种比 panic 更严重的错误，无法使用 recover 操作来捕获。

3 核心原理

map 又称为 hash map ，在算法上是基于 hash 实现 key 的映射和寻址；在数据结构上基于桶数组实现 key-value 的存储。

下面以一组 key-value 写入 map 的流程进行简述：

通过哈希方法取得 key 的 hash 值。
hash 值对桶数组长度取模，确定其所属的桶。
在桶中插入 key-value 对。

hash 的性质，保证了相同的 key 必然产生相同的 hash 值，因此可以映射到相同的桶里面，然后通过桶数组内遍历的方式找到对应的 key-value 对。

因此，只需要在宏观流程上控制每个桶中 key-value 对的数量，就能保证 map 的几项操作都限制在常数级别的时间复杂度。

3.1 hash

hash 也称为散列，是通过某种算法将任意长度的输入压缩到某一固定长度的输出摘要的过程，由于这种属于压缩映射，输入空间远大于输出空间，因此不同输入可能回映射成相同的输出结果。此外，hash 在压缩过程中会存在部分信息丢失，因此这种映射关系具有不可逆性。

hash 的可重入性：相同的 key 必然产生相同的 hash 值。
hash 的离散性：只要两个 key 不相同，不论其相似度的高低，产生的 hash 值会在整个输出域内均匀地离散化。

hash 的单向性：可以通过 hash 值映射到一个字符串，但是不可以通过字符串反向映射到原来的 key 。

hash 冲突：由于输入域（key）无限大，输出域（hash 值）有限，因此必然存在不同 key 映射到相同的 hash 的情况，这也称为 hash 冲突。

3.2 桶数组

map 中，会通过长度为 2 的整数次幂的桶数组进行 key-value 对的存储。

每个桶固定可以存放 8 个 key-value 对。
如果超过 8 个 key-value 对打到桶数组的同一个索引中，此时会通过创建桶链表的方式来解决这一问题。

3.3 解决 hash 冲突

由于 hash 冲突的存在，不同 key 可能存在相同的 hash 值。
hash 值会对桶数组长度取模，因此不同 hash 可能被打到同一个桶中。

综上所述：不同的 key-value 可能会被映射到 map 的同一个桶中。

解决办法：拉链法和开放寻址法。

3.3.1 拉链法

将命中一个桶的元素通过链表的形式进行拼接，因此更容易进行扩展。

3.3.2 开放寻址法

开放寻址法中，在插入新条目时，会基于一定的探测持续寻找，知道找到一个可用于存放数据的空位为止。

3.3.3 两种方法比较

方法	优点
拉链法	简单常用，无需预先为元素分配内存。
开放寻址法	无需额外的指针用于链接元素，内存地址完全连续，可以基于局部性原理，充分利用 CPU 高速缓存。

在 map 解决 hash 冲突问题时，实际上结合了拉链法和开放寻址法两种思路，以 map 的插入操作为例，流程如下：

桶数组中的每个桶，都是一个单向桶链表，以桶为节点进行串联。
每个桶固定可以存放 8 个 key-value 对。
当 key 命中一个桶时，首先会根据开放寻址法，在桶的 8 个位置中寻找空位进行插入。
如果桶的 8 个位置都已被占满，则基于桶的溢出桶指针，找到下一个桶，重复第 3 步。
如果遍历到链表尾部，仍未找到空位，则基于拉链法，在桶的尾部添加一个新桶，并插入 key-value 对。

3.4 扩容优化性能

如果 map 的桶数组长度固定不变，那么随着 key-value 对数量的增长，当一个桶下挂载的 key-value 达到一定的量级，此时操作的时间复杂度会趋于线性，无法满足需求。

因此，map 桶数组的长度会随着 key-value 对数量的变化而实时调整，以保证每个桶内的 key-value 对数量始终控制在常量级别，满足各项操作为 O(1) 时间复杂度的要求。

map 扩容机制的核心包括：

扩容分为增量扩容和等量扩容。
当桶内 key-value 总数 / 桶数组长度 > 6.5 时，桶数组长度增长为原值的两倍。
当桶内溢出桶的数量大于等于 2^B 时（B 为桶数组长度的指数，B 最大取 15），发生等量扩容，桶的长度保持为原值。
采用渐进扩容的方式，当桶被实际操作到时，由使用者负责完成数据迁移，避免因为一次性的全量数据迁移引发性能抖动。

4 数据结构

4.1 hmap

type hmap struct {
	count     int 
	flags     uint8
	B         uint8  
	noverflow uint16 
	hash0     uint32 
	buckets    unsafe.Pointer 
	oldbuckets unsafe.Pointer 
	nevacuate  uintptr        
	extra *mapextra 
}

count ：map 中的 key-value 总数。
flags ：map 的状态标识，可以标识出 map 是否被 goroutine 并发读写。
B ：桶数组长度的指数，桶数组长度为 2^B 。
noverflow ：map 中溢出桶的数量。
hash0 ：hash 随机因子，生成 key 的 hash 值时会用到。
buckets ：桶数组。
oldbuckets ：扩容过程中老的桶数组。
nevacuate ：扩容时的进度标识，index 小于 nevacuate 的桶都已经由老桶转移到新桶中。
extra ：预申请的溢出桶。

4.2 mapextra

type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
	nextOverflow *bmap
}

在 map 初始化过程中，如果容量过大，会提前申请好一批溢出桶，以供后续使用，这部分溢出桶存放在 hmap.mapextra 中。

overflow ：供桶数组 buckets 使用的溢出桶。
oldoverflow ：扩容流程中，供老桶数组 oldBuckets 使用的溢出桶。
nextoverflow ：下一个可用的桶。

4.3 bmap

const bucketCnt = 8
type bmap struct {
    tophash [bucketCnt]uint8
}

bmap 就是 map 中的桶，可以存储 8 组 key-value 对的数据，以及下一个指向下一个溢出桶的指针。
每组 key-value 对数据包含 key 高 8 位 hash 值 tophash 、key 、val 三个部分。
在 go 中的源码中只有 tophash 部分，但由于 tophash 、key 、val 的数据长度固定，因此可以通过内存地址偏移的方式寻到后续的 key 数组、val 数组以及溢出指针。

下面的代码时将 bmap 补充完整如下：

type bmap struct {
    tophash [bucketCnt]uint8
    keys [bucketCnt]T
    values [bucketCnt]T
    overflow uint8
}

5 构造方法

5.1 makemap

主干源码浏览：

func makemap(t *maptype, hint int, h *hmap) *hmap {
	mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	if h == nil {
		h = new(hmap)
	}
	h.hash0 = uint32(rand())

	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

hint 为 map 拟分配的容量，在分配前，会提前对拟分配的内存大小进行判断，如果超限，会将 hint 设置为 0。

mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
if overflow || mem > maxAlloc {
    hint = 0
}

通过 new 方法初始化 hmap 。

if h == nil {
    h = new(hmap)
}

通过 rand() 生成一个随机种子，增加 map 的随机性，用于增加哈希函数的随机性，防止哈希碰撞攻击并提升安全性。

h.hash0 = uint32(rand())

根据负载因子来动态调整桶数组的容量 B ，负载因子衡量哈希表中元素的填充程度，帮助决定是否需要扩容以保持高效的查找和插入性能。

B := uint8(0)
for overLoadFactor(hint, B) {
    B++
}
h.B = B

调用 makeBucketArray 方法，初始化桶数组 hmap.buckets 。

var nextOverflow *bmap
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)

如果 map 容量过大，会提前申请一批溢出桶 hmap.extra 。

if nextOverflow != nil {
    h.extra = new(mapextra)
    h.extra.nextOverflow = nextOverflow
}

5.2 overLoadFactor

const (
	loadFactorDen = 2
    bucketCnt = 8
    loadFactorNum = 13
    goarch.PtrSize = 8
)

func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

func bucketShift(b uint8) uintptr {
	return uintptr(1) << (b & (goarch.PtrSize*8 - 1))
}

bucketShift 通过 B 来计算桶数组的长度为 2^B。
如果 map 预分配容量小于等于 8，B 取 0，桶的个数为 1。
保证 map 预分配容量小于等于桶数组长度 * 6.5。

kv 对数量	桶数组长度指数 B	桶数组长度 2^B
0 ~ 8	0	1
9 ~ 13	1	2
14 ~ 26	2	4
27 ~ 52	3	8
2^(B-1) * 6.5+1 ~ 2^B*6.5	B	2^B

5.3 makeBucketArray

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	base := bucketShift(b)
	nbuckets := base

	if b >= 4 {
		nbuckets += bucketShift(b - 4)
		sz := t.Bucket.Size_ * nbuckets
		up := roundupsize(sz, t.Bucket.PtrBytes == 0)
		if up != sz {
			nbuckets = up / t.Bucket.Size_
		}
	}

	if base != nbuckets {
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}

通过 bucketShift(B) 计算出 2^B 的值，即初始化桶数组的数量 base 。nbuckets 是实际分配的桶数组数量，初始化设置为 base 。

base := bucketShift(b)
nbuckets := base

当 b >= 4 时，需要计算可能需要的溢出桶，然后通过 roundupsize 将需要的桶数组大小调整为合适的内存分配单位。

if b >= 4 {
    nbuckets += bucketShift(b - 4)
    sz := t.Bucket.Size_ * nbuckets
    up := roundupsize(sz, t.Bucket.PtrBytes == 0)
    if up != sz {
        nbuckets = up / t.Bucket.Size_
    }
}

当 base 和 nbuckets 不相等时，nextOverflow 指向第一个溢出桶的位置，通过 last.setoverflow 将最后一个溢出桶的溢出指针设为桶数组的起始位置，以便在需要更多溢出桶时能正确定位。

if base != nbuckets {
    nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))
    last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))
    last.setoverflow(t, (*bmap)(buckets))
}

func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
	*(**bmap)(add(unsafe.Pointer(b), uintptr(t.BucketSize)-goarch.PtrSize)) = ovf
}

6 读流程

6.1 核心

map 读流程主要分为下面几步：

根据 key 获取到 hash 值。
根据 hash 值对桶数组取模，确定所在的桶。
沿着桶链表依次遍历各个桶内的 key-value 对。
命中相同的 key ，则返回 value ；如果 key 不存在，则返回零值。

6.2 mapaccess

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	if h == nil || h.count == 0 {
		if err := mapKeyError(t, key); err != nil {
			panic(err)
		}
		return unsafe.Pointer(&zeroVal[0])
	}
	if h.flags&hashWriting != 0 {
		fatal("concurrent map read and map write")
	}
	hash := t.Hasher(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))
	if c := h.oldbuckets; c != nil {
		if !h.sameSizeGrow() {
			m >>= 1
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))
		if !evacuated(oldb) {
			b = oldb
		}
	}
	top := tophash(hash)
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
			if t.IndirectKey() {
				k = *((*unsafe.Pointer)(k))
			}
			if t.Key.Equal(key, k) {
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
				if t.IndirectElem() {
					e = *((*unsafe.Pointer)(e))
				}
				return e
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}

func (h *hmap) sameSizeGrow() bool {
	return h.flags&sameSizeGrow != 0
}

func evacuated(b *bmap) bool {
	h := b.tophash[0]
	return h > emptyOne && h < minTopHash
}

如果此时 map 未初始化，或此时 key-value 对数量为 0，直接返回零值。

if h == nil || h.count == 0 {
    if err := mapKeyError(t, key); err != nil {
        panic(err)
    }
    return unsafe.Pointer(&zeroVal[0])
}

如果发现存在其他 goroutine 在写 map ，直接抛出并发读写的 fatal error 。其中，并发写标记位于 hmap.flags 的第 3 个 bit 位。

const hashWriting  = 4

if h.flags&hashWriting != 0 {
    fatal("concurrent map read and map write")
}

通过 map type.Hasher 计算出 key 的 hash 值，并对桶数组长度取模，取得对应的桶。

hash := t.Hasher(key, uintptr(h.hash0))
m := bucketMask(h.B)
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))

其中，bucketMask 会根据 B 求得桶数组长度 -1 的值，用于后续的 & 运算，实现取模的效果。

func bucketMask(b uint8) uintptr {
	return bucketShift(b) - 1
}

在取桶时，会关注当前 map 是否处于扩容的流程，如果是的话，需要在老的桶数组 oldbuckets 中取桶，通过 evacuated 判断桶数组是已经迁移到了新桶还是存留在老桶，如果存留在老桶，需要取老桶进行遍历。

if c := h.oldbuckets; c != nil {
    if !h.sameSizeGrow() {
        m >>= 1
    }
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))
    if !evacuated(oldb) {
        b = oldb
    }
}

在取桶前，会先判断 map 的扩容流程是否是增量扩容，如果是，说明

const sameSizeGrow = 8

func (h *hmap) sameSizeGrow() bool {
    return h.flags&sameSizeGrow != 0
}

取老桶时，会调用 evacuated 判断数据是否已经迁移到新桶，判断的方法是，取桶中首个 tophash 值，如果该值为 2，3，4 中的一个，都表示数据已经完成迁移。

const (
    emptyOne = 1
    evacuatedX = 2
    evacuatedY = 3
    evacuatedEmpty = 4
    minTopHash = 5
)

func evacuated(b *bmap) bool {
	h := b.tophash[0]
	return h > emptyOne && h < minTopHash
}

取 key hash 值的高 8 位值 top 。如果该值 <5 ，会累加 5，以避开 0 ～ 4 的取值，因为这几个值会用于枚举，具有一些特殊的含义。

const minTopHash = 5

func tophash(hash uintptr) uint8 {
	top := uint8(hash >> (goarch.PtrSize*8 - 8))
	if top < minTopHash {
		top += minTopHash
	}
	return top
}

开启两层 for 循环进行遍历流程，外层基于桶链表，依次遍历首个桶和后续的每个溢出桶，内层依次遍历一个桶内的 key-value 对。

bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
            // ...
		}
	}
	return unsafe.Pointer(&zeroVal[0])

内存遍历时，首先查询高 8 位的 tophash 值，看是否和 key 的 top 值匹配。如果不匹配且当前位置 tophash 值为 0，说明桶的后续位置都未放入过元素，当前 key 在 map 中不存在，可以直接打破循环，返回零值。

const emptyRest = 0

if b.tophash[i] != top {
    if b.tophash[i] == emptyRest {
        break bucketloop
    }
    continue
}

如果找到了相等的 key ，则通过地址偏移的方式取到 value 并返回。其中 dataOffset 为一个桶中 tophash 数组所占用的空间大小。

if t.Key.Equal(key, k) {
    e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
    if t.IndirectElem() {
        e = *((*unsafe.Pointer)(e))
    }
    return e
}

倘若遍历完成，仍未找到匹配的目标，返回零值兜底。

7 写流程

7.1 核心

map 写流程主要分为以下几步：

根据 key 取 hash 值。
根据 hash 值对桶数组取模，确定所在的桶。
如果 map 处于扩容，则迁移命中的桶，帮助推进渐进式扩容。
沿着桶链表依次遍历各个桶内的 key-value 对。
倘若命中相同的 key ，则对 value 中进行更新。
倘若 key 不存在，则插入 key-value 对。
倘若发现 map 达成扩容条件，则会开启扩容模式，并重新返回第 2 步。

7.2 mapassign

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	if h == nil {
		panic(plainError("assignment to entry in nil map"))
	}
	if h.flags&hashWriting != 0 {
		fatal("concurrent map writes")
	}
	hash := t.Hasher(key, uintptr(h.hash0))

	h.flags ^= hashWriting

	if h.buckets == nil {
		h.buckets = newobject(t.Bucket)
	}

again:
	bucket := hash & bucketMask(h.B)
	if h.growing() {
		growWork(t, h, bucket)
	}
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
	top := tophash(hash)

	var inserti *uint8
	var insertk unsafe.Pointer
	var elem unsafe.Pointer
bucketloop:
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if isEmpty(b.tophash[i]) && inserti == nil {
					inserti = &b.tophash[i]
					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
					elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
				}
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
			if t.IndirectKey() {
				k = *((*unsafe.Pointer)(k))
			}
			if !t.Key.Equal(key, k) {
				continue
			}
			if t.NeedKeyUpdate() {
				typedmemmove(t.Key, k, key)
			}
			elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
			goto done
		}
		ovf := b.overflow(t)
		if ovf == nil {
			break
		}
		b = ovf
	}

	if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
		hashGrow(t, h)
		goto again 
	}

	if inserti == nil {
		newb := h.newoverflow(t, b)
		inserti = &newb.tophash[0]
		insertk = add(unsafe.Pointer(newb), dataOffset)
		elem = add(insertk, bucketCnt*uintptr(t.KeySize))
	}

	if t.IndirectKey() {
		kmem := newobject(t.Key)
		*(*unsafe.Pointer)(insertk) = kmem
		insertk = kmem
	}
	if t.IndirectElem() {
		vmem := newobject(t.Elem)
		*(*unsafe.Pointer)(elem) = vmem
	}
	typedmemmove(t.Key, insertk, key)
	*inserti = top
	h.count++

done:
	if h.flags&hashWriting == 0 {
		fatal("concurrent map writes")
	}
	h.flags &^= hashWriting
	if t.IndirectElem() {
		elem = *((*unsafe.Pointer)(elem))
	}
	return elem
}

写操作时，倘若 map 未初始化，直接 panic。

if h == nil {
    panic(plainError("assignment to entry in nil map"))
}

倘若其他 goroutine 在进行写或删操作，抛出并发写 fatal error 。

if h.flags&hashWriting != 0 {
    fatal("concurrent map writes")
}

通过 maptype.Hasher() 方法求得 key 对应的 hash 值。

hash := t.Hasher(key, uintptr(h.hash0))

通过异或位运算，将 map.flags 的第 3 个 bit 位置为 1，添加写标记。

h.flags ^= hashWriting

倘若 map 的桶数组 buckets 为空，则对其进行初始化。

if h.buckets == nil {
    h.buckets = newobject(t.Bucket)
}

找到当前 key 对应的桶索引 bucket 。

bucket := hash & bucketMask(h.B)

倘若发现当前 map 正处于扩容过程，则帮助其渐进扩容。

if h.growing() {
    growWork(t, h, bucket)
}

从 map 的桶数组 buckets 出发，结合桶索引和桶容量大小，进行地址偏移，获得对应桶 b。

b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))

取得 key 的高 8 位 tophash 。

top := tophash(hash)

提前声明好的三个指针，用于指向存放 key-value 的空槽。

inserti ：tophash 拟插入位置。
insertk：key 拟插入位置。
elem：val 拟插入位置。

var inserti *uint8
var insertk unsafe.Pointer
var elem unsafe.Pointer

开启两层 for 循环，外层沿着桶链表依次遍历，内层依次遍历桶内的 key-value 对。

bucketloop:
	for {
		for i := uintptr(0); i < bucketCnt; i++ {
            // ...
        }
		ovf := b.overflow(t)
		if ovf == nil {
			break
		}
		b = ovf
	}

如果 key 的 tophash 和当前位置 tophash 不同，则会尝试将 inserti 、insertk 、elem 调整指向首歌空位，用于后续的插入操作。如果发现当前位置 tophash 标识为 emptyRest(0) ，则说明当前桶链表后续位置都为空，无序继续遍历，直接 break 遍历流程即可。

if b.tophash[i] != top {
    if isEmpty(b.tophash[i]) && inserti == nil {
        inserti = &b.tophash[i]
        insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
        elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
    }
    if b.tophash[i] == emptyRest {
        break bucketloop
    }
    continue
}

如果桶中某个位置的 tophash 标识为 emptyOne(1) ，说明当前未放入元素，如果为 emptyRest(0) ，说明包括当前位置在内，此后的位置都为空。

const emptyRest = 0 
const emptyOne = 1 

func isEmpty(x uint8) bool {
    return x <= emptyOne
}

倘若找到了相等的 key，则执行更新操作，并且直接跳转到方法的 done 标志位处，进行收尾处理。

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
if t.IndirectKey() {
    k = *((*unsafe.Pointer)(k))
}
if !t.Key.Equal(key, k) {
    continue
}
if t.NeedKeyUpdate() {
    typedmemmove(t.Key, k, key)
}
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
goto done

倘若没找到相等的 key，会在执行插入操作前，判断 map 是否需要开启扩容模式。倘若需要扩容，会在开启扩容模式后，跳转回 again 标志位，重新开始桶的定位以及遍历流程。

if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    goto again
}

倘若遍历完桶链表，都没有为当前待插入的 key-value 对找到空位，则会创建一个新的溢出桶，挂载在桶链表的尾部，并将 inserti、insertk、elem 指向溢出桶的首个空位。

if inserti == nil {
    newb := h.newoverflow(t, b)
    inserti = &newb.tophash[0]
    insertk = add(unsafe.Pointer(newb), dataOffset)
    elem = add(insertk, bucketCnt*uintptr(t.KeySize))
}

创建溢出桶时：

如果 hmap.extra 中还有剩余可用的溢出桶，则直接获取 hmap.extra.nextOverflow，并将 nextOverflow 调整指向下一个空闲可用的溢出桶。
如果 hmap 已经没有空闲溢出桶了，则创建一个新的溢出桶。
hmap 的溢出桶数量 hmap.noverflow 累加 1。
将新获得的溢出桶添加到原桶链表的尾部。
返回溢出桶。

func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
	var ovf *bmap
	if h.extra != nil && h.extra.nextOverflow != nil {
		ovf = h.extra.nextOverflow
		if ovf.overflow(t) == nil {
			h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.BucketSize)))
		} else {
			ovf.setoverflow(t, nil)
			h.extra.nextOverflow = nil
		}
	} else {
		ovf = (*bmap)(newobject(t.Bucket))
	}
	h.incrnoverflow()
	if t.Bucket.PtrBytes == 0 {
		h.createOverflow()
		*h.extra.overflow = append(*h.extra.overflow, ovf)
	}
	b.setoverflow(t, ovf)
	return ovf
}

将 tophash、key、value 插入到取得空位中，并且将 map 的 key-value 对计数器 count 值加 1。

if t.IndirectKey() {
    kmem := newobject(t.Key)
    *(*unsafe.Pointer)(insertk) = kmem
    insertk = kmem
}
if t.IndirectElem() {
    vmem := newobject(t.Elem)
    *(*unsafe.Pointer)(elem) = vmem
}
typedmemmove(t.Key, insertk, key)
*inserti = top
h.count++

收尾环节，再次校验是否有其他协程并发写，倘若有，则抛 fatal error 。将 hmap.flags 中的写标记抹去，然后退出方法。

done:
	if h.flags&hashWriting == 0 {
		fatal("concurrent map writes")
	}
	h.flags &^= hashWriting
	if t.IndirectElem() {
		elem = *((*unsafe.Pointer)(elem))
	}
	return elem

8 删流程

8.1 核心

map 删除 kv 主要分为以下几步：

根据 key 取 hash 值。
根据 hash 值对桶数组取模，确定所在的桶。
如果 map 处于扩容，则迁移命中的桶，帮助推进渐进式扩容。
沿着桶链表依次遍历各个桶内的 key-value 对。
如果命中相同的 key，删除对应的 key-value 对；并将当前位置的 tophash 置为 emptyOne，表示为空。
如果当前位置为末位，或者下一个位置的 tophash 为 emptyRest，则沿当前位置向前遍历，将毗邻的 emptyOne 统一更新为 emptyRest。

8.2 mapdelete

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	if h == nil || h.count == 0 {
		if err := mapKeyError(t, key); err != nil {
			panic(err)
		}
		return
	}
	if h.flags&hashWriting != 0 {
		fatal("concurrent map writes")
	}

	hash := t.Hasher(key, uintptr(h.hash0))

	h.flags ^= hashWriting

	bucket := hash & bucketMask(h.B)
	if h.growing() {
		growWork(t, h, bucket)
	}
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
	bOrig := b
	top := tophash(hash)
search:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break search
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
			k2 := k
			if t.IndirectKey() {
				k2 = *((*unsafe.Pointer)(k2))
			}
			if !t.Key.Equal(key, k2) {
				continue
			}
			if t.IndirectKey() {
				*(*unsafe.Pointer)(k) = nil
			} else if t.Key.PtrBytes != 0 {
				memclrHasPointers(k, t.Key.Size_)
			}
			e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
			if t.IndirectElem() {
				*(*unsafe.Pointer)(e) = nil
			} else if t.Elem.PtrBytes != 0 {
				memclrHasPointers(e, t.Elem.Size_)
			} else {
				memclrNoHeapPointers(e, t.Elem.Size_)
			}
			b.tophash[i] = emptyOne
			if i == bucketCnt-1 {
				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
					goto notLast
				}
			} else {
				if b.tophash[i+1] != emptyRest {
					goto notLast
				}
			}
			for {
				b.tophash[i] = emptyRest
				if i == 0 {
					if b == bOrig {
						break
					}
					c := b
					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
					}
					i = bucketCnt - 1
				} else {
					i--
				}
				if b.tophash[i] != emptyOne {
					break
				}
			}
		notLast:
			h.count--
			if h.count == 0 {
				h.hash0 = uint32(rand())
			}
			break search
		}
	}

	if h.flags&hashWriting == 0 {
		fatal("concurrent map writes")
	}
	h.flags &^= hashWriting
}

如果 map 未初始化或者内部 key-value 对数量为 0，删除时不会报错，直接返回。

if h == nil || h.count == 0 {
    if err := mapKeyError(t, key); err != nil {
        panic(err)
    }
    return
}

如果存在其他 goroutine 在进行写或删操作，抛出并发写的 fatal error。

if h.flags&hashWriting != 0 {
    fatal("concurrent map writes")
}

通过 maptype.Hasher() 方法求得 key 对应的 hash 值。

hash := t.Hasher(key, uintptr(h.hash0))

通过异或位运算，将 map.flags 的第 3 个 bit 位置为 1，添加写标记。

h.flags ^= hashWriting

找到当前 key 对应的桶索引 bucket。

bucket := hash & bucketMask(h.B)

如果发现当前 map 正处于扩容过程，则帮助其渐进扩容。

if h.growing() {
    growWork(t, h, bucket)
}

从 map 的桶数组 buckets 出发，结合桶索引和桶容量大小，进行地址偏移，获得对应桶 b，并赋值给 bOrg。

b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
bOrig := b

取得 key 的高 8 位 tophash。

top := tophash(hash)

开启两层 for 循环，外层沿着桶链表依次遍历，内层依次遍历桶内的 key-value 对。

search:
    for ; b != nil; b = b.overflow(t) {
        for i := uintptr(0); i < bucketCnt; i++ {
            // ...
        }
    }

遍历时，如果发现当前位置 tophash 值为 emptyRest，则直接结束遍历流程。

if b.tophash[i] != top {
    if b.tophash[i] == emptyRest {
        break search
    }
    continue
}

如果 key 不相等，则继续遍历。

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
k2 := k
if t.IndirectKey() {
    k2 = *((*unsafe.Pointer)(k2))
}
if !t.Key.Equal(key, k2) {
    continue
}

如果 key 相等，则删除对应的 key-value 对，并且将当前位置的 tophash 置为 emptyOne。

if t.IndirectKey() {
    *(*unsafe.Pointer)(k) = nil
} else if t.Key.PtrBytes != 0 {
    memclrHasPointers(k, t.Key.Size_)
}
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
if t.IndirectElem() {
    *(*unsafe.Pointer)(e) = nil
} else if t.Elem.PtrBytes != 0 {
    memclrHasPointers(e, t.Elem.Size_)
} else {
    memclrNoHeapPointers(e, t.Elem.Size_)
}
b.tophash[i] = emptyOne

如果当前位置不位于最后一个桶的最后一个位置，或者当前位置的后置位 tophash 不为 emptyRest ，则无需向前遍历更新 tophash 标识，直接跳转到 notLast 位置即可。

if i == bucketCnt-1 {
    if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
        goto notLast
    }
} else {
    if b.tophash[i+1] != emptyRest {
        goto notLast
    }
}

向前遍历，将沿途的空位（ tophash 为 emptyOne ）的 tophash 都更新为 emptySet。

for {
    b.tophash[i] = emptyRest
    if i == 0 {
        if b == bOrig {
            break
        }
        c := b
        for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
        }
        i = bucketCnt - 1
    } else {
        i--
    }
    if b.tophash[i] != emptyOne {
        break
    }
}

如果成功从 map 中删除了一组 key-value 对，则将 hmap 的计数器 count 值减 1. 倘若 map 中的元素全都被删除完了，会为 map 更换一个新的随机因子 hash0 。

notLast:
    h.count--
    if h.count == 0 {
        h.hash0 = uint32(rand())
    }
    break search

收尾环节，再次校验是否有其他协程并发写，倘若有，则抛 fatal error 。将 hmap.flags 中的写标记抹去，然后退出方法。

if h.flags&hashWriting == 0 {
    fatal("concurrent map writes")
}
h.flags &^= hashWriting

9 遍历流程

9.1 迭代器数据结构

type hiter struct {
	key         unsafe.Pointer 
	elem        unsafe.Pointer 
	t           *maptype
	h           *hmap
	buckets     unsafe.Pointer 
	bptr        *bmap          
	overflow    *[]*bmap       
	oldoverflow *[]*bmap       
	startBucket uintptr        
	offset      uint8          
	wrapped     bool           
	B           uint8
	i           uint8
	bucket      uintptr
	checkBucket uintptr
}

hiter 是遍历 map 时用于存放临时数据的迭代器：

key ：指向遍历得到 key 的指针。
value ：指向遍历得到 value 的指针。
t ：map 类型，包含了 key、value 类型大小等信息。
h ：map 的指针。
buckets ：map 的桶数组。
bptr ：当前遍历到的桶。
overflow ：新老桶数组对应的溢出桶。
startBucket ：遍历起始位置的桶索引。
offset ：遍历起始位置的 key-value 对索引。
wrapped ：遍历是否穿越桶数组尾端回到头部了。
B ：桶数组的长度指数。
i ：当前遍历到的 key-value 对在桶中的索引。
bucket ：当前遍历到的桶。
checkBucket ：因为扩容流程的存在，需要额外检查的桶。

9.2 mapiterinit

创建 map 迭代器 hiter ，并且通过取随机数的方式，决定遍历的起始桶号，以及起始 key-value 对索引号。

func mapiterinit(t *maptype, h *hmap, it *hiter) {
	it.t = t
	if h == nil || h.count == 0 {
		return
	}

	if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {
		throw("hash_iter size incorrect")
	}
	it.h = h

	it.B = h.B
	it.buckets = h.buckets
	if t.Bucket.PtrBytes == 0 {
		h.createOverflow()
		it.overflow = h.extra.overflow
		it.oldoverflow = h.extra.oldoverflow
	}

	r := uintptr(rand())
	it.startBucket = r & bucketMask(h.B)
	it.offset = uint8(r >> h.B & (bucketCnt - 1))

	it.bucket = it.startBucket

	if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
		atomic.Or8(&h.flags, iterator|oldIterator)
	}

	mapiternext(it)
}

通过取随机数的方式，决定遍历时的起始桶，以及桶中起始 key-value 对的位置。

r := uintptr(rand())
it.startBucket = r & bucketMask(h.B)
it.offset = uint8(r >> h.B & (bucketCnt - 1))

it.bucket = it.startBucket

完成迭代器 hiter 中各项参数的初始化后，启动 mapiternext 方法开启遍历。

9.3 mapiternext

func mapiternext(it *hiter) {
	h := it.h
	if h.flags&hashWriting != 0 {
		fatal("concurrent map iteration and map write")
	}
	t := it.t
	bucket := it.bucket
	b := it.bptr
	i := it.i
	checkBucket := it.checkBucket

next:
	if b == nil {
		if bucket == it.startBucket && it.wrapped {
			it.key = nil
			it.elem = nil
			return
		}
		if h.growing() && it.B == h.B {
			oldbucket := bucket & it.h.oldbucketmask()
			b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
			if !evacuated(b) {
				checkBucket = bucket
			} else {
				b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
				checkBucket = noCheck
			}
		} else {
			b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
			checkBucket = noCheck
		}
		bucket++
		if bucket == bucketShift(it.B) {
			bucket = 0
			it.wrapped = true
		}
		i = 0
	}
	for ; i < bucketCnt; i++ {
		offi := (i + it.offset) & (bucketCnt - 1)
		if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
			continue
		}
		k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.KeySize))
		if t.IndirectKey() {
			k = *((*unsafe.Pointer)(k))
		}
		e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize))
		if checkBucket != noCheck && !h.sameSizeGrow() {
			if t.ReflexiveKey() || t.Key.Equal(k, k) {
				hash := t.Hasher(k, uintptr(h.hash0))
				if hash&bucketMask(it.B) != checkBucket {
					continue
				}
			} else {
				if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
					continue
				}
			}
		}
		if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
			!(t.ReflexiveKey() || t.Key.Equal(k, k)) {
			it.key = k
			if t.IndirectElem() {
				e = *((*unsafe.Pointer)(e))
			}
			it.elem = e
		} else {
			rk, re := mapaccessK(t, h, k)
			if rk == nil {
				continue
			}
			it.key = rk
			it.elem = re
		}
		it.bucket = bucket
		if it.bptr != b {
			it.bptr = b
		}
		it.i = i + 1
		it.checkBucket = checkBucket
		return
	}
	b = b.overflow(t)
	i = 0
	goto next
}

遍历时发现其他 goroutine 在并发写，直接抛出 fatal error。

if h.flags&hashWriting != 0 {
    fatal("concurrent map iteration and map write")
}

开启最外圈的循环，依次遍历桶数组中的每个桶链表，通过 next 和 goto next 关键字实现循环代码块。

next:
    if b == nil {
        // ...
        b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize))) 
        bucket++
        if bucket == bucketShift(it.B) {
            bucket = 0
            it.wrapped = true
        }
        i = 0
    }
    // ...
    b = b.overflow(t)
    // ...
    goto next
}

如果已经遍历完所有的桶，重新回到起始桶为止，则直接结束方法。

if bucket == it.startBucket && it.wrapped {
    it.key = nil
    it.elem = nil
    return
}

如果 map 处于扩容流程，取桶时兼容新老桶数组的逻辑。如果桶处于旧桶数组且未完成迁移，需要将 checkBucket 置为当前的桶号。

if h.growing() && it.B == h.B {
    oldbucket := bucket & it.h.oldbucketmask()
    b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
    if !evacuated(b) {
        checkBucket = bucket
    } else {
        b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
        checkBucket = noCheck
    }
} else {
    b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
    checkBucket = noCheck
}

遍历的桶号加 1，倘若来到桶数组末尾，则将桶号置为 0。将 key-value 对的遍历索引 i 置为 0。

bucket++
if bucket == bucketShift(it.B) {
    bucket = 0
    it.wrapped = true
}
i = 0

依次遍历各个桶中每个 key-value 对。

for ; i < bucketCnt; i++ {
    // ...
    return
}

如果遍历到的桶属于旧桶数组未迁移完成的桶，需要按照其在新桶中的顺序完成遍历。比如，增量扩容流程中，旧桶中的 key-value 对最终应该被分散迁移到新桶数组的 x、y 两个区域，则此时遍历时，哪怕 key-value 对仍存留在旧桶中未完成迁移，遍历时也应该严格按照其在新桶数组中的顺序来执行。

if checkBucket != noCheck && !h.sameSizeGrow() {
        if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
            continue
    }
}

执行 mapaccessK 方法，基于读流程方法获取 key-value 对，通过迭代 hiter 的 key、value 指针进行接收，用于对用户的遍历操作进行响应。

rk, re := mapaccessK(t, h, k)
if rk == nil {
      continue 
}
it.key = rk
it.elem = re

10 扩容流程

10.1 扩容类型

map 的扩容类型分为两类，一类叫做增量扩容，一类叫做等量扩容。

增量扩容

表现：扩容后，桶数组的长度增长为原长度的 2 倍。
目的：降低每个桶中 key-value 对的数量，优化 map 操作的时间复杂度。

等量扩容

表现：扩容后，桶数组的长度和之前保持一致；但是溢出桶的数量会下降。
目的：提高桶主体结构的数据填充率，减少溢出桶数量，避免发生内存泄漏。

10.2 何时扩容

只有 map 的写流程可能开启扩容模式。
写 map 新插入 key-value 对之前，会发起是否需要扩容的逻辑判断。

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // ...
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again
    }
    // ...
}

根据 hmap 的 oldbuckets 是否空，可以判断 map 此前是否已开启扩容模式。

func (h *hmap) growing() bool {
	return h.oldbuckets != nil
}

如果此前未进入扩容模式，且 map 中 key-value 对的数量超过 8 个，且大于桶数组长度的 6.5 倍，则进入增量扩容。

const(
   loadFactorNum = 13
   loadFactorDen = 2
   bucketCnt = 8
)

func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

如果溢出桶的数量大于 2^B 个（即桶数组的长度；B 大于 15 时取15），则进入等量扩容。

func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	if B > 15 {
		B = 15
	}
	return noverflow >= uint16(1)<<(B&15)
}

10.3 如何开启扩容模式

func hashGrow(t *maptype, h *hmap) {
	bigger := uint8(1)
	if !overLoadFactor(h.count+1, h.B) {
		bigger = 0
		h.flags |= sameSizeGrow
	}
	oldbuckets := h.buckets
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	h.nevacuate = 0
	h.noverflow = 0

	if h.extra != nil && h.extra.overflow != nil {
		if h.extra.oldoverflow != nil {
			throw("oldoverflow is not nil")
		}
		h.extra.oldoverflow = h.extra.overflow
		h.extra.overflow = nil
	}
	if nextOverflow != nil {
		if h.extra == nil {
			h.extra = new(mapextra)
		}
		h.extra.nextOverflow = nextOverflow
	}
}

如果是增量扩容，bigger 值取 1。倘若是等量扩容，bigger 值取 0，并将 hmap.flags 的第 4 个 bit 位置为 1，标识当前处于等量扩容流程。

const sameSizeGrow = 8

bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
    bigger = 0
    h.flags |= sameSizeGrow
}

将原桶数组赋值给 oldBuckets，并创建新的桶数组和一批新的溢出桶。此处会通过变量 bigger，实现不同扩容模式下，新桶数组长度的区别处理。

buckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

更新 hmap 的桶数组长度指数 B ，flag 标识，并将新、老桶数组赋值给 hmap.oldBuckets 和 hmap.buckets 。扩容迁移进度 hmap.nevacuate 标记为 0。新桶数组的溢出桶数量 hmap.noverflow 置为 0。

flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
    flags |= oldIterator
}
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
h.nevacuate = 0
h.noverflow = 0

将原本存量可用的溢出桶赋给 hmap.extra.oldoverflow。倘若存在下一个可用的溢出桶，赋给 hmap.extra.nextOverflow。

if h.extra != nil && h.extra.overflow != nil {
    if h.extra.oldoverflow != nil {
        throw("oldoverflow is not nil")
    }
    h.extra.oldoverflow = h.extra.overflow
    h.extra.overflow = nil
}
if nextOverflow != nil {
    if h.extra == nil {
        h.extra = new(mapextra)
    }
    h.extra.nextOverflow = nextOverflow
}

10.4 扩容迁移规则

在等量扩容中，新桶数组长度与原桶数组相同。
key-value 对在新桶数组和老桶数组的中的索引号保持一致。
在增量扩容中，新桶数组长度为原桶数组的两倍。
把新桶数组中桶号对应于老桶数组的区域称为 x 区域，新扩展的区域称为 y 区域。
实际上，一个 key 属于哪个桶，取决于其 hash 值对桶数组长度取模得到的结果，因此依赖于其低位的 hash 值结果。
在增量扩容流程中，新桶数组的长度会扩展一位，假定 key 原本从属的桶号为 i，则在新桶数组中从属的桶号只可能是 i （x 区域）或者 i + 老桶数组长度（y 区域）。
当 key 低位 hash 值向左扩展一位的 bit 位为 0，则应该迁往 x 区域的 i 位置；倘若该 bit 位为 1，应该迁往 y 区域对应的 i + 老桶数组长度的位置。

10.5 渐进式扩容

map 采用的是渐进扩容的方式，避免因为一次性的全量数据迁移引发性能抖动。当每次触发写、删操作时，会为处于扩容流程中的 map 完成两组桶的数据迁移。

一组桶是当前写、删操作所命中的桶。
另一组桶是，当前未迁移的桶中，索引最小的那个桶。

func growWork(t *maptype, h *hmap, bucket uintptr) {
	evacuate(t, h, bucket&h.oldbucketmask())

	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
	newbit := h.noldbuckets()
	if !evacuated(b) {
		var xy [2]evacDst
		x := &xy[0]
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize)))
		x.k = add(unsafe.Pointer(x.b), dataOffset)
		x.e = add(x.k, bucketCnt*uintptr(t.KeySize))

		if !h.sameSizeGrow() {
			y := &xy[1]
			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize)))
			y.k = add(unsafe.Pointer(y.b), dataOffset)
			y.e = add(y.k, bucketCnt*uintptr(t.KeySize))
		}

		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			e := add(k, bucketCnt*uintptr(t.KeySize))
			for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) {
				top := b.tophash[i]
				if isEmpty(top) {
					b.tophash[i] = evacuatedEmpty
					continue
				}
				if top < minTopHash {
					throw("bad map state")
				}
				k2 := k
				if t.IndirectKey() {
					k2 = *((*unsafe.Pointer)(k2))
				}
				var useY uint8
				if !h.sameSizeGrow() {
					hash := t.Hasher(k2, uintptr(h.hash0))
					if h.flags&iterator != 0 && !t.ReflexiveKey() && !t.Key.Equal(k2, k2) {
						useY = top & 1
						top = tophash(hash)
					} else {
						if hash&newbit != 0 {
							useY = 1
						}
					}
				}

				if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
					throw("bad evacuatedN")
				}

				b.tophash[i] = evacuatedX + useY
				dst := &xy[useY]                 

				if dst.i == bucketCnt {
					dst.b = h.newoverflow(t, dst.b)
					dst.i = 0
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
					dst.e = add(dst.k, bucketCnt*uintptr(t.KeySize))
				}
				dst.b.tophash[dst.i&(bucketCnt-1)] = top 
				if t.IndirectKey() {
					*(*unsafe.Pointer)(dst.k) = k2 
				} else {
					typedmemmove(t.Key, dst.k, k) 
				}
				if t.IndirectElem() {
					*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
				} else {
					typedmemmove(t.Elem, dst.e, e)
				}
				dst.i++
				dst.k = add(dst.k, uintptr(t.KeySize))
				dst.e = add(dst.e, uintptr(t.ValueSize))
			}
		}
		if h.flags&oldIterator == 0 && t.Bucket.PtrBytes != 0 {
			b := add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))
			ptr := add(b, dataOffset)
			n := uintptr(t.BucketSize) - dataOffset
			memclrHasPointers(ptr, n)
		}
	}

	if oldbucket == h.nevacuate {
		advanceEvacuationMark(h, t, newbit)
	}
}

从老桶数组中获取到待迁移的桶 b。

b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))

获取到老桶数组的长度 newbit。

newbit := h.noldbuckets()

倘若当前桶已经完成了迁移，则无需处理。
创建一个二元数组 xy，分别承载 x 区域和 y 区域中的新桶位置，用于接受来自老桶数组的迁移数组；只有在增量扩容的流程中，才存在 y 区域，因此才需要对 xy 中的 y 进行定义。

var xy [2]evacDst
x := &xy[0]
x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize)))
x.k = add(unsafe.Pointer(x.b), dataOffset)
x.e = add(x.k, bucketCnt*uintptr(t.KeySize))

if !h.sameSizeGrow() {
    y := &xy[1]
    y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize)))
    y.k = add(unsafe.Pointer(y.b), dataOffset)
    y.e = add(y.k, bucketCnt*uintptr(t.KeySize))
}

开启两层 for 循环，外层遍历桶链表，内层遍历每个桶中的 key-value 对。

for ; b != nil; b = b.overflow(t) {
    k := add(unsafe.Pointer(b), dataOffset)
    e := add(k, bucketCnt*uintptr(t.keysize))
    for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
       // ...
    }
}

取每个位置的 tophash 值进行判断，倘若当前是个空位，则将当前位置 tophash 值置为 evacuatedEmpty，开始遍历下一个位置。

top := b.tophash[i]
if isEmpty(top) {
  b.tophash[i] = evacuatedEmpty
  continue
}

寻找到迁移的目的桶。

const evacuatedX = 2
const evacuatedY = 3  

k2 := k
var useY uint8
if !h.sameSizeGrow() {       
   hash := t.hasher(k2, uintptr(h.hash0))
   if hash&newbit != 0 {
        useY = 1
   }
}
b.tophash[i] = evacuatedX + useY
dst := &xy[useY]

其中目的桶的类型定义如下：

type evacDst struct {
    b *bmap          
    i int           
    k unsafe.Pointer 
    e unsafe.Pointer 
}

evacDst.b ：目的地的所在桶。
evacDst.i ：即将入桶的 key-value 对在桶中的索引。
evacDst.k ：入桶 key 的存储指针。
evacDst.e ：入桶 value 的存储指针。

将 key-value 对迁移到目的桶中，并且更新目的桶结构内几个指针的指向。

if dst.i == bucketCnt {
    dst.b = h.newoverflow(t, dst.b)
    dst.i = 0
    dst.k = add(unsafe.Pointer(dst.b), dataOffset)
    dst.e = add(dst.k, bucketCnt*uintptr(t.KeySize))
}
dst.b.tophash[dst.i&(bucketCnt-1)] = top 
if t.IndirectKey() {
    *(*unsafe.Pointer)(dst.k) = k2 
} else {
    typedmemmove(t.Key, dst.k, k) 
}
if t.IndirectElem() {
    *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
} else {
    typedmemmove(t.Elem, dst.e, e)
}
dst.i++
dst.k = add(dst.k, uintptr(t.KeySize))
dst.e = add(dst.e, uintptr(t.ValueSize))

如果当前迁移的桶是旧桶数组未迁移的桶中索引最小的一个，则 hmap.nevacuate 累加 1。如果已经迁移完所有的旧桶，则会确保 hmap.flags 中，等量扩容的标识位被置为 0。

if oldbucket == h.nevacuate {
    advanceEvacuationMark(h, t, newbit)
}

func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
	h.nevacuate++
	stop := h.nevacuate + 1024
	if stop > newbit {
		stop = newbit
	}
	for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
		h.nevacuate++
	}
	if h.nevacuate == newbit {
		h.oldbuckets = nil
		if h.extra != nil {
			h.extra.oldoverflow = nil
		}
		h.flags &^= sameSizeGrow
	}
}

11 参考

小徐先生的编程世界
Golang 源码 1.22.5

1 前言#

2 基本使用#

2.1 概述#

2.2 初始化#

2.3 读#

2.4 写#

2.5 删除#

2.6 遍历#

2.7 清空#

2.8 并发冲突#

3 核心原理#

3.1 hash#

3.2 桶数组#

3.3 解决 hash 冲突#

3.3.1 拉链法#

3.3.2 开放寻址法#

3.3.3 两种方法比较#

3.4 扩容优化性能#

4 数据结构#

4.1 hmap#

4.2 mapextra#

4.3 bmap#

5 构造方法#

5.1 makemap#

5.2 overLoadFactor#

5.3 makeBucketArray#

6 读流程#

6.1 核心#

6.2 mapaccess#

7 写流程#

7.1 核心#

7.2 mapassign#

8 删流程#

8.1 核心#

8.2 mapdelete#

9 遍历流程#

9.1 迭代器数据结构#

9.2 mapiterinit#

9.3 mapiternext#

10 扩容流程#

10.1 扩容类型#

10.2 何时扩容#

10.3 如何开启扩容模式#

10.4 扩容迁移规则#

10.5 渐进式扩容#

11 参考#