共计 27900 个字符，预计需要花费 70 分钟才能阅读完成。
因为本文篇幅较长，故将目录整顿如下
什么是 Map
维基百科的定义
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type composed of a collection of (key, value) pairs, such that each possible key appears at most once in the collection.
阐明：在计算机科学中，蕴含键值对（key-value）汇合的形象数据结构（关联数组、符号表或字典），其每个可能的键在该汇合中最多呈现一次，这样的数据结构就是一种 Map。
操作
对 Map 的操作次要是增删改查：
- 在汇合中减少键值对
- 在汇合中移除键值对
- 批改某个存在的键值对
- 依据特定的键寻找对应的值
实现
Map 的实现次要有两种形式：哈希表（hash table）和搜寻树（search tree）。例如 Java 中的 hashMap 是基于哈希表实现，而 C ++ 中的 Map 是基于一种均衡搜寻二叉树——红黑树而实现的。以下是不同实现形式的工夫复杂度比照。
能够看到，对于元素查找而言，二叉搜寻树的均匀和最坏效率都是 O(log n)，哈希表实现的均匀效率是 O(1)，但最坏状况下能达到 O(n)，不过如果哈希表设计优良，最坏状况根本不会呈现（所以，读者不想晓得 Go 是如何设计的 Map 吗）。另外二叉搜寻树返回的 key 是有序的，而哈希表则是乱序。
哈希表
因为 Go 中 map 的基于哈希表（也被称为散列表）实现，本文不探讨搜寻树的 map 实现。以下是 Go 官网博客对 map 的阐明。
One of the most useful data structures in computer science is the hash table. Many hash table implementations exist with varying properties, but in general they offer fast lookups, adds, and deletes. Go provides a built-in map type that implements a hash table.
学习哈希表首先要了解两个概念：哈希函数和哈希抵触。
哈希函数
哈希函数（常被称为散列函数）是能够用于将任意大小的数据映射到固定大小值的函数，常见的包含 MD5、SHA 系列等。
一个设计优良的哈希函数应该蕴含以下个性：
- 平均性：一个好的哈希函数应该在其输入范畴内尽可能平均地映射，也就是说，应以大致相同的概率生成输入范畴内的每个哈希值。
- 效率高：哈希效率要高，即便很长的输出参数也能疾速计算出哈希值。
- 可确定性：哈希过程必须是确定性的，这意味着对于给定的输出值，它必须始终生成雷同的哈希值。
- 雪崩效应：渺小的输出值变动也会让输入值产生微小的变动。
- 不可逆：从哈希函数的输入值不可反向推导出原始的数据。
哈希抵触
反复一遍，哈希函数是将任意大小的数据映射到固定大小值的函数。那么，咱们能够预见到，即便哈希函数设计得足够优良，简直每个输出值都能映射为不同的哈希值。然而，当输出数据足够大，大到能超过固定大小值的组合能表白的最大数量数，抵触将不可避免！（参见抽屉原理）
抽屉原理：桌上有十个苹果，要把这十个苹果放到九个抽屉里，无论怎样放，咱们会发现至多会有一个抽屉外面放不少于两个苹果。抽屉原理有时也被称为鸽巢原理。
如何解决哈希抵触
比拟罕用的 Has 抵触解决方案有链地址法和凋谢寻址法。
在讲链地址法之前，先阐明两个概念。
- 哈希桶。哈希桶（也称为槽，相似于抽屉原理中的一个抽屉）能够先简略了解为一个哈希值，所有的哈希值组成了哈希空间。
- 装载因子。装载因子是示意哈希表中元素的填满水平。它的计算公式：装载因子 = 填入哈希表中的元素个数 / 哈希表的长度。装载因子越大，填入的元素越多，空间利用率就越高，但产生哈希抵触的几率就变大。反之，装载因子越小，填入的元素越少，抵触产生的几率减小，但空间节约也会变得更多，而且还会进步扩容操作的次数。装载因子也是决定哈希表是否进行扩容的要害指标，在 java 的 HashMap 的中，其默认装载因子为 0.75；Python 的 dict 默认装载因子为 2 /3。
链地址法
链地址法的思维就是将映射在一个桶里的所有元素用链表串起来。
上面以一个简略的哈希函数 H(key) = key MOD 7（除数取余法）对一组元素 [50, 700, 76, 85, 92, 73, 101] 进行映射，通过图示来了解链地址法解决 Hash 抵触的解决逻辑。
链地址法解决抵触的形式与图的邻接表存储形式在款式上很类似，发生冲突，就用单链表组织起来。
凋谢寻址法
对于链地址法而言，槽位数 m 与键的数目 n 是没有间接关系的。然而对于凋谢寻址法而言，所有的元素都是存储在 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 ;
……
咱们同样以哈希函数 H(key) = key MOD 7（除数取余法）对 [50, 700, 76, 85, 92, 73, 101] 进行映射，通过图示来了解线性探测法解决 Hash 碰撞。
其中，empty 代表槽位为空，occupied 代表槽位已被占（后续映射到该槽，则须要线性向下持续探测），而 lazy delete 则代表将槽位外面的数据革除，并不开释存储空间。
两种解决方案比拟
对于凋谢寻址法而言，它只有数组一种数据结构就可实现存储，继承了数组的长处，对 CPU 缓存敌对，易于序列化操作。然而它对内存的利用率不如链地址法，且发生冲突时代价更高。当数据量明确、装载因子小，适宜采纳凋谢寻址法。
链表节点能够在须要时再创立，不用像凋谢寻址法那样当时申请好足够内存，因而链地址法对于内存的利用率会比开方寻址法高。链地址法对装载因子的容忍度会更高，并且适宜存储大对象、大数据量的哈希表。而且相较于凋谢寻址法，它更加灵便，反对更多的优化策略，比方可采纳红黑树代替链表。然而链地址法须要额定的空间来存储指针。
值得一提的是，在 Python 中 dict 在产生哈希抵触时采纳的凋谢寻址法，而 java 的 HashMap 采纳的是链地址法。
Go Map 实现
同 python 与 java 一样，Go 语言中的 map 是也基于哈希表实现的，它解决哈希抵触的形式是链地址法，即通过应用数组 + 链表的数据结构来表白 map。
留神：本文后续呈现的 map 对立代指 Go 中实现的 map 类型。
map 数据结构
map 中的数据被寄存于一个数组中的，数组的元素是桶（bucket），每个桶至少蕴含 8 个键值对数据。哈希值低位（low-order bits）用于抉择桶，哈希值高位（high-order bits）用于在一个独立的桶中区别出键。哈希值高下位示意图如下
本文基于 go 1.15.2 darwin/amd64 剖析，源码位于 src/runtime/map.go.
- map 的构造体为 hmap
// A header for a Go map.
type hmap struct {count int // 代表哈希表中的元素个数，调用 len(map)时，返回的就是该字段值。flags uint8 // 状态标记，下文常量中会解释四种状态位含意。B uint8 // buckets（桶）的对数 log_2（哈希表元素数量最大可达到装载因子 *2^B）noverflow uint16 // 溢出桶的大略数量。hash0 uint32 // 哈希种子。buckets unsafe.Pointer // 指向 buckets 数组的指针，数组大小为 2^B，如果元素个数为 0，它为 nil。oldbuckets unsafe.Pointer // 如果产生扩容，oldbuckets 是指向老的 buckets 数组的指针，老的 buckets 数组大小是新的 buckets 的 1 /2。非扩容状态下，它为 nil。nevacuate uintptr // 示意扩容进度，小于此地址的 buckets 代表已搬迁实现。extra *mapextra // 这个字段是为了优化 GC 扫描而设计的。当 key 和 value 均不蕴含指针，并且都能够 inline 时应用。extra 是指向 mapextra 类型的指针。- mapextra 的构造体
// mapextra holds fields that are not present on all maps.
type mapextra struct {// 如果 key 和 value 都不蕴含指针，并且能够被 inline(<=128 字节)
// 就应用 hmap 的 extra 字段 来存储 overflow buckets，这样能够防止 GC 扫描整个 map
// 然而 bmap.overflow 也是个指针。这时候咱们只能把这些 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
}- bmap 构造体
// A bucket for a Go map.
type bmap struct {
// tophash 蕴含此桶中每个键的哈希值最高字节（高 8 位）信息（也就是后面所述的 high-order bits）。// 如果 tophash[0] < minTopHash，tophash[0]则代表桶的搬迁（evacuation）状态。tophash [bucketCnt]uint8
}bmap 也就是 bucket（桶）的内存模型图解如下（相干代码逻辑可查看 src/cmd/compile/internal/gc/reflect.go 中的 bmap()函数）。
在以上图解示例中，该桶的第 7 位 cell 和第 8 位 cell 还未有对应键值对。须要留神的是，key 和 value 是各自存储起来的，并非设想中的 key/value/key/value… 的模式。这样做尽管会让代码组织稍显简单，然而它的益处是能让咱们打消例如 map[int64]int 所须要的填充（padding）。此外，在 8 个键值对数据前面有一个 overflow 指针，因为桶中最多只能装 8 个键值对，如果有多余的键值对落到了以后桶，那么就须要再构建一个桶（称为溢出桶），通过 overflow 指针链接起来。
- 重要常量标记
const (
// 一个桶中最多能装载的键值对（key-value）的个数为 8
bucketCntBits = 3
bucketCnt = 1 << bucketCntBits
// 触发扩容的装载因子为 13/2=6.5
loadFactorNum = 13
loadFactorDen = 2
// 键和值超过 128 个字节，就会被转换为指针
maxKeySize = 128
maxElemSize = 128
// 数据偏移量应该是 bmap 构造体的大小，它须要正确地对齐。// 对于 amd64p32 而言，这意味着：即便指针是 32 位的，也是 64 位对齐。dataOffset = unsafe.Offsetof(struct {
b bmap
v int64
}{}.v)
// 每个桶（如果有溢出，则蕴含它的 overflow 的链接桶）在搬迁实现状态（evacuated* states）下，要么会蕴含它所有的键值对，要么一个都不蕴含（但不包含调用 evacuate()办法阶段，该办法调用只会在对 map 发动 write 时产生，在该阶段其余 goroutine 是无奈查看该 map 的）。简略的说，桶里的数据要么一起搬走，要么一个都还未搬。// tophash 除了搁置失常的高 8 位 hash 值，还会存储一些非凡状态值（标记该 cell 的搬迁状态）。失常的 tophash 值，最小应该是 5，以下列出的就是一些非凡状态值。emptyRest = 0 // 示意 cell 为空，并且比它高索引位的 cell 或者 overflows 中的 cell 都是空的。（初始化 bucket 时，就是该状态）emptyOne = 1 // 空的 cell，cell 曾经被搬迁到新的 bucket
evacuatedX = 2 // 键值对曾经搬迁结束，key 在新 buckets 数组的前半部分
evacuatedY = 3 // 键值对曾经搬迁结束，key 在新 buckets 数组的后半局部
evacuatedEmpty = 4 // cell 为空，整个 bucket 曾经搬迁结束
minTopHash = 5 // tophash 的最小正常值
// flags
iterator = 1 // 可能有迭代器在应用 buckets
oldIterator = 2 // 可能有迭代器在应用 oldbuckets
hashWriting = 4 // 有协程正在向 map 写人 key
sameSizeGrow = 8 // 等量扩容
// 用于迭代器查看的 bucket ID
noCheck = 1<<(8*sys.PtrSize) - 1
)综上，咱们以 B 等于 4 为例，展现一个残缺的 map 结构图。
创立 map
map 初始化有以下两种形式
make(map[k]v)
// 指定初始化 map 大小为 hint
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)
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)
}
}
// 即 b 大于等于 4 的状况下，会预调配一些溢出桶。// 为了把跟踪这些溢出桶的开销降至最低，应用了以下约定：// 如果预调配的溢出桶的 overflow 指针为 nil，那么能够通过指针碰撞（bumping the pointer）取得更多可用桶。//（对于指针碰撞：假如内存是相对规整的，所有用过的内存都放在一边，闲暇的内存放在另一边，两头放着一个指针作为分界点的指示器，那所分配内存就仅仅是把那个指针向闲暇空间那边移动一段与对象大小相等的间隔，这种调配形式称为“指针碰撞”）// 对于最初一个溢出桶，须要一个平安的非 nil 指针指向它。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
}根据上述代码，咱们能确定在失常状况下，失常桶和溢出桶在内存中的存储空间是间断的，只是被 hmap 中的不同字段援用而已。
哈希函数
在初始化 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 算法（https://code.google.com/p/xxh…）和 cityhash 算法（https://code.google.com/p/cit…）启发而来，代码别离对应于 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
// 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 通过哈希计算后失去 64bit 位的哈希值。如果 B =5，buckets 数组的长度，即桶的数量是 32（2 的 5 次方）。
例如，现要置一 key 于 map 中，该 key 通过哈希后，失去的哈希值如下：
后面咱们晓得，哈希值低位（low-order bits）用于抉择桶，哈希值高位（high-order bits）用于在一个独立的桶中区别出键。当 B 等于 5 时，那么咱们抉择的哈希值低位也是 5 位，即 01010，它的十进制值为 10，代表 10 号桶。再用哈希值的高 8 位，找到此 key 在桶中的地位。最开始桶中还没有 key，那么新退出的 key 和 value 就会被放入第一个 key 空位和 value 空位。
留神：对于高下位的抉择，该操作的本质是取余，然而取余开销很大，在理论代码实现中采纳的是位操作。以下是 tophash 的实现代码。
func tophash(hash uintptr) uint8 {top := uint8(hash >> (sys.PtrSize*8 - 8))
if top < minTopHash {top += minTopHash}
return top
}当两个不同的 key 落在了同一个桶中，这时就产生了哈希抵触。go 的解决形式是链地址法（这里为了让读者更好了解，只形容非扩容且该 key 是第一次增加的状况）：在桶中依照程序寻到第一个空位并记录下来，后续在该桶和它的溢出桶中均未发现存在的该 key，将 key 置于第一个空位；否则，去该桶的溢出桶中寻找空位，如果没有溢出桶，则增加溢出桶，并将其置溢出桶的第一个空位（因为是第一次增加，所以不形容已存在该 key 的状况）。
上图中的 B 值为 5，所以桶的数量为 32。通过哈希函数计算出待插入 key 的哈希值，低 5 位哈希 00110，对应于 6 号桶；高 8 位 10010111，十进制为 151，因为桶中前 6 个 cell 曾经有失常哈希值填充了(遍历)，所以将 151 对应的高位哈希值搁置于第 7 位 cell，对应将 key 和 value 别离置于相应的第七个空位。
如果是查找 key，那么咱们会依据高位哈希值去桶中的每个 cell 中找，若在桶中没找到，并且 overflow 不为 nil，那么持续去溢出桶中寻找，直至找到，如果所有的 cell 都找过了，还未找到，则返回 key 类型的默认值（例如 key 是 int 类型，则返回 0）。
查找 key
对于 map 的元素查找，其源码实现如下
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 算法，可详见 src/runtime/alg.go 中 typehash 函数中的逻辑
hash := t.hasher(key, uintptr(h.hash0))
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() {m >>= 1}
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)
// 以下是查找的外围逻辑
// 双重循环遍历：外层循环是从桶到溢出桶遍历；内层是桶中的 cell 遍历
// 跳出循环的条件有三种：第一种是曾经找到 key 值；第二种是以后桶再无溢出桶；// 第三种是以后桶中有 cell 位的 tophash 值是 emptyRest，这个值在后面解释过，它代表此时的桶前面的 cell 还未利用，所以无需再持续遍历。bucketloop:
for ; b != nil; b = b.overflow(t) {for i := uintptr(0); i < bucketCnt; i++ {
// 判断 tophash 值是否相等
if b.tophash[i] != top {if b.tophash[i] == emptyRest {break bucketloop}
continue
}
// 因为在 bucket 中 key 是用间断的存储空间存储的，因而能够通过 bucket 地址 + 数据偏移量（bmap 构造体的大小）+ keysize 的大小，失去 k 的地址
// 同理，value 的地址也是类似的计算方法，只是再要加上 8 个 keysize 的内存地址
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {k = *((*unsafe.Pointer)(k))
}
// 判断 key 是否相等
if t.key.equal(key, k) {e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
if t.indirectelem() {e = *((*unsafe.Pointer)(e))
}
return e
}
}
}
// 所有的 bucket 都未找到，则返回零值
return unsafe.Pointer(&zeroVal[0])
}以下是 mapaccess1 的查找过程图解
map 的元素查找，对应 go 代码有两种模式
// 模式一
v := m[k]
// 模式二
v, ok := m[k]模式一的代码实现，就是上述的 mapaccess1 办法。此外，在源码中还有个 mapaccess2 办法，它的函数签名如下。
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {}与 mapaccess1 相比，mapaccess2 多了一个 bool 类型的返回值，它代表的是是否在 map 中找到了对应的 key。因为和 mapaccess1 基本一致，所以具体代码就不再贴出。
同时，源码中还有 mapaccessK 办法，它的函数签名如下。
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {}与 mapaccess1 相比，mapaccessK 同时返回了 key 和 value，其代码逻辑也统一。
赋值 key
对于写入 key 的逻辑，其源码实现如下
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")
}
// 通过 key 和哈希种子，算出对应哈希值
hash := t.hasher(key, uintptr(h.hash0))
// 将 flags 的值与 hashWriting 做按位或运算
// 因为在以后 goroutine 可能还未实现 key 的写入，再次调用 t.hasher 会产生 panic。h.flags ^= hashWriting
if h.buckets == nil {h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
again:
// bucketMask 返回值是 2 的 B 次方减 1
// 因而，通过 hash 值与 bucketMask 返回值做按位与操作，返回的在 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 {
// 如果 cell 位为空，那么就能够在对应地位进行插入
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.elemsize))
}
if b.tophash[i] == emptyRest {break bucketloop}
continue
}
// 第二种状况是 cell 位的 tophash 值和以后的 tophash 值相等
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
if t.indirectkey() {k = *((*unsafe.Pointer)(k))
}
// 留神，即便以后 cell 位的 tophash 值相等，不肯定它对应的 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 的完结逻辑中去
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 // Growing the table invalidates everything, so try again
}
// 状况二：// 在不满足状况一的条件下，会为以后桶再新建溢出桶，并将 tophash，key 插入到新建溢出桶的对应内存的 0 号地位
if inserti == nil {
// all current buckets are full, allocate a new one.
newb := h.newoverflow(t, b)
inserti = &newb.tophash[0]
insertk = add(unsafe.Pointer(newb), dataOffset)
elem = add(insertk, bucketCnt*uintptr(t.keysize))
}
// 在插入地位存入新的 key 和 value
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
// map 中的 key 数量 +1
h.count++
done:
if h.flags&hashWriting == 0 {throw("concurrent map writes")
}
h.flags &^= hashWriting
if t.indirectelem() {elem = *((*unsafe.Pointer)(elem))
}
return elem
}通过对 mapassign 的代码剖析之后，发现该函数并没有将插入 key 对应的 value 写入对应的内存，而是返回了 value 应该插入的内存地址。为了弄清楚 value 写入内存的操作是产生在什么时候，剖析如下 map.go 代码。
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 配合，能力实现一些简单的工作。同时阐明，在平时学习 go 的源代码实现时，必要时还须要看一些汇编代码。
删除 key
了解了赋值 key 的逻辑，删除 key 的逻辑就比较简单了。本文就不再探讨该局部内容了，读者感兴趣能够自行查看 src/runtime/map.go 的 mapdelete 办法逻辑。
遍历 map
论断：迭代 map 的后果是无序的
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 的后果就不可能是依照原来的程序了（详见下文的 map 扩容内容）。
但其实，go 为了保障遍历 map 的后果是无序的，做了以下事件：map 在遍历时，并不是从固定的 0 号 bucket 开始遍历的，每次遍历，都会从一个 随机值序号的 bucket，再从其中 随机的 cell开始遍历。而后再依照桶序遍历上来，直到回到起始桶完结。
上图的例子，是遍历一个处于未扩容状态的 map。如果 map 正处于扩容状态时，须要先判断以后遍历 bucket 是否曾经实现搬迁，如果数据还在老的 bucket，那么就去老 bucket 中拿数据。
留神：在下文中会解说到增量扩容和等量扩容。当产生了增量扩容时，一个老的 bucket 数据可能会决裂到两个不同的 bucket 中去，那么此时，如果须要从老的 bucket 中遍历数据，例如 1 号，则不能将老 1 号 bucket 中的数据全副取出，仅仅只能取出老 1 号 bucket 中那些在裂变之后，调配到新 1 号 bucket 中的那些 key（这个内容，请读者看完下文 map 扩容的解说之后再回头了解）。
鉴于篇幅起因，本文不再对 map 遍历的具体源码进行正文贴出。读者可自行查看源码 src/runtime/map.go 的 mapiterinit() 和mapiternext()办法逻辑。
这里正文一下 mapiterinit() 中随机保障的要害代码
// 生成随机数
r := uintptr(fastrand())
if h.B > 31-bucketCntBits {r += uintptr(fastrand()) << 31
}
// 决定了从哪个随机的 bucket 开始
it.startBucket = r & bucketMask(h.B)
// 决定了每个 bucket 中随机的 cell 的地位
it.offset = uint8(r >> h.B & (bucketCnt - 1))map 扩容
在文中解说装载因子时，咱们提到装载因子是决定哈希表是否进行扩容的要害指标。在 go 的 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），再决定是否进行搬迁工作。
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 (atomic wrt gc)
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 {
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，一次性搬迁将会造成比拟大的延时，因而才采纳逐渐搬迁策略。
在解说该逻辑之前，须要读者先了解以下两个知识点。
- 知识点 1：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 次方。
- 知识点 2：确定搬迁区间
在源码中，有 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）。
这里留一个问题：为什么确定 key 落在哪个区间很重要？
确定了要搬迁到的指标 bucket 后，搬迁操作就比拟好进行了。将源 key/value 值 copy 到目的地相应的地位。设置 key 在原始 buckets 的 tophash 为 evacuatedX 或是 evacuatedY，示意曾经搬迁到了新 map 的 bucket x 或是 bucket y，新 map 的 tophash 则失常取 key 哈希值的高 8 位。
上面正式解读搬迁外围代码 evacuate() 函数。
evacuate()函数
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
// 首先定位老的 bucket 的地址
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
// newbit 代表扩容之前老的 bucket 个数
newbit := h.noldbuckets()
// 判断该 bucket 是否曾经被搬迁
if !evacuated(b) {
// 官网 TODO，后续版本兴许会实现
// TODO: reuse overflow buckets instead of using new ones, if there
// is no iterator using the old buckets. (If !oldIterator.)
// xy 蕴含了高下区间的搬迁目的地内存信息
// 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)) {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)
// 对于失常 key，进入以下 else 逻辑
} else {
if hash&newbit != 0 {useY = 1}
}
}
if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {throw("bad evacuatedN")
}
// evacuatedX + 1 == evacuatedY
b.tophash[i] = evacuatedX + useY
// useY 要么为 0，要么为 1。这里就是选取在 bucket x 的起始内存地位，或者抉择在 bucket y 的起始内存地位（只有增量同步才会有这个抉择可能）。dst := &xy[useY]
// 如果目的地的桶曾经装满了（8 个 cell），那么须要新建一个溢出桶，持续搬迁到溢出桶下来。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
// 如果待搬迁的 key 是指针，则复制指针过来
if t.indirectkey() {*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
// 如果待搬迁的 key 是值，则复制值过来
} else {typedmemmove(t.key, dst.k, k) // copy elem
}
// value 和 key 同理
if t.indirectelem() {*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
} else {typedmemmove(t.elem, dst.e, e)
}
// 将以后搬迁目标桶的记录 key/value 的索引值（也能够了解为 cell 的索引值）加一
dst.i++
// 因为桶的内存布局中在最初还有 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)
}
}
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 {
// 搬迁结束，所以指向老的 buckets 的指针置为 nil
h.oldbuckets = nil
// 在解说 hmap 的构造中，有过阐明。如果 key 和 value 均不蕴含指针，则都能够 inline。// 那么保留它们的 buckets 数组其实是挂在 hmap.extra 中的。所以，这种状况下，其实咱们是搬迁的 extra 的 buckets 数组。// 因而，在这种状况下，须要在搬迁结束后，将 hmap.extra.oldoverflow 指针置为 nil。if h.extra != nil {h.extra.oldoverflow = nil}
// 最初，革除正在扩容的标记位，扩容结束。h.flags &^= sameSizeGrow
}
}代码比拟长，然而文中正文曾经比拟清晰了，如果对 map 的扩容还不分明，能够参见以下图解。
针对上图的 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 落在哪个区间很重要？因为对于增量扩容而言，本来一个 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 应该插入的内存地址。
总结
Go 语言的 map，底层是哈希表实现的，通过链地址法解决哈希抵触，它依赖的外围数据结构是数组加链表。
map 中定义了 2 的 B 次方个桶，每个桶中可能包容 8 个 key。依据 key 的不同哈希值，将其散落到不同的桶中。哈希值的低位（哈希值的后 B 个 bit 位）决定桶序号，高位（哈希值的前 8 个 bit 位）标识同一个桶中的不同 key。
当向桶中增加了很多 key，造成元素过多，超过了装载因子所设定的水平，或者屡次增删操作，造成溢出桶过多，均会触发扩容。
扩容分为增量扩容和等量扩容。增量扩容，会减少桶的个数（增加一倍），把原来一个桶中的 keys 被重新分配到两个桶中。等量扩容，不会更改桶的个数，只是会将桶中的数据变得紧凑。不论是增量扩容还是等量扩容，都须要创立新的桶数组，并不是原地操作的。
扩容过程是渐进性的，次要是避免一次扩容须要搬迁的 key 数量过多，引发性能问题。触发扩容的机会是减少了新元素，桶搬迁的机会则产生在赋值、删除期间，每次最多搬迁两个 桶。查找、赋值、删除的一个很外围的内容是如何定位到 key 所在的地位，须要重点了解。一旦了解，对于 map 的源码就可以看懂了。
应用倡议
从 map 设计能够晓得，它并不是一个并发平安的数据结构。同时对 map 进行读写时，程序很容易出错。因而，要想在并发状况下应用 map，请加上锁（sync.Mutex 或者 sync.RwMutex）。其实，Go 规范库中曾经为咱们实现了并发平安的 map——sync.Map，我之前写过文章对它的实现进行解说，详情能够查看公号：Golang 技术分享——《深刻了解 sync.Map》一文。
遍历 map 的后果是无序的，在应用中，应该留神到该点。
通过 map 的构造体能够晓得，它其实是通过指针指向底层 buckets 数组。所以和 slice 一样，只管 go 函数都是值传递，然而，当 map 作为参数被函数调用时，在函数外部对 map 的操作同样会影响到内部的 map。
另外，有个非凡的 key 值 math.NaN，它每次生成的哈希值是不一样的，这会造成 m[math.NaN]是拿不到值的，而且屡次对它赋值，会让 map 中存在多个 math.NaN 的 key。不过这个根本用不到，晓得有这个非凡状况就能够了。
参考链接
https://en.wikipedia.org/wiki…
https://blog.golang.org/maps
https://mp.weixin.qq.com/s/OH…
https://www.cse.cuhk.edu.hk/i…
https://github.com/cch123/gol…
https://zhuanlan.zhihu.com/p/…
https://draveness.me/golang/d…
https://github.com/talkgo/nig…
https://my.oschina.net/renhc/…
