全文四万多字，包含了对 map 的相关原理还有源码的深度解析，文中的图片大都来自文末的参考文章，如果有哪个地方写的不对，欢迎批评指正！！！
Go 中的 map 使用的是链地址法解决哈希冲突，但是它的实现并不是对冲突的元素采用链表存储，而是采用了数组的形式。
哈希表相关概念哈希表是计算机科学中的最重要数据结构之一，这不仅因为它 O(1) 的读写性能非常优秀，还因为它提供了键值之间的映射。想要实现一个性能优异的哈希表，需要注意两个关键点 —— 哈希函数和冲突解决方法。
哈希函数哈希函数（常被称为散列函数）是可以用于将任意大小的数据映射到固定大小值的函数，常见的包括MD5、SHA系列等。实现哈希表的关键点在于哈希函数的选择，哈希函数的选择在很大程度上能够决定哈希表的读写性能。在理想情况下，哈希函数应该能够将不同键映射到不同的索引上，这要求哈希函数的输出范围大于输入范围，但是由于键的数量会远远大于映射的范围，所以在实际使用时，这个理想的效果是不可能实现的。
一个设计优秀的哈希函数应该包含以下特性：
- 均匀性：一个好的哈希函数应该在其输出范围内尽可能均匀地映射，也就是说，应以大致相同的概率生成输出范围内的每个哈希值。
- 效率高：哈希效率要高，即使很长的输入参数也能快速计算出哈希值。
- 可确定性：哈希过程必须是确定性的，这意味着对于给定的输入值，它必须始终生成相同的哈希值。
- 雪崩效应：微小的输入值变化也会让输出值发生巨大的变化。
- 不可逆：从哈希函数的输出值不可反向推导出原始的数据。
-
哈希桶。哈希桶（也称为槽，类似于抽屉原理中的一个抽屉）可以理解为一个哈希值，所有的哈希值组成哈希空间。
-
装载因子。装载因子是表示哈希表中元素的填满程度。它的计算公式：
装 载 因 子 = 填 入 哈 希 表 中 的 元 素 个 数 / 哈 希 表 的 长 度 。 装载因子=填入哈希表中的元素个数/哈希表的长度。 装载因子=填入哈希表中的元素个数/哈希表的长度。
装载因子越大，填入的元素越多，空间利用率就越高，但发生哈希冲突的几率就变大。反之，装载因子越小，填入的元素越少，冲突发生的几率减小，但空间浪费也会变得更多，而且还会提高扩容操作的次数。装载因子也是决定哈希表是否进行扩容的关键指标，在 java 的 HashMap 的中，其默认装载因子为 0.75；Python的 dict 默认装载因子为2/3。
哈希函数是将任意大小的数据映射到固定大小值的函数。那么，可以预见到，即使哈希函数设计得足够优秀，几乎每个输入值都能映射为不同的哈希值。但是，当输入数据足够大，大到能超过固定大小值的组合能表达的最大数量数，冲突将不可避免！
这里提到的哈希碰撞不是多个键对应的哈希完全相等，可能是多个哈希的部分相等，例如：两个键对应哈希的前四个字节相同。
解决哈希冲突的方法 开放寻址法抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，至少会有一个抽屉里面放不少于两个苹果。抽屉原理有时也被称为鸽巢原理。
开放寻址法是一种在哈希表中解决哈希碰撞的方法，这种方法的核心思想是依次探测和比较数组中的元素以判断目标键值对是否存在于哈希表中
对于开放寻址法而言，所有的元素都是存储在 Hash 表当中的，所以无论任何时候都要保证哈希表的槽位数 m 大于或等于键的数据 n（必要时，需要对哈希表进行动态扩容）。
开放寻址法有多种方式：线性探测法、平方探测法、随机探测法和双重哈希法。举个线性探测法的例子：
设 Hash(key) 表示关键字 key 的哈希值， 表示哈希表的槽位数（哈希表的大小）。
线性探测法则可以表示为：
-
如果 Hash(x) % M 已经有数据，则尝试 (Hash(x) + 1) % M ;
-
如果 (Hash(x) + 1) % M 也有数据了，则尝试 (Hash(x) + 2) % M ;
-
如果 (Hash(x) + 2) % M 也有数据了，则尝试 (Hash(x) + 3) % M ;
……
开放寻址法中对性能影响最大的是装载因子。随着装载因子的增加，线性探测的平均用时就会逐渐增加，这会影响哈希表的读写性能。当装载率超过 70% 之后，哈希表的性能就会急剧下降，而一旦装载率达到 100%，整个哈希表就会完全失效，这时查找和插入任意元素的时间复杂度都是 O(n) 的，这时需要遍历数组中的全部元素，所以在实现哈希表时需要多关注装载因子的变化。
链地址法链地址法的思想是将映射在一个桶里的所有元素用链表串起来。
对于开放寻址法而言，它只有数组一种数据结构就可完成存储，继承了数组的优点，对 CPU 缓存友好，易于序列化操作。但是它对内存的利用率不如链地址法，且发生冲突时代价更高。当数据量明确、装载因子小，适合采用开放寻址法。
链表节点可以在需要时再创建，不必像开放寻址法那样事先申请好足够内存，因此链地址法对于内存的利用率会比开方寻址法高。链地址法对装载因子的容忍度会更高，并且适合存储大对象、大数据量的哈希表。而且相较于开放寻址法，它更加灵活，支持更多的优化策略，比如可采用红黑树代替链表。但是链地址法需要额外的空间来存储指针。
Map 中的数据结构在 Python 中 dict 在发生哈希冲突时采用的开放寻址法，而 java 的 HashMap 采用的是链地址法，而 Go 中使用的也是链地址法，但不完全遵循了链地址法的思想，其主要使用的空间还是数组，其次才用了链表。
Go 中的结构体为 hamp，该结构体的字段如下：
type hmap struct {
// 代表当前哈希表中的元素个数，len(map) 返回的就是该字段值
count int
// 状态标识，比如正在被写、buckets 和 oldbuckets 在被遍历、等量扩容(Map扩容相关字段)
flags uint8
// buckets（桶）的数量的对数，也就是说该哈希表中桶的数量为 2^B 个
B uint8
// 溢出桶的大致数量
noverflow uint16
// 哈希种子，这个值在哈希创建时随机生成，并在计算 key 的哈希的时候会传入哈希函数，以此提高哈希函数的随机性
hash0 uint32 // hash seed
// 指向 buckets 数组的指针，数组大小为 2^B，如果元素个数为 0，它为 nil。
buckets unsafe.Pointer
// 如果发生扩容，oldbuckets 是指向老的 buckets 数组的指针，老的 buckets 数组大小是新的buckets 的 1/2。非扩容状态下，它为 nil。
oldbuckets unsafe.Pointer
// 表示扩容进度，小于此地址的 buckets 代表已搬迁完成。
nevacuate uintptr
// 这个字段是为了优化 GC 扫描而设计的。当 key 和 value 均不包含指针，并且都可以 <=128 字节时使用。extra 是指向 mapextra 类型的指针。
extra *mapextra
}
bmap
buckets 是一个指针，它指向的是一个类型为 bmap 的结构体数组，也就是具体存储 map 键值对的哈希空间。bmap 的结构如下：
type bmap struct {
// tophash 包含此桶中每个键的哈希值最高字节（高8位）信息。
// 如果tophash[0] < minTopHash，tophash[0]则代表桶的搬迁（evacuation）状态。
tophash [bucketCnt]uint8
}
这里的 tophash 指的是哈希值的高八位，在 Go 中，Hash 值的分布如下，高八位即 high-order bits 部分：
在运行期间，bmap 结构体其实不止包含 tophash 字段，因为哈希表中可能存储不同类型的键值对（例如声明了接口类型），而且 Go 语言也不支持泛型，所以键值对占据的内存空间大小只能在编译时进行推导。bmap 中的其他字段在运行时也都是通过计算内存地址的方式访问的，所以它的定义中就不包含这些字段。所以在编译期间通过 cmd/compile/internal/gc.bmap 函数重建了它的结构，动态地创建一个新的结构：
type bmap struct {
//hash值的高八位
topbits [8]uint8
// key 的数组
keys [8]keytype
// value 的数组
values [8]valuetype
// 对齐内存使用的，不是每个 bmap 都有会这个字段，需要满足一定条件
pad uintptr
// 溢出桶，也是指向一个 bmap，上面的字段 topbits、keys、elems 长度为 8，最多存8组键值对，存满了就往指向的这个 bmap 里存
overflow uintptr
}
一个 bmap 的内存模型如下所示：
在上图解示例中，该桶的第 7 位 cell 和第 8 位 cell 还未有对应键值对。需要注意的是，key 和 value 是各自存储起来的，并非想象中的 key/value/key/value… 的形式。这样做虽然会让代码组织稍显复杂，但是它的好处是能让消除填充所需要的字段（padding）。例如 map[int64]int ，如果按照 key/value/key/value/... 这样的模式存储，那在每一个 key/value 对之后都要额外 padding 7 个字节；而将所有的 key，value 分别绑定到一起，这种形式 key/key/.../value/value/...，则只需要在最后添加 padding。
此外，在 8 个键值对数据后面有一个 overflow 指针，因为桶中最多只能装 8 个键值对，如果有多余的键值对落到了当前桶，那么就需要再构建一个桶（称为溢出桶），通过 overflow 指针链接起来。
mapextra当 map 的 key 和 value 都不是指针，并且 size 都小于 128 字节的情况下，会把 bmap 标记为不含指针，这样可以避免 gc 时扫描整个 hmap。但是，bmap 其实有一个 overflow 的字段，是指针类型的，破坏了 bmap 不含指针的设想，这时会把 overflow 移动到 extra 字段来，在这个字段里将指针指向溢出桶。
所以实际上 bmap.overflow 和 hmap.extra.overflow 所指向的地址是一样的，都是溢出桶的内存地址，只是在某些特殊情况下用 hmap.extra.overflow 代替 bmap.overflow ，从而优化了 GC 过程。
type mapextra struct {
// 如果 key 和 value 都不包含指针，并且可以被 inline(<=128 字节)
// 就使用 hmap 的 extr a字段来存储 overflow buckets，这样可以避免 GC 扫描整个 map
// 然而 bmap.overflow 也是个指针。随意其实 bmap.overflow 的指针也是指向了
// hmap.extra.overflow 和 hmap.extra.oldoverflow 中
// overflow 包含的是 hmap.buckets 的 overflow 的 buckets
// oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
overflow *[]*bmap
oldoverflow *[]*bmap
// 指向空闲的 overflow bucket 的指针
nextOverflow *bmap
}
map 中的常量
map 中还定义了一些重要的常量：
注意：键和值超过 128 个字节后，会被转换成指针
const (
// 一个桶中最多容纳的键值对的对数，也就是一个桶最多容纳 2^3=8 个
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits
// 触发扩容的装载因子为 13/2=6.5
loadFactorNum = 13
loadFactorDen = 2
// 键和值超过 128 个字节后，会被转换成指针
maxKeySize = 128
maxElemSize = 128
// 数据偏移量，大小为 bmap 结构体的大小，它需要正确的对齐，
dataOffset = unsafe.Offsetof(struct {
b bmap
v int64
}{}.v)
// 每个桶（如果有溢出，则包含它的 overflow 的链桶）在搬迁完成状态（evacuated* states）下，
// 要么会包含它所有的键值对，要么一个都不包含（但不包括调用 evacuate() 方法阶段，
// 该方法调用只会在对 map 发起 write 时发生，在该阶段其他 goroutine 是无法查看该map的（map 非并发安全））。
// 简单的说，在非写过程的状态中，桶里的数据要么一起搬走，要么一个都还未搬。
// tophash 除了放置正常的高 8 位 hash 值，还会存储一些特殊状态值（标志该 cell 的搬迁状态）。
// 正常的tophash值，最小应该是5，以下列出的就是一些特殊状态值：
// 表示 cell 为空，并且比它高索引位的 cell 或者 overflows 中的 cell 都是空的。（初始化 bucket 时，就是该状态）
emptyRest = 0
// 空的cell，cell已经被搬迁到新的bucket
emptyOne = 1
// 键值对已经搬迁完毕，key 在新 buckets 数组的前半部分
evacuatedX = 2
// 键值对已经搬迁完毕，key 在新 buckets 数组的后半部分
evacuatedY = 3
// cell 为空，整个 bucket 已经搬迁完毕
evacuatedEmpty = 4
// tophash的最小正常值
minTopHash = 5
// flags
// 可能有迭代器在使用 buckets
iterator = 1
// 可能有迭代器在使用 oldbuckets
oldIterator = 2
// 有协程正在向 map 写入 key
hashWriting = 4
// 等量扩容
sameSizeGrow = 8
// 用于迭代器检查的 bucket ID
noCheck = 1<<(8*sys.PtrSize) - 1
)
整体来说，map 的数据结构如下所示：
在上面的数据结构中，实际上 buckets 指向的 []bmap 和 bmap.overflow 指向的 []bmap 的内存在地址空间上是连续的，这个可以在下面 map 初始化的时候看出来。
Map 初始化map 初始化的方式有以下两种：
make(map[k]v) // 指定初始化大小为 hint 的 map make(map[k]v,hint)
对于不指定初始化大小，和初始化值 hint<=8(bucketCnt) 时，go会调用 makemap_small 函数（源码位置 src/runtime/map.go），并直接从堆上进行分配。
func makemap_small() *hmap {
h := new(hmap)
h.hash0 = fastrand()
return h
}
当 hint>8 时，则调用 makemap 函数：
// 如果编译器认为可以在栈上创建 map 和第一个 bucket，那么 h 和 bucket 可能都是非空
// 如果 h != nil，那么 map 可以直接在 h 中创建
// 如果 h.buckets != nil，那么 h 指向的 bucket 可以作为 map 的第一个 bucket 使用
func makemap(t *maptype, hint int, h *hmap) *hmap {
// math.MulUintptr 返回 hint 与 t.bucket.size 的乘积，并判断该乘积是否溢出。
mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
// maxAlloc 的值，根据平台系统的差异而不同，具体计算方式参照 src/runtime/malloc.go
if overflow || mem > maxAlloc {
hint = 0
}
// initialize Hmap
if h == nil {
h = new(hmap)
}
// 通过 fastrand 得到一个随机的哈希种子
h.hash0 = fastrand()
// 根据输入的元素个数 hint，找到能装下这些元素所需要的 B 值
B := uint8(0)
// 2^B < hint/装载因子，找到满足条件的 B
for overLoadFactor(hint, B) {
B++
}
h.B = B
// 分配初始哈希表
// 如果 B 为0，那么 buckets 字段后续会在 mapassign 方法中 lazily 分配
if h.B != 0 {
var nextOverflow *bmap
// makeBucketArray 创建一个 map 的底层保存 buckets 的数组，它最少会分配 h.B^2 的大小。
h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
if nextOverflow != nil {
h.extra = new(mapextra)
h.extra.nextOverflow = nextOverflow
}
}
return h
}
分配 buckets 数组的 makeBucketArray 函数如下：
// makeBucket 为 map 创建用于保存 buckets 的数组。
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
base := bucketShift(b)
nbuckets := base
// 对于小的 b 值（小于4），即桶的数量小于 16 时，使用溢出桶的可能性很小。对于此情况，就避免计算开销。
if b >= 4 {
// 当桶的数量大于等于 16 个时，正常情况下就会额外创建 2^(b-4) 个溢出桶
nbuckets += bucketShift(b - 4)
sz := t.bucket.size * nbuckets
up := roundupsize(sz)
if up != sz {
nbuckets = up / t.bucket.size
}
}
// 这里，dirtyalloc 分两种情况。
// 如果它为 nil，则会分配一个新的底层数组。
// 如果它不为 nil，则它指向的是曾经分配过的底层数组，该底层数组是由之前同样的 t 和 b 参数通过 makeBucketArray 分配的
// 如果数组不为空，需要把该数组之前的数据清空并复用。
if dirtyalloc == nil {
// 由这里可以看出，正常桶和溢出桶在内存中的存储空间是连续的，因为分配的大小是正常桶+溢出桶
buckets = newarray(t.bucket, int(nbuckets))
} else {
buckets = dirtyalloc
size := t.bucket.size * nbuckets
if t.bucket.ptrdata != 0 {
memclrHasPointers(buckets, size)
} else {
memclrNoHeapPointers(buckets, size)
}
}
// 在满足分配溢出桶的条件下，为了把跟踪这些溢出桶的开销降至最低，使用了以下约定：
// 如果预分配的溢出桶的 overflow 指针为 nil，那么可以通过指针碰撞（bumping the pointer）获得更多可用桶。
// 关于指针碰撞：假设内存是绝对规整的，所有用过的内存都放在一边，空闲的内存放在另一边，中间放着一个指针作为分界点的指示器，那所分配内存就仅仅是把指针向空闲空间那边挪动一段与对象大小相等的距离，这种分配方式称为“指针碰撞”）
if base != nbuckets {
// buckets(基地址) + base(2^B)*bucketsize, 即获得第一个 overflow
nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
// 对于最后一个溢出桶，需要一个安全的非 nil 指针指向它，这是为了保证这部分尚未使用的内存 GC 期间安全
// 最后一个 overflow
last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
// 最后一个 overflow 指针指向 buckets(基地址, 也是安全的指针)
last.setoverflow(t, (*bmap)(buckets))
}
return buckets, nextOverflow
}
通过上面的创建过程，初始化出来的 map 大致是如下的结构：
此外，还能看出，正常桶和溢出桶在内存中的存储空间是连续的，只是被 hmap 中的不同字段引用而已
Map 的哈希函数在初始化 go 程序运行环境时（src/runtime/proc.go中的 schedinit），就需要通过 alginit 方法完成对哈希的初始化：
func schedinit() {
lockInit(&sched.lock, lockRankSched)
...
tracebackinit()
moduledataverify()
stackinit()
mallocinit()
fastrandinit() // must run before mcommoninit
mcommoninit(_g_.m, -1)
cpuinit() // must run before alginit
// 这里调用alginit()
alginit() // maps must not be used before this call
modulesinit() // provides activeModules
typelinksinit() // uses maps, activeModules
itabsinit() // uses activeModules
...
goargs()
goenvs()
parsedebugvars()
gcinit()
...
}
对于哈希算法的选择，程序会根据当前架构判断是否支持 AES，如果支持就使用 AES hash，其实现的代码位于 src/runtime/asm_{386,amd64,arm64}.s 中；若不支持，其 hash 算法则根据 xxhash 算法和 cityhash 算启发而来，代码分别对应于 32 位（src/runtime/hash32.go）和 64 位机器（src/runtime/hash32.go）中：
func alginit() {
// Install AES hash algorithms if the instructions needed are present.
if (GOARCH == "386" || GOARCH == "amd64") &&
cpu.X86.HasAES && // AESENC
cpu.X86.HasSSSE3 && // PSHUFB
cpu.X86.HasSSE41 { // PINSR{D,Q}
initAlgAES()
return
}
if GOARCH == "arm64" && cpu.ARM64.HasAES {
initAlgAES()
return
}
getRandomData((*[len(hashkey) * sys.PtrSize]byte)(unsafe.Pointer(&hashkey))[:])
hashkey[0] |= 1 // make sure these numbers are odd
hashkey[1] |= 1
hashkey[2] |= 1
hashkey[3] |= 1
}
上面在创建 map 的时候，map 的哈希种子是通过 h.hash0 = fastrand() 得到的。它是在以下 maptype 中的 hasher 中被使用到，在下文内容中会看到hash值的生成。
type maptype struct {
typ _type
key *_type
elem *_type
bucket *_type // internal type representing a hash bucket
// hasher 的第一个参数就是指向 key 的指针，
// h.hash0 = fastrand() 得到的 hash0，就是 hasher 方法的第二个参数。
// hasher方法返回的就是hash值。
hasher func(unsafe.Pointer, uintptr) uintptr
keysize uint8 // size of key slot
elemsize uint8 // size of elem slot
bucketsize uint16 // size of bucket
flags uint32
}
Map 的基本操作
Key 的定位
假定 key 经过哈希计算后得到 64bit 位的哈希值。如果 B=5，buckets 数组的长度，即桶的数量是 32（2 的 5 次方）。
现要置一 key 于 map 中，该 key 经过哈希后，得到的哈希值如下：
 uint8 {
top := uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {
top += minTopHash
}
return top
}
当两个不同的 key 落在了同一个桶中，这时就发生了哈希冲突。go 的解决方式是链地址法（这里只描述非扩容且该 key 是第一次添加的情况）：在桶中按照顺序寻到第一个空位并记录下来，后续在该桶和它的溢出桶中均未发现存在的该 key，将 key 置于第一个空位；否则，去该桶的溢出桶中寻找空位，如果没有溢出桶，则添加溢出桶，并将其置溢出桶的第一个空位。
例如，下图中的 B 值为 5，所以桶的数量为 32。通过哈希函数计算出待插入 key 的哈希值，低 5 位哈希00110，对应于 6 号桶；高 8 位10010111，十进制为 151，由于桶中前 6 个 cell 已经有正常哈希值填充了(遍历)，所以将 151 对应的高位哈希值放置于第 7 位cell（第8个 cell 为empty Rest，表明它还未使用），对应将 key 和 value 分别置于相应的第七个空位。
如果是查找 key，那么会根据高位哈希值去桶中的每个 cell 中找，若在桶中没找到，并且 overflow 不为nil，那么继续去溢出桶中寻找，直至找到，如果所有的 cell 都找过了，还未找到，则返回 key 类型的默认值（例如 key 是 int 类型，则返回 0）。
查找key通过 key 查找 value 的方式有以下两种：
v := hash[key] // => v := *mapaccess1(maptype, hash, &key) v, ok := hash[key] // => v, ok := mapaccess2(maptype, hash, &key)
赋值语句左侧接受参数的个数会决定使用的运行时方法：
- 当接受一个参数时，会使用 mapaccess1，该函数仅会返回一个指向目标值的指针；
- 当接受两个参数时，会使用 mapaccess2，除了返回目标值之外，它还会返回一个用于表示当前键对应的值是否存在的 bool 值。
mapaccess1 查找 key 的代码实现如下：
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 如果开启了竞态检测 -race
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := funcPC(mapaccess1)
racereadpc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
// 如果开启了 memory sanitizer -msan
if msanenabled && h != nil {
msanread(key, t.key.size)
}
// 如果 map 为空或者元素个数为 0，返回零值
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return unsafe.Pointer(&zeroVal[0])
}
// 注意，这里是按位与操作
// 当 h.flags 对应的值为 hashWriting（代表有其他 goroutine 正在往 map 中写 key）时，
// 那么位计算的结果不为 0，因此抛出以下错误。
// 这也表明，go 的 map 是非并发安全的
if h.flags&hashWriting != 0 {
throw("concurrent map read and map write")
}
// 不同类型的 key，会使用不同的 hash 算法，这里获取 hash 值
hash := t.hasher(key, uintptr(h.hash0))
// 返回 1 << b-1，即 low-order bits，用于下面与操作筛选出对应的 bucket
m := bucketMask(h.B)
// 按位与操作，找到对应的 bucket
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
// 如果 oldbuckets 不为空，那么证明 map 发生了扩容
// 如果有扩容发生，老的 buckets 中的数据可能还未搬迁至新的 buckets 里
// 所以需要先在老的 buckets 中找
if c := h.oldbuckets; c != nil {
if !h.sameSizeGrow() {
// 增量扩容情况下，老 buckets 数组的大小是原来的一半
m >>= 1
}
// 找到 oldbucket 地址
oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
// 如果在 oldbuckets 中 tophash[0] 的值，为 evacuatedX、evacuatedY，evacuatedEmpty 其中之一
// 则 evacuated() 返回为true，说明搬迁完成。
// 因此，只有当搬迁未完成时，才会从此 oldbucket 中遍历
if !evacuated(oldb) {
b = oldb
}
}
// 取出当前 key 值的 tophash 值，即高八位的值
top := tophash(hash)
bucketloop:
// 以下是查找的核心逻辑
// 双重循环遍历：外层循环是从桶到溢出桶遍历；内层是桶中的 cell 遍历
// 跳出循环的条件有三种：
// 1. 第一种是已经找到 key 值；
// 2. 第二种是当前桶再无溢出桶；
// 3. 第三种是当前桶中有 cell 位的 tophash 值是 emptyRest，这个值它代表此时的桶后面的 cell 还未利用，所以无需再继续遍历。
// 初识时 b 为 key 所在的桶，此时是在正常桶中
for ; b != nil; b = b.overflow(t) {
// 该桶存放最多 8 个键值对，依次对比 tophash 值是否相等
for i := uintptr(0); i < bucketCnt; i++ {
if b.tophash[i] != top {
// 不相等且满足第三种条件，跳出循环
if b.tophash[i] == emptyRest {
break bucketloop
}
// 不相等继续遍历
continue
}
// 因为在 bucket 中 key 是用连续的存储空间存储的，因此可以通过 bucket 地址 +
// 数据偏移量（bmap 结构体的大小，也就是 tophash 占用的大小，因为 dataOffset 定义的是声明的 bmap）+
// keysize 的大小，得到 k 的地址
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// 如果 key 是指针（当键超过 maxKeySize（128个字节）时会转换为指针），则需要进行解引用
if t.() {
k = *((*unsafe.Pointer)(k))
}
// 判断 key 是否相等
if t.key.equal(key, k) {
// 同理，value 的地址也是相似的计算方法，只是再要加上8个 keysize 的内存地址
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
// 如果 value 是指针，解引用
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
// 返回找到的值
return e
}
}
}
// 所有的bucket都未找到，则返回零值
return unsafe.Pointer(&zeroVal[0])
}
根据上面的代码，可以看出它的查找流程如下：
- 判断 map 是否为空，为空的话返回零值
- 通过按位与的操作检测 map 是否有其他线程在进行写入，有的话则抛出错误。这也表明 map 不是并发安全的
- 对 key 取 hash 获得哈希值，通过哈希值的低位确定在哪一个 bucket
- 判断是否发生了扩容，如果发生了扩容并且键值搬迁未完成，则需要先到 old bucket 中查找
- 开始内外层循环遍历，依次对比 tophash 是否相等，直到找到对应的 key 或者找不到退出循环，查找过程结束
对于 mapaccess2 函数，它的函数签名如下：
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)
与 mapaccess1 相比，mapaccess2只是多了一个bool类型的返回值，它代表的是是否在 map 中找到了对应的key ，这里贴一下间断的代码：
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
...
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 alg.equal(key, k) {
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
// 多了一个 boolean 返回值
return v, true
}
}
}
// 找不到，返回 false
return unsafe.Pointer(&zeroVal[0]), false
}
同时，源码中还有mapaccessK方法，它的函数签名如下。
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {}
与 mapaccess1 相比，mapaccessK 同时返回了 key和 value，其代码逻辑也一致。
写入 key向 map 中插入或者修改 key，最终调用的是 mapassign 函数。
实际上插入或修改 key 的语法是一样的，只不过前者操作的 key 在 map 中不存在，而后者操作的 key 存在 map 中。
mapassign 函数如下：
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
// 如果 h 是空指针，赋值会引起panic
// 例如以下语句
// var m map[string]int
// m["k"] = 1
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
// 如果开启了竞态检测 -race
if raceenabled {
callerpc := getcallerpc()
pc := funcPC(mapassign)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
// 如果开启了memory sanitizer -msan
if msanenabled {
msanread(key, t.key.size)
}
// 同样检查是否有其他 goroutine 正在对 map 进行 key 写入，有的话抛出错误
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
// 获取哈希值
hash := t.hasher(key, uintptr(h.hash0))
// 将 flags 的值与 hashWriting 做按位"异或"运算并赋值到 flags
// 因为在当前 goroutine 可能还未完成 key 的写入，再次调用 t.hasher 会发生 panic。
h.flags ^= hashWriting
// 这种情况在初始化 map 并且 hint<=8(bucketCnt)时，由于直接在堆上进行分配，所以会出现
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
// bucketMask 返回值是 2 的 B 次方减 1，即 low-order bits
// 因此，通过 hash 值与 bucketMask 返回值做按位与操作获取 low-order bits，
// 返回在 buckets 数组中的第几号桶
bucket := hash & bucketMask(h.B)
// 如果 map 正在搬迁（即h.oldbuckets != nil）中,则先进行搬迁工作。
if h.growing() {
growWork(t, h, bucket)
}
// 计算出上面求出的 bucket 的内存位置
// post = start + bucketNumber * bucketsize
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
// 获取高八位哈希值
top := tophash(hash)
var inserti *uint8
var insertk unsafe.Pointer
var elem unsafe.Pointer
bucketloop:
for {
// 遍历桶中的 8 个 cell
for i := uintptr(0); i < bucketCnt; i++ {
// 这里分两种情况：
// 第一种情况是 cell 位的 tophash 值和当前 tophash 值不相等
// 在 b.tophash[i] != top 的情况下，这个位置有可能会是一个空槽位
// 一般情况下 map 的槽位分布是这样的，e 表示 empty:
// [h0][h1][h2][h3][h4][e][e][e]
// 但在执行过 delete 操作时，可能会变成这样:
// [h0][h1][e][e][h5][e][e][e]
// 所以如果再插入的话，会尽量往前面的位置插
// [h0][h1][e][e][h5][e][e][e]
// ^
// ^
// 这个位置
// 所以在循环的时候还要顺便把前面的空位置先记下来
// 因为有可能在后面会找到相等的 key，也可能找不到相等的 key
if b.tophash[i] != top {
// 当前是一个空槽位并且这是第一个空位
if isEmpty(b.tophash[i]) && inserti == nil {
// 记录这个空闲的位置tophash的地址，用于后面赋值，同时获取将要插入 k，v 位置的地址
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.elemsize))
}
// 查找到末尾了，break 跳出循环
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 第二种情况是 cell 位的 tophash 值和当前的 tophash 值相等
// 查找当前 cell 位的 key 值
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {
k = *((*unsafe.Pointer)(k))
}
// 注意，即使当前 cell 位的 tophash 值相等，不一定它对应的 key 也是相等的
// 所以还要做一个 key 值判断，判断如果 key 值不相等，记录下一轮遍历
if !t.key.equal(key, k) {
continue
}
// 如果已经有该 key 了，就更新它
if t.needkeyupdate() {
typedmemmove(t.key, k, key)
}
// 这里获取到了要插入 key 对应的 value 的内存地址
// pos = start + dataOffset + 8*keysize + i*elemsize
elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
// 如果顺利到这，就直接跳到done的结束逻辑中去
// 这种情况下不会触发下面的情况，直接跳到 done
goto done
}
// 如果桶中的 8 个 cell 遍历完，还未找到对应的空 cell 或覆盖 cell，
// 那么就进入它的溢出桶中去遍历
ovf := b.overflow(t)
// 如果连溢出桶中都没有找到合适的 cell，跳出循环。
if ovf == nil {
break
}
b = ovf
}
// 在已有的桶和溢出桶中都未找到合适的 cell 供 key 写入，那么有可能会触发以下两种情况
// 情况一：
// 判断当前 map 的装载因子是否达到设定的 6.5 阈值，或者当前 map 的溢出桶数量是否过多。如果存在这两种情况之一，则进行扩容操作。
// 注意，这里 hashGrow() 实际并未完成扩容，对哈希表数据的搬迁（复制）操作是通过 growWork() 来完成的。
// 重新跳入 again 逻辑，在进行完 growWork() 操作后，再次遍历新的桶。
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
// 此处涉及的扩容机制后面讲
hashGrow(t, h)
goto again
}
// 情况二：
// 在不满足情况一的条件下，会为当前桶再新建溢出桶，
// 并将 tophash，key 插入到新建溢出桶的对应内存的 0 号位置
if inserti == nil {
// 获取新建溢出桶的位置（后面有分析这个函数的实现）
newb := h.newoverflow(t, b)
// 记录这个空闲的位置tophash的地址，用于后面赋值，同时获取将要插入 k、v 的位置的指针
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}
// 如果 key 是指针（当键超过 maxKeySize（128个字节）时会转换为指针），则需要进行解引用获取值
if t.indirectkey() {
kmem := newobject(t.key)
// 赋值
*(*unsafe.Pointer)(insertk) = kmem
insertk = kmem
}
// value 同理
if t.indirectelem() {
vmem := newobject(t.elem)
// 获取 value 应该插入的地址
*(*unsafe.Pointer)(elem) = vmem
}
// 更新 key 值
typedmemmove(t.key, insertk, key)
// 将 tophash 赋值到bmap tophash数组的[i]位置
*inserti = top
h.count++
done:
// 再判断一次当前 map 是否有其他 goroutine 在写
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
h.flags &^= hashWriting
if t.indirectelem() {
// 获取 value 应该插入的地址
elem = *((*unsafe.Pointer)(elem))
}
// 返回 value 的底层内存位置
return elem
}
在上面的写入流程中，在已有的桶和溢出桶中都未找到合适的 cell 供 key 写入，并且尚不满足扩容阈值的情况下，会通过 newoverflow 获得新的溢出桶。前面 map 初始化的时候提到过，其初始化后的结构是这样子的：
所以 extra.nextOverflow 会指向预分配的溢出桶，另外最后一个溢出桶的 overflow 会指向 buckets[0]，通过这个特性，可以用来判断是否是最后一个溢出桶。
这里再分析一下 newoverflow 的实现：
func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
var ovf *bmap
// 在创建 map 时，实际上会先分配一部分溢出桶用于后续需要
// 这里就会先检查是否有预分配的溢出桶，并且溢出桶还没有用完
if h.extra != nil && h.extra.nextOverflow != nil {
// ovf 指向预分配的溢出桶位置
ovf = h.extra.nextOverflow
// overflow 为 nil ，说明不是最后一个桶
if ovf.overflow(t) == nil {
// 这时候只需要修改 nextOverflow 地址指向下一个溢出桶(因为内存是连续的)，即碰撞指针的思想
h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
} else {
// overflow 不是 nil，说明这是最后的一个桶了，
// 重置此桶上的 overflow 指针为 nil，同时设置 extra.nextOverflow = nil,
// 标记溢出桶已经用完了
ovf.setoverflow(t, nil)
h.extra.nextOverflow = nil
}
} else {
// 没有溢出桶 或者 溢出桶用完了
// 内存空间重新分配一个bmap
ovf = (*bmap)(newobject(t.bucket))
}
// 生成溢出桶 bmap 的计数器计数
h.incrnoverflow()
if t.bucket.ptrdata == 0 {
// 创建 extra 和 overflow
h.createOverflow()
*h.extra.overflow = append(*h.extra.overflow, ovf)
}
// 将这个 bucket 的 overflow 指针指向溢出桶
b.setoverflow(t, ovf)
return ovf
}
通过对 mapassign 的代码分析之后，发现该函数并没有将插入 key 对应的 value 写入对应的内存，而是返回了 value 应该插入的内存地址。也就是说 map 并不会在 mapassign 这个运行时函数中将值拷贝到桶中，该函数只会返回内存地址。
真正的赋值操作是在编译期间插入的，对下面的程序使用 go tool 工具分析：
package main
func main() {
m := make(map[int]int)
for i := 0; i < 100; i++ {
m[i] = 666
}
}
m[i] = 666对应的汇编代码
$ go tool compile -S map.go
...
0x0098 00152 (map.go:6) LEAQ type.map[int]int(SB), CX
0x009f 00159 (map.go:6) MOVQ CX, (SP)
0x00a3 00163 (map.go:6) LEAQ ""..autotmp_2+184(SP), DX
0x00ab 00171 (map.go:6) MOVQ DX, 8(SP)
0x00b0 00176 (map.go:6) MOVQ AX, 16(SP)
0x00b5 00181 (map.go:6) CALL runtime.mapassign_fast64(SB) // 调用函数runtime.mapassign_fast64，该函数实质就是 mapassign（上文示例源代码是该 mapassign 系列的通用逻辑）
0x00ba 00186 (map.go:6) MOVQ 24(SP), AX 24(SP), AX // 返回值，即 value 应该存放的内存地址
0x00bf 00191 (map.go:6) MOVQ $666, (AX) // 把 666 放入该地址中
...
可以看到，赋值的最后一步实际上是编译器额外生成的汇编指令来完成的，可见靠 runtime 有些工作是没有做完的。所以，在 go 中，编译器和 runtime 配合，才能完成一些复杂的工作。
此外，可以看到上面的函数调用是 runtime.mapassign_fast64，这里说明一下：
mapassign 有一系列的函数，根据 key 类型的不同，编译器会将其优化为相应的“快速函数”，但在实现思路上其实都跟 mapassign 一样。类型有以下这些：
key 类型 插入 uint32 mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer uint64 mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer string mapassign_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer
最后，总结一下 map 中 key 的写入流程：
- 检测 map 中 hmap 是否为空指针，是否有其他 groutine 在进行写入，如果有抛出错误；标记 flags 表示当前 groutine 在对 map 进行写操作
- 根据哈希值的低位获得对应的 bucket
- 判断是否正在进行扩容后的搬迁，如果是则先进行搬迁
- 计算高八位的哈希值，首先循环遍历桶中的 8 个 cell，如果 8 个 cell 遍历完还没有，则到溢出桶中进行遍历。这里分两种情况：
- 第一种情况是 cell 位的 tophash 值和当前 tophash 值不相等，因为有可能删除导致中间个别 cell 没有值，但是在后面又还有可能找到相等的 tophash，所以这时会先记录第一个不相等的值（可能当前位为空），然后继续遍历，目的是尽可能往前插入键值
- 第二种情况是 cell 位的 tophash 值和当前的 tophash 值相等，此时会查看当前的 key 值，因为即使当前 cell 位的 tophash 值相等，不一定它对应的 key 也是相等的。不相等则继续遍历，相等则获取当前 value 的地址直接返回(相当于更新 value）。
- 如果遍历所有之后没有找到合适的位置，则需要新建溢出桶来承载键值对。这里也分为两种情况：
-
第一种是需要判断当前 map 的装载因子是否达到 6.5 的阈值或者溢出桶过多，这两种情况都需要对 map 进行扩容处理后再重新遍历
-
第二种情况则是在在不满足情况一的条件下，为当前桶新建溢出桶，并将 tophash，key 插入到新建溢出桶的对应内存的 0 号位置，然后返回 value 的底层内存位置
map 在扩容的时候有两个指标：装载因子和溢出桶的数量。
为了保证访问效率，当 map 将要添加、修改或删除 key 时，都会检查是否需要扩容，扩容实际上是以空间换时间的手段。在上面源码 mapassign 中，其实已经注释 map 扩容条件，主要是两点：
- 判断已经达到装载因子的临界点，即元素个数 > 桶（bucket）总数 * 6.5，这时候说明大部分的桶可能都快满了（即平均每个桶存储的键值对达到 6.5 个），如果插入新元素，有大概率需要挂在溢出桶（overflow bucket）上。
func overLoadFactor(count int, B uint8) bool {
return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
- 判断溢出桶是否太多，当桶总数 < 2 ^ 15 时，如果溢出桶总数 >= 桶总数，则认为溢出桶过多。当桶总数 >= 2 ^ 15 时，直接与 2 ^ 15 比较，当溢出桶总数 >= 2 ^ 15 时，即认为溢出桶太多了。
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
if B > 15 {
B = 15
}
return noverflow >= uint16(1)<<(B&15)
}
对于第2点，其实是对第 1 点的补充。因为在装载因子比较小的情况下，有可能 map 的查找和插入效率也很低，而仅判断第 1 点是避免不了这种情况的。在这种情况下，计算装载因子的分子比较小，即 map 里元素总数少，但是桶数量多（真实分配的桶数量多，包括大量的溢出桶）。
在某些场景下，比如不断的增删，这样会造成 overflow 的 bucket 数量增多，但负载因子又不高，未达不到第 1 点的临界值，就不能触发扩容来缓解这种情况。这样会造成桶的使用率不高，值存储得比较稀疏，查找插入效率会变得非常低，因此有了第 2 点判断指标。这就像是一座空城，房子很多，但是住户很少，都分散了，找起人来很困难。
例如下面，由于 map 的不断删除，0 号 bucket 中的桶链就造成了大量的稀疏桶。
针对这两种情况，官方采用了不同的解决方案
- 针对 1，将 B + 1，新建一个 buckets 数组，也就是说新的 buckets 大小是原来的 2 倍，然后旧 buckets 数据搬迁到新的 buckets。该方法称之为增量扩容。
- 针对 2，并不扩大容量，buckets 数量维持不变，重新做一遍类似增量扩容的搬迁动作，把松散的键值对重新排列一次，以使 bucket 的使用率更高，进而保证更快的存取。该方法称之为等量扩容。
对于 2 的解决方案，其实存在一个极端的情况：如果插入 map 的 key 哈希都一样，那么它们就会落到同一个 bucket 里，超过 8 个就会产生 overflow bucket，结果也会造成 overflow bucket 数过多。移动元素其实解决不了问题，因为这时整个哈希表已经退化成了一个链表，操作效率变成了 O(n)。但 Go 的每一个 map 都会在初始化阶段的 makemap 时定一个随机的哈希种子，所以要构造这种冲突是没那么容易的。
在源码中，和扩容相关的主要是 hashGrow() 函数与 growWork() 函数**。hashGrow() 函数实际上并没有真正地“搬迁”，它只是分配好了新的 buckets，并将老的 buckets 挂到了 oldbuckets 字段上。真正搬迁 buckets 的动作在 growWork() 函数中，而调用 growWork() 函数的动作是在 mapassign() 和 mapdelete() 函数中。**也就是插入（包括修改）、删除 key 的时候，都会尝试进行搬迁 buckets 的工作。它们会先检查 oldbuckets 是否搬迁完毕（检查 oldbuckets 是否为 nil），再决定是否进行搬迁工作。
再重新看一下 mapassign 的相关片段：
again:
...
// 如果 map 正在搬迁（即h.oldbuckets != nil）中,则先进行搬迁工作。
if h.growing() {
// 这里其实只搬迁了当前的 bucket
growWork(t, h, bucket)
}
...
// 重新跳入 again 逻辑，在进行完 growWork() 操作后，再次遍历新的桶。
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
// 分配新的 buckets，并将老的 buckets 挂到 oldbuckets 字段上
hashGrow(t, h)
goto again
}
再分别看看 hashGrow 和 growWork 的实现:
hashGrow 函数：
func hashGrow(t *maptype, h *hmap) {
// 如果达到条件 1，那么将 B 值加 1，相当于是原来的 2 倍
// 否则对应条件 2，进行等量扩容，所以 B 不变
bigger := uint8(1)
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow
}
// 记录老的buckets
oldbuckets := h.buckets
// 申请新的 buckets 空间
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
// 注意 &^ 运算符，这块代码的逻辑是转移标志位
flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
flags |= oldIterator
}
// 提交 grow
h.B += bigger
h.flags = flags
h.oldbuckets = oldbuckets
h.buckets = newbuckets
// 搬迁进度为0
h.nevacuate = 0
// overflow buckets 数为0
h.noverflow = 0
// 如果发现 hmap 是通过 extra 字段来存储 overflow buckets 时
if h.extra != nil && h.extra.overflow != nil {
// Promote current overflow buckets to the old generation.
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
}
}
growWork 函数：
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 为了确认搬迁的 bucket 是我们正在使用的 bucket
// 即如果当前 key 映射到老的 bucket1，那么就搬迁该 bucket1。
evacuate(t, h, bucket&h.oldbucketmask())
// 如果还未完成扩容工作，则再搬迁一个bucket。
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
从 growWork() 函数可以知道，搬迁的核心逻辑是 evacuate() 函数。
从上面可以看出，扩容过程是渐进性的，每次最多搬迁两个桶。
为什么每次至多搬迁 2 个bucket？
这其实是一种性能考量，如果 map 存储了数以亿计的 key-value，一次性搬迁将会造成比较大的延时，因此才采用逐步搬迁策略。
在搬迁函数 evacuate 中，其逻辑主要涉及一个是 bucket 序列号的变化，另外一个就是搬迁区间的确认。
- bucket 序列号的变化
对于 bucket 序列号的变化，增量扩容（条件1）和等量扩容（条件2）都需要进行 bucket 的搬迁工作。对于等量扩容而言，由于 buckets 的数量不变，因此可以按照序号来搬迁。例如老的的 0 号 bucket，仍然搬至新的 0 号 bucket 中。
但是，对于增量扩容而言，就会有所不同。例如原来的 B=5，那么增量扩容时，B 就会变成 6。那么决定 key 值落入哪个 bucket 的低位哈希值就会发生变化（从取 5 位变为取 6 位），取新的低位 hash 值得过程称为 rehash。
因此，在增量扩容中，某个 key 在搬迁前后 bucket 序号可能和原来相等，也可能是相比原来加上 2^B（原来的 B 值），取决于低 hash 值第倒数第 B+1 位是 0 还是 1。
如下图中，当原始的 B = 3 时，旧 buckets 数组长度为 8，在编号为 2 的 bucket 中，其 2 号 cell 和 5 号 cell，它们的低 3 位哈希值相同（不相同的话，也就不会落在同一个桶中了），但是它们的低 4 位分别是 0010、1010。当发生了增量扩容，2 号就会被搬迁到新 buckets 数组的 2 号 bucket 中去，5 号被搬迁到新 buckets 数组的 10 号 bucket 中去，它们的桶号差距是 2 的 3 次方。
- 搬迁区间的确认
在源码中，有 bucket x 和 bucket y 的概念，其实就是增量扩容到原来的 2 倍，桶的数量是原来的 2 倍，前一半桶被称为 bucket x，后一半桶被称为 bucket y。一个 bucket 中的 key 可能会分裂到两个桶中去，分别位于 bucket x 的桶，或 bucket y 中的桶。所以在搬迁一个 cell 之前，需要知道这个 cell 中的 key 是落到哪个区间（而对于同一个桶而言，搬迁到 bucket x 和 bucket y 桶序号的差别是老的 buckets 大小，即 2^old_B）。
确定了要搬迁到的目标 bucket 后，搬迁操作就比较好进行了。将源 key/value 值 copy 到目的地相应的位置。设置 key 在原始 buckets 的 tophash 为 evacuatedX 或是 evacuatedY，表示已经搬迁到了新 map 的bucket x 或是 bucket y，新 map 的 tophash 则正常取 key 哈希值的高 8 位。
为什么确定 key 落在哪个区间很重要？
因为对于增量扩容而言，原本一个 bucket 中的 key 会被分裂到两个 bucket 中去，它们分别处于 bucket x 和 bucket y 中，但是它们之间存在关系 bucket x + 2^B = bucket y （其中，B 是老 bucket 对应的 B 值）。
假设 key 所在的老 bucket 序号为 n，那么如果 key 落在新的 bucket x，则它应该置入 bucket x 起始位置 + n*bucket 的内存中去；如果 key 落在新的 bucket y，则它应该置入 bucket y 起始位置 + n*bucket 的内存中去。因此，确定 key 落在哪个区间，这样就很方便进行内存地址计算，快速找到 key 应该插入的内存地址。
下面看看 evacuate() 函数的具体实现：
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
// 传进来的 oldbucket 实际上是当前定位到的需要搬迁的 bucket
// 这里首先定位原先 bucket 的位置
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
// 获取扩容之前 bucket 的个数
newbit := h.noldbuckets()
// 判断该 bucket 是否已经完成搬迁
if !evacuated(b) {
// 官方TODO，后续也许会实现：如果没有迭代器使用旧的存储桶，则重用溢出存储桶而不是使用新的存储桶。
// xy 包含了高低区间的搬迁目的地内存信息，[bucket, index, key, value]
// x.b 是对应的搬迁目的桶
// x.k 是指向对应目的桶中存储当前 key 的内存地址
// x.e 是指向对应目的桶中存储当前 value 的内存地址
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))
// 只有当增量扩容时才计算 bucket y 的相关信息（和后续计算 useY 相呼应）
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))
}
// evacuate 函数每次只完成一个 bucket 的搬迁工作，因此要遍历完此 bucket 的所有的 cell，将有值的 cell copy 到新的地方。
// bucket 还会链接 overflow bucket，它们同样需要搬迁。
// 因此同样会有 2 层循环，外层遍历 bucket 和 overflow bucket，内层遍历 bucket 的所有 cell。
// 遍历当前桶 bucket 和其之后的溢出桶 overflow bucket
// 注意：初始的 b 是待搬迁的老 bucket
for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
e := add(k, bucketCnt*uintptr(t.keysize))
// 遍历桶中的 cell，这里 i，k，e 分别用于对应 tophash 下标，key 和 value
for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
// 获取tophash
top := b.tophash[i]
// 如果当前 cell 的 tophash 值是 emptyOne 或者 emptyRest，
// 则代表此 cell 没有key。将其标记为evacuatedEmpty，表示它“已经被搬迁”。
if isEmpty(top) {
b.tophash[i] = evacuatedEmpty
continue
}
// 正常不会出现这种情况
// 未被搬迁的 cell 只可能是 emptyOne、emptyRest 或是正常的 top hash（大于等于 minTopHash）
if top < minTopHash {
throw("bad map state")
}
k2 := k
// 如果 key 是指针，则解引用
if t.indirectkey() {
k2 = *((*unsafe.Pointer)(k2))
}
var useY uint8
// 如果是增量扩容
if !h.sameSizeGrow() {
// 计算哈希值，判断当前key和vale是要被搬迁到bucket x还是bucket y
hash := t.hasher(k2, uintptr(h.hash0))
if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
// 有一个特殊情况：有一种 key，每次对它计算 hash，得到的结果都不一样。
// 这个 key 就是 math.NaN() 的结果，它的含义是 not a number，类型是 float64。
// 当它作为 map 的 key时，会遇到一个问题：再次计算它的哈希值和它当初插入 map 时的计算出来的哈希值不一样！
// 这个 key 是永远不会被 Get 操作获取的！当使用 m[math.NaN()] 语句的时候，是查不出来结果的。
// 这个 key 只有在遍历整个 map 的时候，才能被找到。
// 并且，可以向一个 map 插入多个数量的 math.NaN() 作为 key，它们并不会被互相覆盖。
// 当搬迁碰到 math.NaN() 的 key 时，只通过 tophash 的最低位决定分配到 X part 还是 Y part（如果扩容后是原来 buckets 数量的 2 倍）。
// 如果 tophash 的最低位是 0 ，分配到 X part；如果是 1 ，则分配到 Y part。
useY = top & 1
top = tophash(hash)
} else {
// 对于正常的 key，则进入 else 的逻辑
if hash&newbit != 0 {
useY = 1
}
}
}
if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
throw("bad evacuatedN")
}
// 标示这个位置k，v 迁到 x 还是 y，
// 因为 evacuatedX + 1 == evacuatedY，如果 useY 是 0，那就是 x，否则是 y
b.tophash[i] = evacuatedX + useY
// useY 要么为0，要么为 1。
// 这里就是选取在 bucket x 的起始内存位置，或者选择在 bucket y 的起始内存位置
// （只有增量同步才会有这个选择可能）。
dst := &xy[useY]
// 如果目的地的桶已经装满了（8个cell），那么需要新建一个溢出桶，继续搬迁到溢出桶上去。
if dst.i == bucketCnt {
// newoverflow() 前面分析过，它会当将已经事先创建好的 overflow bucket 设置到 bucket 上了
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))
}
// 通过与操作直接避免了边界检查，并设置相应下标位置的值为 tophash（真的妙！！！）
dst.b.tophash[dst.i&(bucketCnt-1)] = top
// 如果待搬迁的key是指针，则复制指针过去
if t.indirectkey() {
*(*unsafe.Pointer)(dst.k) = k2
} else {
// 如果待搬迁的key是值，则复制值过去
typedmemmove(t.key, dst.k, k)
}
// value 和 key 同理
if t.indirectelem() {
*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
} else {
typedmemmove(t.elem, dst.e, e)
}
// 将当前搬迁目的桶的记录 key/value 的索引值（也可以理解为 cell 的索引值）加一
dst.i++
// 计算下一个 dst.k,dst.e 的内存地址
// 由于桶的内存布局中在最后还有 overflow 的指针，所以这里不用担心更新有可能会超出 key 和 value 数组的指针地址。
dst.k = add(dst.k, uintptr(t.keysize))
dst.e = add(dst.e, uintptr(t.elemsize))
}
}
// 如果没有协程在使用老的桶，就对老的桶进行清理，用于帮助 gc
if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
// 只清除 bucket 的 key,value 部分，保留 top hash 部分，指示搬迁状态
ptr := add(b, dataOffset)
n := uintptr(t.bucketsize) - dataOffset
memclrHasPointers(ptr, n)
}
}
// 用于更新搬迁进度
if oldbucket == h.nevacuate {
advanceEvacuationMark(h, t, newbit)
}
}
更新搬迁进度的函数 advanceEvacuationMark 实现如下：
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
// 搬迁桶的进度加一
h.nevacuate++
// 实验表明，1024 至少会比 newbit 高出一个数量级。
// newbit 是传进来的参数，代表扩容之前老的 bucket 个数。
// 所以，用当前进度加 1024 用于确保 O(1) 行为。
stop := h.nevacuate + 1024
if stop > newbit {
stop = newbit
}
// 计算已经搬迁完的桶数
for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
h.nevacuate++
}
// 如果h.nevacuate == newbit，则代表所有的桶都已经搬迁完毕
if h.nevacuate == newbit { // newbit == # of oldbuckets
// 搬迁完毕，所以指向老的 buckets 的指针置为nil
h.oldbuckets = nil
// 前面说过，如果 map 中 key 和 value 均不包含指针，则都可以 inline。
// 那么保存它们的 buckets 数组其实是挂在 hmap.extra 中的。
// 所以，这种情况下，其实我们是搬迁的 extra 的 buckets 数组。
// 因此，在这种情况下，需要在搬迁完毕后，将 hmap.extra.oldoverflow 指针置为nil。
if h.extra != nil {
h.extra.oldoverflow = nil
}
// 最后，清除正在扩容的标志位，扩容完毕。
h.flags &^= sameSizeGrow
}
}
这里在看一下对于判断当前 bucket 是否搬迁完成的函数 evacuated ：
func evacuated(b *bmap) bool {
h := b.tophash[0]
return h > emptyOne && h < minTopHash
}
如果 b.tophash[0] 的值在标志值范围内，即在 (0,4) 区间里，说明已经被搬迁过了。
empty = 0 evacuatedEmpty = 1 evacuatedX = 2 evacuatedY = 3 minTopHash = 4
到这里就完成了 map 的扩容，总结一下整体的流程如下：
- 首先判断是需要等量扩容还是增量扩容，增量扩容的条件是元素个数 > 桶（bucket）总数 * 6.5。而等量扩容的条件是当桶总数 < 2 ^ 15 时，如果溢出桶总数 >= 桶总数，则认为溢出桶过多;当桶总数 >= 2 ^ 15 时，直接与 2 ^ 15 比较，当溢出桶总数 >= 2 ^ 15 时，即认为溢出桶太多了
- 记录当前 buckets 数据，申请新的 buckets 空间
- 将 oldbuckets 指针原有的 buckets，设置 nextOverflow 指针
- 通过 growWork 函数执行旧键值对的搬迁，搬迁采用渐进式的方式，次至多搬迁 2 个bucket。
- 搬迁过程会进行 rehash，对于等量扩容，则只需要将旧的键值对取出来依次放入即可；对于增量扩容，从哈希值的倒数 B 位（原来的 B 值）多取 1 位，变成 B+1位（这里其实是因为扩容后容量为 2 倍，所以在最高位多取一位相当于乘以 2）。然后根据多取出来的一位是 0 还是 1 进行分配，0 则分配到前一般桶 bucket x 加上偏移的位置；1 则分配到后一般桶 backet y 对应加上偏移的位置。
针对下面的 map，其 B 为3，所以原始 buckets 数组为8。当 map 元素数变多，加载因子超过 6.5，所以引起了增量扩容。
以 3 号 bucket 为例，可以看到，由于 B 值加 1，所以在新选取桶时，需要取低 4 位哈希值，这样就会造成 cell 会被搬迁到新 buckets 数组中不同的桶（3 号或 11 号桶）中去。注意，在一个桶中，搬迁 cell 的工作是有序的：它们是依序填进对应新桶的 cell 中去的。
当然，实际情况中 3 号桶很可能还有溢出桶，在这里为了简化绘图，假设 3 号桶没有溢出桶，如果有溢出桶，则相应地添加到新的 3 号桶和 11 号桶中即可，如果对应的 3 号和 11 号桶均装满，则给新的桶添加溢出桶来装载。
对于下图的 map，其 B 也为 3。假设整个 map 中的 overflow 过多，触发了等量扩容。注意，等量扩容时，新的 buckets 数组大小和旧 buckets 数组是一样的。
以 6 号桶为例，它有一个 bucket 和 3 个 overflow buckets，但是实际上桶里的数据非常稀疏，等量扩容的目的就是为了把松散的键值对重新排列一次，以使 bucket 的使用率更高，进而保证更快的存取。搬迁完毕后，新的 6 号桶中只有一个基础 bucket，暂时并不需要溢出桶。这样，和原 6 号桶相比，数据变得紧密，使后续的数据存取变快。
删除 key哈希表的删除逻辑与写入逻辑很相似，只是触发哈希的删除需要使用关键字，如果在删除期间遇到了哈希表的扩容，就会分流桶中的元素，分流结束之后会找到桶中的目标元素完成键值对的删除工作。
删除操作底层的执行函数是 mapdelete，它的流程如下：
-
首先会检查 h.flags 标志，如果发现写标位是 1，直接 panic，因为这表明有其他协程同时在进行写操作。
-
接着计算 key 的哈希，找到落入的 bucket。检查此 map 如果正在扩容的过程中，直接触发一次搬迁操作。
-
删除操作同样是两层循环，核心还是找到 key 的具体位置。寻找过程都是类似的，在 bucket 中挨个 cell 寻找。
-
找到对应位置后，对 key 或者 value 进行“清零”操作。
-
修改 map 中 cell 的状态，如果 bucket 以一堆 emptyOne 状态结束, 还需要将其更改为 emptyRest 状态
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
// 如果开启了竞态检测 -race
if raceenabled && h != nil {
callerpc := getcallerpc()
pc := funcPC(mapdelete)
racewritepc(unsafe.Pointer(h), callerpc, pc)
raceReadObjectPC(t.key, key, callerpc, pc)
}
// 如果开启了memory sanitizer -msan
if msanenabled && h != nil {
msanread(key, t.key.size)
}
// 如果map为空或者元素个数为0, 直接返回
if h == nil || h.count == 0 {
if t.hashMightPanic() {
t.hasher(key, 0) // see issue 23734
}
return
}
// 当 h.flags 对应的值为 hashWriting (代表有其他goroutine正在往map中写key)时,
// 那么位计算的结果不为0, 因此抛出错误
if h.flags&hashWriting != 0 {
throw("concurrent map writes")
}
hash := t.hasher(key, uintptr(h.hash0))
// 将 flags 的值与 hashWriting 做按位 "异或" 运算
// 之所以调用 t.hasher 后设置 hashWriting, 是因为 t.hasher 可能会 panic,
// 在这种情况下, 实际上并没有执行写(删除)操作.
h.flags ^= hashWriting
// 计算出桶的位置
bucket := hash & bucketMask(h.B)
if h.growing() {
// 直接触发一次搬迁操作
growWork(t, h, bucket)
}
// 获取 bucket 的内存地址
b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
bOrig := b
top := tophash(hash)
search:
// 以下是查找的核心逻辑
// 同样双重循环遍历: 外层循环是从桶到溢出桶遍历; 内层是桶中的cell遍历
// 跳出循环的条件有三种:
// 第一种是已经找到 key 值, 并且已经完成清理工作
// 第二种是当前桶再无溢出桶;
// 第三种是当前桶中有 cell 位的 tophash 值是 emptyRest, 它代表此时的桶后面的 cell 还未利用, 所以无需再继续遍历
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
}
// 第一种情况, 说明已经找到了 key 值完全一样
// 对 key 清零
if t.indirectkey() {
*(*unsafe.Pointer)(k) = nil
} else if t.key.ptrdata != 0 {
memclrHasPointers(k, t.key.size)
}
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
// 对 value 清零
if t.indirectelem() {
*(*unsafe.Pointer)(e) = nil
} else if t.elem.ptrdata != 0 {
memclrHasPointers(e, t.elem.size)
} else {
memclrNoHeapPointers(e, t.elem.size)
}
// 对应的 tophash 设置成 emptyOne
b.tophash[i] = emptyOne
// 如果 bucket 现在以一堆 emptyOne 状态结束, 将其更改为 emptyRest 状态.
// 将此功能设为一个单独的函数会很好, 但是 for 循环当前不可内联
// 可以立即结束循环的的两种状况:
// 情况1: 当前 cell 是 bucket 的最后一个 cell, 且后续的 overflow bucket 的 cell tophash 不为 emptyRest
// 情况2: 当前 cell 后续的 cell tophash 不为 emptyRest
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
}
}
// 如果 bucket 现在以一堆 emptyOne 状态结束, 将其更改为 emptyRest 状态
// 在这里存在两种情况:
// 跳出本循环的两种情况:
// 1. 遇到桶内的第一个 bucket。注意: 桶实质上就是一个单向的链表。
// 2. 遇到 cell 的 tophash 非删除状态(emptyOne)
for {
b.tophash[i] = emptyRest
if i == 0 {
// 回到桶开始的位置
if b == bOrig {
break
}
// 获取当前 bucket 的前面的 prev bucket(即 prev bucket 的 overflow 是当前 bucket)
// 每次都是从桶内的首个元素开始，相当于从后往前将 emptyOne 改成 emptyRest
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:
// 对应 count 值减一
h.count--
break search
}
}
if h.flags&hashWriting == 0 {
throw("concurrent map writes")
}
// 清除 hashWriting flag
h.flags &^= hashWriting
}
同样，和写入函数一样，根据 key 类型的不同，删除操作会被优化成更具体的函数：
| key 类型 | 删除 |
|---|---|
| uint32 | mapdelete_fast32(t *maptype, h *hmap, key uint32) |
| uint64 | mapdelete_fast64(t *maptype, h *hmap, key uint64) |
| string | mapdelete_faststr(t *maptype, h *hmap, ky string) |
迭代 map 的结果是无序的，对于下面的例子：
package main
func main() {
m := make(map[int]int)
for i := 0; i < 10; i++ {
m[i] = i
}
for k, v := range m {
fmt.Println(k, v)
}
}
运行以上代码，会发现每次输出顺序都是不同的。
map 遍历的过程，是按序遍历 bucket，同时按需遍历 bucket 中和其 overflow bucket 中的 cell。但是 map 在扩容后，会发生 key 的搬迁，这造成原来落在一个 bucket 中的 key，搬迁后，有可能会落到其他 bucket 中了，从这个角度看，遍历 map 的结果就不可能是按照原来的顺序了。
但其实，go 为了保证遍历 map 的结果是无序的，做了以下事情：map在遍历时，并不是从固定的 0 号 bucket 开始遍历的，每次遍历，都会从一个随机值序号的 bucket，再从其中随机的 cell 开始遍历。然后再按照桶序遍历下去，直到回到起始桶结束。
下面的例子是遍历一个处于未扩容状态的 map。如果 map 正处于扩容状态时，需要先判断当前遍历 bucket 是否已经完成搬迁，如果数据还在老的 bucket，那么就去老 bucket 中拿数据。
当发生了增量扩容时，一个老的 bucket 数据可能会分裂到两个不同的 bucket 中去，那么此时，如果需要从老的 bucket 中遍历数据，例如 1 号，则不能将老 1 号 bucket 中的数据全部取出，仅仅只能取出老 1 号 bucket 中那些在裂变之后，分配到新 1 号 bucket 中的那些 key。
对下面的例子进行编译：
package main
import "fmt"
func main() {
m := make(map[string]int)
m["silverming"] = 18
for k, v := range m {
fmt.Println(k, v)
}
}
执行命令：
go tool compile -S main.go
可以看到如下几行汇编的代码：
//... 0x0104 00260 (main.go:8) CALL runtime.mapiterinit(SB) //... 0x01c8 00456 (main.go:8) CALL runtime.mapiternext(SB) //...
可以看到对于 map 的迭代，底层调用的是 mapiterinit 和 mapiternext 函数。
mapiterinit 就是对 hiter 结构体里的字段进行初始化赋值操作，这个结构用于保证随机性。
hiter 的结构如下：
type hiter struct {
// key 指针
key unsafe.Pointer
// value 指针
elem unsafe.Pointer
// map 类型，包含如 key size 大小等
t *maptype
h *hmap
// 初始化时指向的 buckets
buckets unsafe.Pointer
// 当前遍历到的 bmap
bptr *bmap
overflow *[]*bmap // keeps overflow buckets of hmap.buckets alive
oldoverflow *[]*bmap // keeps overflow buckets of hmap.oldbuckets alive
// 起始遍历的 bucket 编号
startBucket uintptr
// 在迭代过程中开始的桶内偏移，也就是从桶的哪个 cell 开始
offset uint8
// 是否又从头遍历了
wrapped bool
// B 的大小
B uint8
// 当前 cell 序号
i uint8
// 指向当前的 bucket
bucket uintptr
// 因为扩容需要检查的 bucket
checkBucket uintptr
}
mapinterinit 函数的实现如下：
// mapiterinit 初始化用于在 map 上进行遍历的 hiter 结构
// it 指向的 hiter 结构由编译器顺序传递在堆栈上分配, 或者由 reflect_mapiterinit 在堆上分配
// 由于结构包含指针, 因此两者都需要将 hiter 归零
func mapiterinit(t *maptype, h *hmap, it *hiter) {
// 如果开启了竞态检测 -race
if raceenabled && h != nil {
callerpc := getcallerpc()
racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiterinit))
}
// hmap 不存在 或者 hmap 没有存储数据
if h == nil || h.count == 0 {
return
}
// hiter 的大小是 12 个系统指针大小。在 cmd/compile/internal/gc/reflect.go:hiter() 当中有这样的体现
if unsafe.Sizeof(hiter{})/sys.PtrSize != 12 {
throw("hash_iter size incorrect") // see cmd/compile/internal/gc/reflect.go
}
it.t = t
it.h = h
// 抓取桶状态快照
it.B = h.B
it.buckets = h.buckets
if t.bucket.ptrdata == 0 {
// 重新分配 overflow
// 并在 hiter 中存储指向当前 h.extra.overflow 和 h.extra.oldoverflow.
// 这样在迭代的过程中, 不论 table 的增长还是有新的 overflow buckets 被添加到 table 当中
// 都可以让 overflow bucket 处于活动状态
h.createOverflow()
it.overflow = h.extra.overflow
it.oldoverflow = h.extra.oldoverflow
}
// 随机迭代的关键代码
// 生成随机数
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {
// 在 B>28 时, 增加一个偏移量
r += uintptr(fastrand()) << 31
}
// 确定从哪个 bucket 开始遍历
// bucketMask(h.B) 返回 2^B-1，也就是桶的数量-1
it.startBucket = r & bucketMask(h.B)
// 确定从哪个 bucket 的哪个 cell 开始遍历
it.offset = uint8(r >> h.B & (bucketCnt - 1))
// iterator state
it.bucket = it.startBucket
// 标记当前的迭代器
// 多个迭代器可以同事运行
if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
atomic.Or8(&h.flags, iterator|oldIterator)
}
// 开始进行迭代
mapiternext(it)
}
上面的代码实现中，例如，B = 2，那 bucketMask(h.B) 结果就是 3，低 8 位为 00000011，将 r 与之相与，就可以得到一个 0~3 的 bucket 序号；bucketCnt - 1 等于 7，低 8 位为 00000111，将 r 右移 2 位后，与 7 相与，就可以得到一个 0~7 号的 cell。
于是，在 mapiternext 函数中就会从 it.startBucket 的 it.offset 号的 cell 开始遍历，取出其中的 key 和 value，直到又回到起点 bucket，完成遍历过程。
源码部分比较好看懂，尤其是理解了前面注释的几段代码后，再看这部分代码就没什么压力了。所以，接下来，我将通过图形化的方式讲解整个遍历过程，希望能够清晰易懂。
接下来看看遍历的过程，mapiternext 的实现如下：
func mapiternext(it *hiter) {
h := it.h
// 如果开启了竞态检测 -race
if raceenabled {
callerpc := getcallerpc()
racereadpc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
}
// 检测当前是不是有 groutine 在进行写入，有的话直接抛出错误
if h.flags&hashWriting != 0 {
throw("concurrent map iteration and map write")
}
// 获取相应的元素
t := it.t
bucket := it.bucket
b := it.bptr
i := it.i
checkBucket := it.checkBucket
next:
// current bucket 为 nil, 第一次或者最后一次迭代
if b == nil {
// 当前的 bucket 是开始的 bucket 并且已经遍历过了
if bucket == it.startBucket && it.wrapped {
// end of iteration
it.key = nil
it.elem = nil
return
}
// 如果迭代器是在增长过程中启动的，尚未完成增长。
// 并且要查看的存储桶尚未装满（即尚未撤离旧存储桶），
// 则需要遍历旧存储桶，仅返回将要迁移到该存储桶的旧存储桶的值。
// 也就是像上面的例子，仅仅只能取出老 1 号 bucket 中那些在裂变之后，分配到新 1 号 bucket 中的那些 key。
if h.growing() && it.B == h.B {
// 按位与操作，根据 bucket 新增位是 1 还是 0 判断分配到哪里，
// 0 的是需要遍历的（见扩容原理）
oldbucket := bucket & it.h.oldbucketmask()
b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
// 判断当前 bucket 是否已经搬迁了
if !evacuated(b) {
// 如果还没有完成搬迁，则当前 bucket 不需要遍历，后面会跳到 oldbucket 中遍历
checkBucket = bucket
} else {
// 还没后完成搬迁，则当前 bucket 不需要遍历
b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
checkBucket = noCheck
}
} else {
// 正常情况，没有发生扩容时的遍历
b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
checkBucket = noCheck
}
bucket++
// 到了顺序上的最后一个 bucket，置 0 继续遍历
if bucket == bucketShift(it.B) {
bucket = 0
it.wrapped = true
}
i = 0
}
// 遍历当前 bucket 的 cell
for ; i < bucketCnt; i++ {
offi := (i + it.offset) & (bucketCnt - 1)
//
if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
// TODO: emptyRest is hard to use here, as we start iterating
// in the middle of a bucket. It's feasible, just tricky.
// 当前的 cell 状态是 emptyRest, emptyOne(空), evacuatedEmpty(迁移前是emptyRest, emptyOne)
continue
}
// 获取 k,e 分别对应 key 和 value 的内存地址
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.elemsize))
// 去掉需要忽略的特殊情况，也就是增量扩容的情况
if checkBucket != noCheck && !h.sameSizeGrow() {
// 特殊情况：需要遍历 oldbucket 的场景
// 遍历 oldbucket，跳过将要转到另一个新 bucket 的任何键（在增长过程中，每个 oldbucket 会扩展到两个 bucket 中）。
// reflexivekey() // true if k==k for all keys
if t.reflexivekey() || t.key.equal(k, k) {
// 如果 oldbucket 中的 cell 不是搬移到迭代中的当前新存储桶的, 则将其跳过.
hash := t.hasher(k, uintptr(h.hash0))
if hash&bucketMask(it.B) != checkBucket {
continue
}
} else {
// 如果 k！= k(也就是 key 值是 NaNs 的特殊情况), 则 hash 不可重复. 这里需要对迁移期间发送 NaN 的方向进行可重复且随机的选择.
// 这里将使用低位的 tophash 来决定 NaN 的走法.
// 注意: 这种情况就是为什么我们需要两个迁移值, 即 evacuatedX 和 evacuatedY, 它们的低位不同.
if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
continue
}
}
}
// 遍历, 获取对应的 k, v
if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
!(t.reflexivekey() || t.key.equal(k, k)) {
// 特殊情况:
// 在正常状况(没有发生map扩容[增量方式])下进行遍历也称为 golden data;
// 或者
// key != key (只能发生 key=NANs 的状况下), 这些 key 是没法更新和删除的, 只能在遍历的时候返回。
it.key = k
if t.indirectelem() {
e = *((*unsafe.Pointer)(e))
}
it.elem = e
} else {
// 自从启动迭代器以来，哈希表已经增长。这个 key 的 value 现在位于其他位置。
// 检查当前哈希表中的数据。
// 此代码处理 key 已被删除，更新，删除或重新插入的情况。
// 注意：这里需要重新注册 key ，因为它可能已更新为 equal（）相同但不相同的 key（例如+0.0与-0.0）。
rk, re := mapaccessK(t, h, k)
if rk == nil {
// key 已经被删除
continue
}
it.key = rk
it.elem = re
}
// 后续处理
it.bucket = bucket
if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
it.bptr = b
}
it.i = i + 1
it.checkBucket = checkBucket
return
}
b = b.overflow(t)
i = 0
goto next
}
在上面的遍历过程中有一个特殊情况，如果碰到 key 是 math.NaN() 这种的，处理方式要看它被分裂后具体落入哪个 bucket。只不过只用看它 tophash 的最低位。如果 tophash 的最低位是 0 ，分配到 X part；如果是 1 ，则分配到 Y part。据此决定是否取出 key，放到遍历结果集里。
map 遍历的核心在于理解 2 倍扩容时，老 bucket 会分裂到 2 个新 bucket 中去。而遍历操作，会按照新 bucket 的序号顺序进行，碰到老 bucket 未搬迁的情况时，要在老 bucket 中找到将来要搬迁到新 bucket 来的 key。也就是上面说的当发生了增量扩容时，一个老的 bucket 数据可能会分裂到两个不同的 bucket 中去，那么此时，如果需要从老的 bucket 中遍历数据，例如 1 号，则不能将老 1 号 bucket 中的数据全部取出，仅仅只能取出老 1 号 bucket 中那些在裂变之后，分配到新 1 号 bucket 中的那些 key。
总结以上就是 Map 的相关实现原理，可以看到，它并不是一个并发安全的数据结构。同时对 map 进行读写时，程序很容易出错。因此，要想在并发情况下使用 map，可以加上锁（sync.Mutex 或者 sync.RwMutex）。其实，Go 标准库中已经实现了并发安全的 map——sync.Map。
遍历 map 的结果是无序的，在使用中，应该注意到该点。
通过 map 的结构体可以知道，它其实是通过指针指向底层 buckets 数组。所以和 slice 一样，尽管 go 函数都是值传递，但是，当 map 作为参数被函数调用时，在函数内部对 map 的操作同样会影响到外部的map。
另外，有个特殊的 key 值 math.NaN，它每次生成的哈希值是不一样的，这会造成 m[math.NaN] 是拿不到值的，而且多次对它赋值，会让 map 中存在多个 math.NaN 的 key。
参考文章：
由浅到深，入门Go语言Map实现原理
Go是如何设计Map的
深度解密Go语言之map
深入理解GO语言：map结构原理和源码分析
三万字带你认识 Go 底层 map 的实现
Go 语言设计与实现 3.3 节
