万字剖析Golang的map实现原理

0、引言


信赖各人对Map这个数据结构都不陌生，像C++的map、Java的HashMap。各个语言的底层实现各有不同，在本篇博客中，我将分享个人对Go的map实现的明确，以及深入源码进行分析，信赖耐心看完一定会收获不少。

1、宏观结构


信赖各人对于map的基本使用都不陌生，Golang中的map是不允许并发写操纵的，这里的写指代的是宏观意义上的“写”，包括了更新、插入、删除操纵。当发生了并发写时，程序会抛出fatal，这是一个非常严峻的错误，会直接克制程序的进行，因此对于同一个map，它不应该被共享到多个协程中。

我们可以通过以下代码来验证：

1. func main() {
2.         hm := map[int]int{1: 1, 2: 2, 3: 3}
3.         for i := 4; i <= 9999; i++ {
4.                 go func(num int) {
5.                         hm[i] = i
6.                 }(i)
7.         }
8. }

复制代码

程序很快就会报错，因为我们有多个协程同时对map进行写入操纵。

那么map是怎么保存键值对的呢？

起首，我们得知道map的宏观结构，Go对map的计划采用了桶的思想，有一组组桶来装KV对，而且规定一个桶只能装8个KV对。

例如我们把KV1和KV2放在桶1中，KV3放在桶2中。假如我们有许多个KV对，只要桶够多，把它们分散在各个桶中，那么就能将O(N)的时间复杂度缩小到O(N/bucketsNum)了，只要给定符合的桶数，时间复杂度就≈O(1)。

于是，我们要办理两个标题：

• 如何找到一个KV对对应的桶？
  
• 如何保证桶平均下来的KV对数量都是合理的呢？
  

1.1、如何找到桶？


1、对于第一个标题，接纳的措施是使用哈希映射来办理。

假如我们有如许一个函数，它可以使得对于任意长度的输入，都压缩到一个固定长度的输出，而且对于相同的输入，输出必定是一样的。如许子的函数叫做哈希函数，即hash func。详细的可以去网上了解。那么在Go中，它会先求出每个KV的hash值，例如对于一个键值对「“Hello”：“World”」，求出它的hash值为100111101，那么只要对桶数取模即可找到对应的桶了。

对此，我们对hash函数的选取需要有一定的要求，它必须满意以下的性质：

• hash的可重入性：相同的key，必定产生相同的hash值
  
• hash的离散性：只要两个key不相同，岂论相似度的高低，产生的hash值都会在整个输出域内匀称地离散化
  
• hash的单向性：不可通过hash值反向寻找key
  

但是，根据hash的性质，因为输入是无限的，但是输出的长度却是固定有限的，所以必然会存在两个不同的key通过映射到了同一个hash值的环境上，这种环境称之为hash辩论。对于Go对hash辩论接纳的策略，将会在下文提及。

1.2、如何保证桶平均的KV对数量是合理的？


对于这个标题，我们必须接纳一个措施来量化目前的存储状态是否合理。在Go中，引入了负载因子（Load Factor）的概念，对于一个map，假如存在count个键值对，2^B个桶，那么它必须满意以下方程：「count <=LoadFactor*(2^B)」，当count的值凌驾这个界限，就会引发map的扩容机制。LoadFactor在Go中，一样平常取值为6.5。

1.3、桶结构


一个map会维护一个桶数组，桶数组中含有多个桶，每个桶可以存放八个键值对，以及一个指向其溢出桶的指针。用图表示如下：

对于一个桶，含有八个槽位（slot），一个槽位可以放置一对键值对以及它的hash值。在桶的末尾含有一个overflow指针，指向它的溢出桶。

针对哈希辩论，接纳的措施紧张有两种：

• 拉链法：将多个命中到同一个桶的键值对，按照插入顺序依次存放在桶中。
  
• 开放寻址法：对于命中到同一个桶的多个键值对，接纳向后寻找，知道找到空的桶再将值放入其中
  

我们来对比两种策略的长处：
显然，Go接纳的是拉链法，桶数组中的每一个桶，严酷来说应该是一个链表结构的桶数组，它通过overflow指针链接上了下一个溢出桶，使得多个键值对能存放在同一个桶中。若当前桶八个槽位都满了，就开辟一个新的溢出桶，放置在溢出桶里面。

1.4、数据结构界说


结构界说如下：

1. type hmap struct {
2.         count     int // # live cells == size of map.  Must be first (used by len() builtin)
3.         flags     uint8
4.         B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
5.         noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
6.         hash0     uint32 // hash seed
8.         buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
9.         oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
10.         nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
12.         extra *mapextra // optional fields
13. }

复制代码

• count：标识当前map的键值对数量
  
• flags：标识当前map的状态
  
• B：2^B为map目前的总桶数
  
• noverflow：溢出桶数量
  
• hash0：哈希因子
  
• buckets：指向桶数组
  
• oldbuckets：扩容时存储旧的桶数组
  
• nevacuate：待完成数据迁移的桶下标
  
• extra：存储预分配的溢出桶
  

mapextra的界说如下：

1. type mapextra struct {
2.         overflow    *[]*bmap
3.         oldoverflow *[]*bmap
5.         nextOverflow *bmap
6. }

复制代码

• overflow：指向新的预分配溢出桶数组
  
• oldoverflow：指向旧的预分配溢出桶数组
  
• nextoverflow：指向下一个可被使用的溢出桶
  

而bmap是一个桶的详细实现，源码如下：

1. type bmap struct {
2.         tophash [bucketCnt]uint8
3. }

复制代码

虽然在数据界说上，只含有一个tophash，但是在内存上，可以通过直接计算得出下一个槽的位置，以及overflow指针的位置。所以为了便于明确，它的实际结构如下：

1. type bmap struct {
2.         tophash [bucketCnt]uint8
3.         keys [bucketCnt]T
4.     values [bucketCnt]T
5.     overflow unsafe.Pointer
6. }

复制代码

接下来，让我们步入map的主干流程，了解它的机制实现。

2、主干流程


2.1、map的创建与初始化

1. //makemap为make(map[k]v,hint)实现Go映射创建
2. func makemap(t *maptype, hint int, h *hmap) *hmap {
3.         mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
4.         if overflow || mem > maxAlloc {
5.                 hint = 0
6.         }
8.         // initialize Hmap
9.         if h == nil {
10.                 h = new(hmap)
11.         }
12.         h.hash0 = uint32(rand())
14.         // Find the size parameter B which will hold the requested # of elements.
15.         // For hint < 0 overLoadFactor returns false since hint < bucketCnt.
16.         B := uint8(0)
17.         for overLoadFactor(hint, B) {
18.                 B++
19.         }
20.         h.B = B
21.        
22.     //若B==0，那么buckets将会采取懒创建的策略，会在未来要写map的方法mapassign中创建。
23.         if h.B != 0 {
24.                 var nextOverflow *bmap
25.                 h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
26.                 if nextOverflow != nil {
27.                         h.extra = new(mapextra)
28.                         h.extra.nextOverflow = nextOverflow
29.                 }
30.         }
32.         return h
33. }

复制代码

（1）makemap起首根据预分配的容量巨细hint进行分配容量，若容量过大，则会置hint为0；

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

复制代码

math.MulUintptr实现如下：

1. func MulUintptr(a, b uintptr) (uintptr, bool) {
2.         if a|b < 1<<(4*goarch.PtrSize) || a == 0 {
3.                 return a * b, false
4.         }
5.         overflow := b > MaxUintptr/a
6.         return a * b, overflow
7. }

复制代码

返回的两个值为：

• 计算二值的乘积a*b
  
• 乘积是否溢出
  

如果a|b的二进制表示，没有凌驾1<<(4*goarch.PtrSize)，那么它们的乘积也不会溢出。在64位操纵体系中，goarch.PtrSize的巨细为8。否则，则通过a*b>MaxUintptr来判断，MaxUintptr为2^64-1.

（2）通过new方法，初始化hmap

1. // initialize Hmap
2.         if h == nil {
3.                 h = new(hmap)
4.         }

复制代码

（3）通过rand()生成一个哈希因子

1. h.hash0 = uint32(rand())

复制代码

（4）获取哈希表的桶数量标对数B。（留意这里并不是直接计算log_2_hint，是要根据负载因子衡量桶的数量）

1. B := uint8(0)
2.         for overLoadFactor(hint, B) {
3.                 B++
4.         }
5.         h.B = B

复制代码

Go中存在一个特别的参数即“负载因子”，它用于衡量哈希表的填充程度，负载因子越高，哈希表的空间使用率越高，但辩论的概率也会变大，性能大概下降。在Go中，该因子值为6.5。

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

复制代码

在这里，bucketCnt为8。若count<=8，则直接返回false，只需要将键值对放在一个桶中即可。否则，计算当前的哈希表的容量*负载因子，若count的数量＞这个值，将会扩容哈希表，即增大B。

假如count为60，那么B终极为4。

（5）若B!=0，初始化哈希表，使用makeBucketArray方法构造桶数组。

1. if h.B != 0 {
2.                 var nextOverflow *bmap
3.                 h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
4.                 if nextOverflow != nil {
5.                         h.extra = new(mapextra)
6.                         h.extra.nextOverflow = nextOverflow
7.                 }
8.         }

复制代码

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

2.1.1、makeBucketArray方法

1. func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
2.     //初始桶数量
3.         base := bucketShift(b)
4.     //最终桶数量，初始和base相同
5.         nbuckets := base
6.         //溢出桶预分配
7.         if b >= 4 {
8.                 nbuckets += bucketShift(b - 4)
9.         //计算分配的总内存大小
10.                 sz := t.Bucket.Size_ * nbuckets
11.         //将内存大小向上对齐到合适的大小，是内存分配的一个优化。
12.                 up := roundupsize(sz, t.Bucket.PtrBytes == 0)
13.                 if up != sz {
14.             //调整桶数量，使得内存被充分利用
15.                         nbuckets = up / t.Bucket.Size_
16.                 }
17.         }
19.         if dirtyalloc == nil {
20.         //分配nbuckets个桶
21.                 buckets = newarray(t.Bucket, int(nbuckets))
22.         } else {
23.                 //复用旧的内存
24.                 buckets = dirtyalloc
25.                 size := t.Bucket.Size_ * nbuckets
26.                 if t.Bucket.PtrBytes != 0 {
27.                         memclrHasPointers(buckets, size)
28.                 } else {
29.                         memclrNoHeapPointers(buckets, size)
30.                 }
31.         }
33.         if base != nbuckets {
34.                 //如果base和nbuckets的数量不同，说明预分配了溢出桶，需要设置溢出桶链表
35.         //指向第一个可用的预分配溢出桶，计算出溢出桶的起始位置
36.                 nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))
37.         //最后一个预分配的溢出桶的位置
38.                 last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))
39.         //将最后一个溢出桶的指针设置为buckets，形成一个环形链表，用于后面的分配判断
40.                 last.setoverflow(t, (*bmap)(buckets))
41.         }
42.         return buckets, nextOverflow
43. }

复制代码

makeBucketArray方法会根据初始的对数B来判断是否需要分配溢出桶。若B>=4，则需要预分配的溢出桶数量为2^(B-4)。确定好桶的总数后，会根据dirtyalloc是否为nil来判断是否需要新开辟空间。末了会返回指向桶数组的指针以及指向首个溢出桶位置的指针。

当末了返回到上层的makemap方法中，终极创造出的map结构如图：

2.2、map的读流程


2.2.1、读流程步调总览


大致流程如下：
1、查抄表是否为nil，或者表是否没有元素，如果则直接返回零值。
2、若处在并发写状态，则会导致程序瓦解（fatal）。
3、计算key对应的hash值，而且定位到对应的桶上。
4、若数据在旧桶，且数据没有迁移到新桶中，就在旧桶查找，否则在新桶中查找。
5、外层遍历桶数组的每个桶，内层遍历桶的每个kv对，找到了就返回value，否则返回零值

2.2.2、源码跟进mapaccess1

1. func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
2.         //...
3.         if h == nil || h.count == 0 {
4.                 if err := mapKeyError(t, key); err != nil {
5.                         panic(err) // see issue 23734
6.                 }
7.                 return unsafe.Pointer(&zeroVal[0])
8.         }
9.         if h.flags&hashWriting != 0 {
10.                 fatal("concurrent map read and map write")
11.         }
12.         hash := t.Hasher(key, uintptr(h.hash0))
13.         m := bucketMask(h.B)
14.         b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))
15.         if c := h.oldbuckets; c != nil {
16.                 if !h.sameSizeGrow() {
17.                         // There used to be half as many buckets; mask down one more power of two.
18.                         m >>= 1
19.                 }
20.                 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))
21.                 if !evacuated(oldb) {
22.                         b = oldb
23.                 }
24.         }
25.         top := tophash(hash)
26. bucketloop:
27.         for ; b != nil; b = b.overflow(t) {
28.                 for i := uintptr(0); i < bucketCnt; i++ {
29.                         if b.tophash[i] != top {
30.                                 if b.tophash[i] == emptyRest {
31.                                         break bucketloop
32.                                 }
33.                                 continue
34.                         }
35.                         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
36.                         if t.IndirectKey() {
37.                                 k = *((*unsafe.Pointer)(k))
38.                         }
39.                         if t.Key.Equal(key, k) {
40.                                 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
41.                                 if t.IndirectElem() {
42.                                         e = *((*unsafe.Pointer)(e))
43.                                 }
44.                                 return e
45.                         }
46.                 }
47.         }
48.         return unsafe.Pointer(&zeroVal[0])
49. }

复制代码

（1）若哈希表为空，或不存在键值对，则会返回零值。在此之前，会查抄key是否合法，非法会触发panic。

1. if h == nil || h.count == 0 {
2.                 if err := mapKeyError(t, key); err != nil {
3.                         panic(err) // see issue 23734
4.                 }
5.                 return unsafe.Pointer(&zeroVal[0])
6.         }

复制代码

（2）若存在并发写map，会立即报错，使得程序克制运行。flags的第3个bit位标识map是否处于并发写状态。

1. hashWriting  = 4 // a goroutine is writing to the map 4->100
2. if h.flags&hashWriting != 0 {
3.                 fatal("concurrent map read and map write")
4.         }

复制代码

（3）计算key的hash值，而且对桶数量取模，定位到详细的桶。取模运算为x & (mod-1)，只有mod为2的幂时可以加快。

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

复制代码

（4）查抄是否存在旧桶，存在旧桶且数据未搬迁完成则去旧桶中找key，否则在新桶找。

1. if c := h.oldbuckets; c != nil { //c!=nil，说明旧桶未完成迁移（rehash）
2.                 if !h.sameSizeGrow() { //是否是等量扩容
3.                         //如果不是等量扩容，调整 hash 掩码（mask）
4.                         m >>= 1
5.                 }
6.                 oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize)))//计算旧桶地址
7.                 if !evacuated(oldb) { //检查旧桶是否已搬迁
8.                         b = oldb //未搬迁则数据有效
9.                 }
10.         }

复制代码

在取旧桶的时候，会根据evacuated判断数据是否已经迁移到新的桶：判断方法是取桶首个元素的tophash值，若值为2,3,4中的一个，代表数据已经迁移完成。

1. const emptyOne = 1
2. const evacuatedX = 2
3. const evacuatedY = 3
4. const evacuatedEmpty = 4
5. const minTopHash = 5
6. func evacuated(b *bmap) bool {
7.         h := b.tophash[0]
8.         return h > emptyOne && h < minTopHash
9. }

复制代码

（5）取key的hash值的高8位值top，若值<5则累加5，避开0~4，这些值会用于枚举，存在一些特殊的含义。

1. top := tophash(hash)

复制代码

1. func tophash(hash uintptr) uint8 {
2.         top := uint8(hash >> (goarch.PtrSize*8 - 8))
3.         if top < minTopHash {
4.                 top += minTopHash
5.         }
6.         return top
7. }

复制代码

（6）外层b遍历每一个桶，内层遍历b中的每一个kv对，对比每一个kv对的tophash值是否和要查询的key的top值是否相同进行查找。

1. for ; b != nil; b = b.overflow(t) {
2.                 for i := uintptr(0); i < bucketCnt; i++ {
3.                         //...
4.                 }
5.         }

复制代码

若两个hash值不同，而且桶中的当前键值对的tophash为0，表示后续没有元素，直接退出循环返回零值。否则查抄下一个kv。

1. if b.tophash[i] != top {
2.                                 if b.tophash[i] == emptyRest {
3.                                         break bucketloop
4.                                 }
5.                                 continue
6.                         }

复制代码

若找到了，就根据内存偏移找到对应的value而且返回。留意：会调用key.Equal方法详细查抄要读的key和当前key是否一样，避免因为哈希辩论导致读取了错误的value。

1. k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
2.                         if t.IndirectKey() {
3.                                 k = *((*unsafe.Pointer)(k))
4.                         }
5.                         if t.Key.Equal(key, k) {
6.                                 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
7.                                 if t.IndirectElem() {
8.                                         e = *((*unsafe.Pointer)(e))
9.                                 }
10.                                 return e
11.                         }

复制代码

否则终极返回0值。

1. return unsafe.Pointer(&zeroVal[0])

复制代码

2.3、map的写流程


2.3.1、写流程步调总览


大致流程如下：

• 1、若表为nil，则panic，若处在并发写，则fatal
  
• 2、获取key的hash值，用于校验是否已经存在，需要覆盖
  
• 3、设置处于写状态
  
• 4、懒创建buckets，若B==0，则buckets会在第一次写的时候创建
  
• 5、根据hash定位到详细的bucket中，若表处在扩容阶段则调用growWork辅助扩容；创建三个拟插入位置指针，分别存储要插入的tophash、key、value的位置。（作用是若遇见空位置，就存储，然后要继承看是否存在相同的key要覆盖。）
  
• 6、遍历该桶的每一个kv，会遇到两种环境：
  若当前槽位的tophash和要插入的键值对的tophash不相同，那么查抄是否是空槽，是则更新拟存储指针；若当前槽位是空槽，会继承查抄对背面是否存在kv的标识，若背面全是空槽了，就可以直接退出了不必继承遍历。
  若相同，那就直接进行覆盖操纵，更新完成直接到第10步进行收尾。
  
• 7、如果我们没有找到要插入的位置，或者要插入的位置是当前桶的末了一个槽位，查抄以下条件决定是否进行扩容：
  Count+1 > loadfactor * 2^h.B，即总键值对 > 负载因子*总桶数
  h.noverflow > threshold：如果 溢出桶过多，说明辩论严峻，也要扩容。
  发生扩容后，刚刚的记录就无效了，重新到第5步。
  
• 8、若不扩容，且没有插入的位置（没有空槽，也没有覆盖），就新创建一个新桶，连接到当前桶的背面作为溢出桶，插入到新桶的第一个位置上。这个新桶可以是新分配的，也可以是一开始创建表就预分配的（优先）。
  
• 9、对拟插入的位置进行实际的插入
  
• 10、收尾，再次查抄是否处在并发写状态，是则fatal，否则重置写状态标识，然退却出。
  

2.3.2、源码跟进mapassign

1. func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
2.         if h == nil {
3.                 panic(plainError("assignment to entry in nil map"))
4.         }
5.         //...
6.         if h.flags&hashWriting != 0 {
7.                 fatal("concurrent map writes")
8.         }
9.         hash := t.Hasher(key, uintptr(h.hash0))
11.         // Set hashWriting after calling t.hasher, since t.hasher may panic,
12.         // in which case we have not actually done a write.
13.         h.flags ^= hashWriting
15.         if h.buckets == nil {
16.                 h.buckets = newobject(t.Bucket) // newarray(t.Bucket, 1)
17.         }
19. again:
20.         bucket := hash & bucketMask(h.B)
21.         if h.growing() {
22.                 growWork(t, h, bucket)
23.         }
24.         b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
25.         top := tophash(hash)
27.         var inserti *uint8
28.         var insertk unsafe.Pointer
29.         var elem unsafe.Pointer
30. bucketloop:
31.         for {
32.                 for i := uintptr(0); i < bucketCnt; i++ {
33.                         if b.tophash[i] != top {
34.                                 if isEmpty(b.tophash[i]) && inserti == nil {
35.                                         inserti = &b.tophash[i]
36.                                         insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
37.                                         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
38.                                 }
39.                                 if b.tophash[i] == emptyRest {
40.                                         break bucketloop
41.                                 }
42.                                 continue
43.                         }
44.                         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
45.                         if t.IndirectKey() {
46.                                 k = *((*unsafe.Pointer)(k))
47.                         }
48.                         if !t.Key.Equal(key, k) {
49.                                 continue
50.                         }
51.                         // already have a mapping for key. Update it.
52.                         if t.NeedKeyUpdate() {
53.                                 typedmemmove(t.Key, k, key)
54.                         }
55.                         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
56.                         goto done
57.                 }
58.                 ovf := b.overflow(t)
59.                 if ovf == nil {
60.                         break
61.                 }
62.                 b = ovf
63.         }
65.         // Did not find mapping for key. Allocate new cell & add entry.
67.         // If we hit the max load factor or we have too many overflow buckets,
68.         // and we're not already in the middle of growing, start growing.
69.         if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
70.                 hashGrow(t, h)
71.                 goto again // Growing the table invalidates everything, so try again
72.         }
74.         if inserti == nil {
75.                 // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
76.                 newb := h.newoverflow(t, b)
77.                 inserti = &newb.tophash[0]
78.                 insertk = add(unsafe.Pointer(newb), dataOffset)
79.                 elem = add(insertk, bucketCnt*uintptr(t.KeySize))
80.         }
82.         // store new key/elem at insert position
83.         if t.IndirectKey() {
84.                 kmem := newobject(t.Key)
85.                 *(*unsafe.Pointer)(insertk) = kmem
86.                 insertk = kmem
87.         }
88.         if t.IndirectElem() {
89.                 vmem := newobject(t.Elem)
90.                 *(*unsafe.Pointer)(elem) = vmem
91.         }
92.         typedmemmove(t.Key, insertk, key)
93.         *inserti = top
94.         h.count++
96. done:
97.         if h.flags&hashWriting == 0 {
98.                 fatal("concurrent map writes")
99.         }
100.         h.flags &^= hashWriting
101.         if t.IndirectElem() {
102.                 elem = *((*unsafe.Pointer)(elem))
103.         }
104.         return elem
105. }

复制代码

（1）错误处理惩罚：map为空则panic，并发写则出发fatal。

1. if h == nil {
2.                 panic(plainError("assignment to entry in nil map"))
3.         }
4.         //...
5.         if h.flags&hashWriting != 0 {
6.                 fatal("concurrent map writes")
7.         }
8.         hash := t.Hasher(key, uintptr(h.hash0))

复制代码

（2）标识map处在写的状态，而且懒创建桶。

1. h.flags ^= hashWriting
3.         if h.buckets == nil {
4.                 h.buckets = newobject(t.Bucket) // newarray(t.Bucket, 1)
5.         }

复制代码

（3）获取当前key对应的桶的桶索引

1. bucket := hash & bucketMask(h.B)

复制代码

（4）若发现当前map处在扩容状态，则资助其渐进扩容。详细在下文中提及。

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

复制代码

（5）进行地址偏移，定位到详细的桶b

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

复制代码

（6）计算tophash

1. top := tophash(hash)

复制代码

（7）提前声明三个指针，用于指向存放kv对槽位

1. var inserti *uint8 //tophash拟插入位置
2. var insertk unsafe.Pointer //key拟插入位置
3. var elem unsafe.Pointer //value拟插入位置

复制代码

（8）开启循环，和读流程雷同，外层遍历桶，内层遍历桶的每个位置。

1. for {
2.                 for i := uintptr(0); i < bucketCnt; i++ {
3.                 //...
4.                 }
5.                 b = ovf
6.         }

复制代码

（9）若key的tophash和当前槽位的tophash不相同，则进行以下的查抄：

• 若该槽位是空的，那么就将kv拟插入在这个位置（先记录），因为大概存在相同的key在背面的桶中。
  
• 若槽位当前位置tophash标识为emptyRest（0），则标识从当前槽位开始往后的槽位都是空的，就不消继承遍历了，直接退出bucketloop。（说明可以插入在此位置了）
  

1. if b.tophash[i] != top {
2.                                 if isEmpty(b.tophash[i]) && inserti == nil {
3.                                         inserti = &b.tophash[i]
4.                                         insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
5.                                         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
6.                                 }
7.                                 if b.tophash[i] == emptyRest {
8.                                         break bucketloop
9.                                 }
10.                                 continue
11.                         }

复制代码

（10）否则说明找到了相同的key，需要进行覆盖操纵。更新完成后跳到done，实行收尾流程。留意：会调用key.Equal方法详细查抄要写的key和当前key是否一样，避免因为哈希辩论导致原来不同的kv对被错误的覆盖。

1. k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
2.                         if t.IndirectKey() {
3.                                 k = *((*unsafe.Pointer)(k))
4.                         }
5.                         if !t.Key.Equal(key, k) {
6.                                 continue
7.                         }
8.                         // already have a mapping for key. Update it.
9.                         if t.NeedKeyUpdate() {
10.                                 typedmemmove(t.Key, k, key)
11.                         }
12.                         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
13.                         goto done

复制代码

（11）倘若没有相同的key，也没有剩余的空间了，则会考虑实行扩容模式，完成后再回到agian的位置重新桶定位以及遍历流程。

1. // 如果达到负载因子上限，或者溢出桶过多，则扩容
2. if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
3.                 hashGrow(t, h)
4.                 goto again // Growing the table invalidates everything, so try again
5.         }

复制代码

触发扩容的条件：

• h.count+1 > loadFactor * 2^h.B：如果当前 map 达到负载因子上限，需要扩容。
  
• h.noverflow > threshold：如果 溢出桶过多，说明辩论严峻，也要扩容。
  
• h.growing()：查抄是否 已经在扩容，如果已经在扩容，就不会触发新的扩容。
  

（12）若不实行扩容操纵，也没有找到插入的位置，则新创建一个溢出桶，将kv拟插入在溢出桶的第一个位置。

1. if inserti == nil {
2.                 // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
3.                 newb := h.newoverflow(t, b)
4.                 inserti = &newb.tophash[0]
5.                 insertk = add(unsafe.Pointer(newb), dataOffset)
6.                 elem = add(insertk, bucketCnt*uintptr(t.KeySize))
7.         }

复制代码

创建新桶操纵如下：

1. func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
2.         var ovf *bmap
3.     //若表存在预分配溢出桶，则直接使用预分配的溢出桶。
4.         if h.extra != nil && h.extra.nextOverflow != nil {
5.                 if ovf.overflow(t) == nil {
6.             // 不是最后一个预分配的溢出桶，直接移动 `nextOverflow` 指针
7.                         h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.BucketSize)))
8.                 } else {
9.              // 这是最后一个预分配的溢出桶，重置 overflow 指针
10.                         ovf.setoverflow(t, nil)
11.                         h.extra.nextOverflow = nil
12.                 }
13.         } else {
14.         //创建一个新的溢出桶
15.                 ovf = (*bmap)(newobject(t.Bucket))
16.         }
17.     //更新 h.noverflow 计数，跟踪 map 目前有多少个溢出桶。
18.         h.incrnoverflow()
19.         if t.Bucket.PtrBytes == 0 { //如果map只存储基本数据类型
20.                 h.createOverflow() //创建overflow记录表
21.                 *h.extra.overflow = append(*h.extra.overflow, ovf) //记录新的溢出桶
22.         }
23.         b.setoverflow(t, ovf) //把ovf连接到b这个桶的overflow指针
24.         return ovf
25. }

复制代码

这里存在一个非常容易肴杂的点：请留意，在最开始的makeBucketArray方法中，我们提及到了只有末了一个溢出桶它才设置了overflow指针，对于前面的溢出桶，overflow指针是nil，所以可以根据这个特性来判断当前的溢出桶是不是末了一个溢出桶。

用图来表示，每个桶颠末了多次溢出桶扩展后的表状态，如下：

（13）在拟插入位置实际插入kv

1. // store new key/elem at insert position
2. if t.IndirectKey() {
3.   kmem := newobject(t.Key)
4.   *(*unsafe.Pointer)(insertk) = kmem
5.   insertk = kmem
6. }
7. if t.IndirectElem() {
8.   vmem := newobject(t.Elem)
9.   *(*unsafe.Pointer)(elem) = vmem
10. }
11. typedmemmove(t.Key, insertk, key)
12. *inserti = top
13. h.count++

复制代码

（14）收尾流程，再次校验是否处在并发写，有则抛出fatal，否则将标志重置，然退却出。

1. done:
2.         if h.flags&hashWriting == 0 {
3.                 fatal("concurrent map writes")
4.         }
5.         h.flags &^= hashWriting
6.         if t.IndirectElem() {
7.                 elem = *((*unsafe.Pointer)(elem))
8.         }
9.         return elem

复制代码

2.4、map的删流程


2.4.1、删流程步调总览


删流程步调大致如下：

• 1、若表为nil或者不存在元素，则直接返回；若处在并发写则fatal
  
• 2、获取key的哈希因子，根据哈希值找到对应的桶
  
• 3、若表处在扩容阶段，则使用growWork辅助扩容
  
• 4、开始遍历查找要删除的元素，若没找到则直接退出查找流程，找到了则将值清为0值
  
• 5、若表的结构如：「值1——空——空——空——删除值——后全空——后全空」的结构，则需要向前回溯，将值1后的全部slot都置为emptyRest状态。
  
• 6、若删除后，表的count为0，则更新hash因子，避免哈希碰撞攻击。
  
• 7、再次校验是否处在并发写，处在将fatal，否则重置写标识
  

2.4.2、源码跟进mapdelete

1. func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {        //...        if h == nil || h.count == 0 {
2.                 if err := mapKeyError(t, key); err != nil {
3.                         panic(err) // see issue 23734
4.                 }
5.                 return
6.         }
7.         if h.flags&hashWriting != 0 {
8.                 fatal("concurrent map writes")
9.         }         hash := t.Hasher(key, uintptr(h.hash0))
11.         // Set hashWriting after calling t.hasher, since t.hasher may panic,
12.         // in which case we have not actually done a write (delete).
13.         h.flags ^= hashWriting         bucket := hash & bucketMask(h.B)        if h.growing() {
14.                 growWork(t, h, bucket)
15.         }        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 {
16.                                 if b.tophash[i] == emptyRest {
17.                                         break search
18.                                 }
19.                                 continue
20.                         }                        k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
21.                         k2 := k
22.                         if t.IndirectKey() {
23.                                 k2 = *((*unsafe.Pointer)(k2))
24.                         }
25.                         if !t.Key.Equal(key, k2) {
26.                                 continue
27.                         }
28.                         // Only clear key if there are pointers in it.
29.                         if t.IndirectKey() {
30.                                 *(*unsafe.Pointer)(k) = nil
31.                         } else if t.Key.PtrBytes != 0 {
32.                                 memclrHasPointers(k, t.Key.Size_)
33.                         }
34.                         e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
35.                         if t.IndirectElem() {
36.                                 *(*unsafe.Pointer)(e) = nil
37.                         } else if t.Elem.PtrBytes != 0 {
38.                                 memclrHasPointers(e, t.Elem.Size_)
39.                         } else {
40.                                 memclrNoHeapPointers(e, t.Elem.Size_)
41.                         }
42.                         b.tophash[i] = emptyOne                        // If the bucket now ends in a bunch of emptyOne states,                        // change those to emptyRest states.                        // It would be nice to make this a separate function, but                        // for loops are not currently inlineable.                        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 {
43.                                 b.tophash[i] = emptyRest
44.                                 if i == 0 {
45.                                         if b == bOrig {
46.                                                 break // beginning of initial bucket, we're done.
47.                                         }
48.                                         // Find previous bucket, continue at its last entry.
49.                                         c := b
50.                                         for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
51.                                         }
52.                                         i = bucketCnt - 1
53.                                 } else {
54.                                         i--
55.                                 }
56.                                 if b.tophash[i] != emptyOne {
57.                                         break
58.                                 }
59.                         }                notLast:
60.                         h.count--
61.                         // Reset the hash seed to make it more difficult for attackers to
62.                         // repeatedly trigger hash collisions. See issue 25237.
63.                         if h.count == 0 {
64.                                 h.hash0 = uint32(rand())
65.                         }
66.                         break search
67.                 }        }         if h.flags&hashWriting == 0 {
68.                 fatal("concurrent map writes")
69.         }
70.         h.flags &^= hashWriting}

复制代码

（1）错误处理惩罚：当表为nil或者不存在元素，则直接返回；若处在并发写状态则fatal

1. if h == nil || h.count == 0 {
2.                 if err := mapKeyError(t, key); err != nil {
3.                         panic(err) // see issue 23734
4.                 }
5.                 return
6.         }
7.         if h.flags&hashWriting != 0 {
8.                 fatal("concurrent map writes")
9.         }

复制代码

（2）获取key的hash，而且标识表为写状态

1. hash := t.Hasher(key, uintptr(h.hash0))
3.         // Set hashWriting after calling t.hasher, since t.hasher may panic,
4.         // in which case we have not actually done a write (delete).
5.         h.flags ^= hashWriting

复制代码

（3）若表正在扩容，则调用growWork辅助扩容。通过hash值映射到对应的桶b。

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

复制代码

（4）进入桶的遍历，外层遍历桶，内层遍历每个kv对

1. for ; b != nil; b = b.overflow(t) {
2.                 for i := uintptr(0); i < bucketCnt; i++ {
3.                         //...
4.                 }
5.         }

复制代码

（5）若当前槽位的tophash和需要查找的不相同，则查抄背面是否另有元素；有元素就继承进行查找，没有就直接退出，表示想删除的元素不存在。

1. if b.tophash[i] != top {
2.                                 if b.tophash[i] == emptyRest {
3.                                         break search
4.                                 }
5.                                 continue
6.                         }

复制代码

（6）否则，说明找到了对应的key，进行删除操纵，详细包括了：

• 查找key并找到存储位置
  
• 扫除 key 和 value（包括直接清零或 nil 指针）。
  
• 更新 tophash，标志该槽位为空（EmptyOne）。
  

留意：会调用key.Equal方法详细查抄要删除的key和当前key是否一样，避免因为哈希辩论导致原来不同的kv对被错误的删除。

1. k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
2.                         k2 := k
3.                         if t.IndirectKey() {
4.                                 k2 = *((*unsafe.Pointer)(k2))
5.                         }
6.                         if !t.Key.Equal(key, k2) {
7.                                 continue
8.                         }
9.                         // Only clear key if there are pointers in it.
10.                         if t.IndirectKey() {
11.                                 *(*unsafe.Pointer)(k) = nil
12.                         } else if t.Key.PtrBytes != 0 {
13.                                 memclrHasPointers(k, t.Key.Size_)
14.                         }
15.                         e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
16.                         if t.IndirectElem() {
17.                                 *(*unsafe.Pointer)(e) = nil
18.                         } else if t.Elem.PtrBytes != 0 {
19.                                 memclrHasPointers(e, t.Elem.Size_)
20.                         } else {
21.                                 memclrNoHeapPointers(e, t.Elem.Size_)
22.                         }
23.                         b.tophash[i] = emptyOne

复制代码

（7）查抄当前删除的桶的元素是否是桶的末了一个元素：

• 如果，若该桶的背面还存在溢出桶，而且溢出桶非空则跳过清理环节，进入收尾阶段
  
• 若不是，查抄背面是否另有元素，有元素也跳过清理环节。（通过查抄下一个slot的标识是否为emptyRest）
  

1. if i == bucketCnt-1 {
2.     if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
3.         goto notLast
4.     }
5. } else {
6.     if b.tophash[i+1] != emptyRest {
7.         goto notLast
8.     }
9. }

复制代码

否则，说明背面没有更多的元素了，需要向前回溯，将末了一个元素的槽位背面的全部槽位都设置为emptyRest状态，优化未来的流程。

回溯流程：

• 先将当前桶从当前的删除元素一个个往前走，遇到是emptyOne的就修改为emptyRest
  
• 当到达第一个元素而且也为空时，回溯到上一个桶的末尾，重复流程
  
• 遇到非空元素，完成全部回溯而且退出。
  

1. for {
2.                                 b.tophash[i] = emptyRest
3.                                 if i == 0 {
4.                                         if b == bOrig {
5.                                                 break // beginning of initial bucket, we're done.
6.                                         }
7.                                         // Find previous bucket, continue at its last entry.
8.                                         c := b
9.                                         for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
10.                                         }
11.                                         i = bucketCnt - 1
12.                                 } else {
13.                                         i--
14.                                 }
15.                                 if b.tophash[i] != emptyOne {
16.                                         break
17.                                 }
18.                         }

复制代码

（8）收尾流程，将map的元素计数器count-1，若count为0，则更新哈希因子。

1. notLast:
2.                         h.count--
3.                         // Reset the hash seed to make it more difficult for attackers to
4.                         // repeatedly trigger hash collisions. See issue 25237.
5.                         if h.count == 0 {
6.                                 h.hash0 = uint32(rand())
7.                         }
8.                         break search
9.                 }

复制代码

   为什么要更新哈希因子？
  让攻击者无法使用相同的哈希因子 h.hash0 构造出一组导致严峻哈希碰撞的 key，从而保护 map 免受拒绝服务（DoS）攻击。
  
（9）末了的校验是否处在并发写状态，是则fatal，然后再更新状态标识

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

复制代码

3、扩容机制


3.1、扩容类型


Gomap的扩容方式分为两种：

• 等量扩容（Same-Size-Grow）：如果map的溢出桶过多，导致查找性能下降，说明KV分布不匀称，此时就会触发等量扩容，哈希表的桶数不会改变，但会重新分配K-V对的位置，目标是减少溢出桶的数量，增加KV的密度，让数据能平均分布。
  
• 增量扩容（Double-Size-Grow）：如果负载因子超标「count/2^B > loadFactor」，即KV对的数量凌驾了一定上限，就会触发增量扩容，使得Buckets数量翻倍，让全部的KV对重新分配在新的桶数组中，目标是减少K-V对的密度，降低每个桶的KV数量，优化查询时间。
  

   为什么说等量扩容是增加密度呢？
  我们想，既然count是合理的，但是当前map导致了溢出桶过多，那么只大概是颠末了多次删除操纵，导致出现了许多空位，例如「A——空——空——空——B」，如许子每次查找就很耗时了，于是等量扩容需要重新分配KV对的位置变为「A——B」，让数据更加紧凑。
  
3.2、扩容触发


在之前的写流程中，提及到以下代码会触发map的扩容：

1. if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
2.                 hashGrow(t, h)
3.                 goto again // Growing the table invalidates everything, so try again
4. }

复制代码

只有当map不处在扩容中，而且满意以下两个条件之一，触发扩容：

• 负载因子超标：当KV对的数量凌驾桶的数量，而且「KV对数量/桶数 > 负载因子」时，发生扩容
  

1. overLoadFactor(h.count+1, h.B)func overLoadFactor(count int, B uint8) bool {
2.         return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
3. }

复制代码

• 溢出桶过多：当溢出桶数量>桶数组的数量（B最大取15），则发生扩容
  

1. func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
2.         if B > 15 {
3.                 B = 15
4.         }
5.         return noverflow >= uint16(1)<<(B&15)
6. }

复制代码

3.3、扩容流程前置


进入hashGrow方法，观察扩容流程

1. func hashGrow(t *maptype, h *hmap) {
2.     bigger := uint8(1)
3.     if !overLoadFactor(h.count+1, h.B) {
4.         bigger = 0
5.         h.flags |= sameSizeGrow
6.     }
7.     oldbuckets := h.buckets
8.     newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
13.     flags := h.flags &^ (iterator | oldIterator)
14.     if h.flags&iterator != 0 {
15.         flags |= oldIterator
16.     }
17.     // commit the grow (atomic wrt gc)
18.     h.B += bigger
19.     h.flags = flags
20.     h.oldbuckets = oldbuckets
21.     h.buckets = newbuckets
22.     h.nevacuate = 0
23.     h.noverflow = 0
26.     if h.extra != nil && h.extra.overflow != nil {
27.         // Promote current overflow buckets to the old generation.
28.         if h.extra.oldoverflow != nil {
29.             throw("oldoverflow is not nil")
30.         }
31.         h.extra.oldoverflow = h.extra.overflow
32.         h.extra.overflow = nil
33.     }
34.     if nextOverflow != nil {
35.         if h.extra == nil {
36.             h.extra = new(mapextra)
37.         }
38.         h.extra.nextOverflow = nextOverflow
39.     }

复制代码

（1）标识是否为等量扩容，如果等量扩容bigger置0，否则将map的flag的二进制第4位置1标识处在等量扩容阶段。

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

复制代码

（2）岂论如何，发生扩容，那么当前的桶数组就会变成旧的桶数组了，于是将map的oldbuckets指针指向它，然后创建一个新的桶数组。

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

复制代码

（3）更新一些map的标识，包括：

• 处于range的iterator标识，若处在遍历中，则需要标识olditerator
  
• 新map的桶数、完成数据迁移的桶数、溢出桶的桶数等
  

1. flags := h.flags &^ (iterator | oldIterator)
2.         if h.flags&iterator != 0 {
3.                 flags |= oldIterator
4.         }
5.         // commit the grow (atomic wrt gc)
6.         h.B += bigger
7.         h.flags = flags
8.         h.oldbuckets = oldbuckets
9.         h.buckets = newbuckets
10.         h.nevacuate = 0
11.         h.noverflow = 0

复制代码

（4）将原本的可用预分配溢出桶赋值给h.extra.oldoverflow，将新分配的桶数组的新预分配溢出桶赋值给h.extra.nextOverflow

1. if h.extra != nil && h.extra.overflow != nil {
2.                 // Promote current overflow buckets to the old generation.
3.                 if h.extra.oldoverflow != nil {
4.                         throw("oldoverflow is not nil")
5.                 }
6.                 h.extra.oldoverflow = h.extra.overflow
7.                 h.extra.overflow = nil
8.         }
9.         if nextOverflow != nil {
10.                 if h.extra == nil {
11.                         h.extra = new(mapextra)
12.                 }
13.                 h.extra.nextOverflow = nextOverflow
14.         }

复制代码

末了根据注释，我们知道Go的map扩容实际流程会通过growWork和evacuate方法渐进式地完成。

1. // the actual copying of the hash table data is done incrementally
2. // by growWork() and evacuate().

复制代码

3.4、渐进式扩容、源码实现


Go对map的扩容策略接纳的是渐进式扩容（Incrementally Grow），避免一次将全部旧数据迁移至新map引发性能抖动。

迁移规则如下：

• 如果等量扩容，那么新桶数组的长度与旧桶数组长度一致，让数据更加紧凑，从而减少溢出链长度
  
• 如果等量扩容，旧桶的数据迁移到的新桶中，它们桶的下标在桶数组中是一致的。例如旧桶0—迁移至—>新桶0
  
• 如果增量扩容，会根据旧数据KV对的hash值，来判断是否要进行桶的偏移。
  
• 因为一个KV对，要通过hash值来映射到对应的桶中，当桶的数量翻倍之后，对应的对数指标B也会加一，因此取模映射会发生改变。例如，一个KV对的hash值原本是111，原本桶的数量为4，那么B=2，取模运算为：「111 & (1<<2 - 1) = 111 & 11 = 11 = 3」，所以这个KV对会被存放在桶3中。当发生了增量扩容后，B增一为3，此时对于同一个hash值，它的取模变成了：「111 & (1<<3 - 1) = 111 & 111 = 111 = 7」，偏移了4个桶。对于增量扩容的转移，就是通过这个方式来判断旧的KV对应该被放在新的哪一个桶中，假如它原本在第i个桶，原本含有j个桶，那么迁移后它只大概在第i个桶或者第i+j个桶中。
  

---

当每次触发写、删操纵的时候，会为处于map的两组桶的数据完成迁移：

• 一组是当前写、删操纵所命中的桶
  
• 一组是未迁移的桶中，索引最小的谁人桶
  

1. func growWork(t *maptype, h *hmap, bucket uintptr) {
2.         //迁移当前正在使用的桶
3.         evacuate(t, h, bucket&h.oldbucketmask())
5.         //迁移未迁移的桶中，索引最小的桶
6.         if h.growing() {
7.                 evacuate(t, h, h.nevacuate)
8.         }
9. }

复制代码

步入evacuate函数：

1. func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
2.     //oldbcuket为要迁移的旧桶在旧桶数组中的索引
3.     //获取这一个旧桶b
4.         b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
5.     //获取旧桶数组的桶数，根据2^oldB计算
6.         newbit := h.noldbuckets()
7.     //判断此桶b是否已经完成了数据的迁移，未完成则步入函数内部
8.         if !evacuated(b) {
9.                 //xy[2]数组用于存储迁移目标bucket
10.         //xy[0]，记录的是等量扩容迁移的目标桶，代表新桶数组中索引和旧桶一致的那个桶
11.         //xy[1]，记录的是增量扩容迁移的目标桶，索引为原索引加上旧桶容量的桶
12.                 var xy [2]evacDst
13.                 x := &xy[0]
14.                 x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize)))
15.                 x.k = add(unsafe.Pointer(x.b), dataOffset)
16.                 x.e = add(x.k, bucketCnt*uintptr(t.KeySize))
18.                 if !h.sameSizeGrow() {
19.                         //若是增量扩容，则记录xy[1]
20.                         y := &xy[1]
21.             //例如旧桶数组有4个桶，那么旧桶i映射到新桶i+4
22.                         y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.BucketSize)))
23.                         y.k = add(unsafe.Pointer(y.b), dataOffset)
24.                         y.e = add(y.k, bucketCnt*uintptr(t.KeySize))
25.                 }
26.                 //开始遍历旧桶b的所有键值对
27.                 for ; b != nil; b = b.overflow(t) {
28.                         k := add(unsafe.Pointer(b), dataOffset)
29.                         e := add(k, bucketCnt*uintptr(t.KeySize))
30.             //遍历每一个键值对
31.                         for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) {
32.                 //获取当前slot的tophash
33.                                 top := b.tophash[i]
34.                                 if isEmpty(top) {
35.                     //若槽位为空，标识以完成迁移
36.                                         b.tophash[i] = evacuatedEmpty
37.                                         continue
38.                                 }
39.                                 if top < minTopHash {
40.                                         throw("bad map state")
41.                                 }
42.                                 k2 := k
43.                 //处理键为指针的情况
44.                                 if t.IndirectKey() {
45.                                         k2 = *((*unsafe.Pointer)(k2))
46.                                 }
47.                                 var useY uint8
48.                                 if !h.sameSizeGrow() {
49.                     //对于增量扩容的迁移策略
50.                     //计算key的hash值
51.                                         hash := t.Hasher(k2, uintptr(h.hash0))
52.                     //若map处于迭代过程需要特殊处理
53.                                         if h.flags&iterator != 0 && !t.ReflexiveKey() && !t.Key.Equal(k2, k2) {
54.                         //useY决定是否要迁移到新桶中
55.                                                 useY = top & 1
56.                                                 top = tophash(hash)
57.                                         } else {
58.                         //普通key的迁移判断
59.                                                 if hash&newbit != 0 {
60.                             //说明hash的B位是1，key要被迁移到新桶中下标为Y的桶。
61.                             //这里举个例子，假如旧桶有4个，那么B是2，那么newbit就是1<<B=100，若hash的第B位也是1，那就决定要用y的坐标，所以会迁移到桶8
62.                                                         useY = 1
63.                                                 }
64.                                         }
65.                                 }
66.                                 b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
67.                                 dst := &xy[useY]                 // evacuation destination
68.                                 //若到了桶的最后一个slot，完成后跳转到溢出桶
69.                                 if dst.i == bucketCnt {
70.                                         dst.b = h.newoverflow(t, dst.b)
71.                                         dst.i = 0
72.                                         dst.k = add(unsafe.Pointer(dst.b), dataOffset)
73.                                         dst.e = add(dst.k, bucketCnt*uintptr(t.KeySize))
74.                                 }
75.                 //完成K-V对的迁移，更新几个目标指针
76.                                 dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
77.                                 if t.IndirectKey() {
78.                                         *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
79.                                 } else {
80.                                         typedmemmove(t.Key, dst.k, k) // copy elem
81.                                 }
82.                                 if t.IndirectElem() {
83.                                         *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
84.                                 } else {
85.                                         typedmemmove(t.Elem, dst.e, e)
86.                                 }
87.                                 dst.i++
88.                                 dst.k = add(dst.k, uintptr(t.KeySize))
89.                                 dst.e = add(dst.e, uintptr(t.ValueSize))
90.                         }
91.                 }
92.                 //若旧桶完成了迁移，并且没有处于迭代中并且含有指针类型的值，需要手动帮助GC清理掉旧桶。
93.                 if h.flags&oldIterator == 0 && t.Bucket.PtrBytes != 0 {
94.                         b := add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))
95.                         // Preserve b.tophash because the evacuation
96.                         // state is maintained there.
97.                         ptr := add(b, dataOffset)
98.                         n := uintptr(t.BucketSize) - dataOffset
99.                         memclrHasPointers(ptr, n)
100.                 }
101.         }
102.         //若当前迁移的旧桶是未迁移的旧桶中索引最小的，那么将h.nevacuate累加1.若旧桶全部被迁移完毕，会将等量扩容标识置为0
103.         if oldbucket == h.nevacuate {
104.                 advanceEvacuationMark(h, t, newbit)
105.         }
106. }
107. func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
108.         h.nevacuate++
109.         //...
110.         if h.nevacuate == newbit {
111.         //完成所有迁移，工作结束
112.                 h.oldbuckets = nil
113.                 if h.extra != nil {
114.                         h.extra.oldoverflow = nil
115.                 }
116.                 h.flags &^= sameSizeGrow
117.         }
118. }

复制代码

可以阅读上述代码注释来学习它的迁移过程。

4、map的遍历流程


4.1、紧张数据结构


我们知道，可以通过for range的方式来遍历map的每一个kv对，它紧张是通过底层的hiter——Hash Iterator数据结构实现的。

在runtime/map.go中，可以找到对迭代器结构的界说：

1. type hiter struct {
2.     key         unsafe.Pointer // 当前遍历的 key 指针
3.     elem        unsafe.Pointer // 当前遍历的 value 指针
4.     t           *maptype       // 关联的 map 类型信息
5.     h           *hmap          // 指向被遍历的 map 结构
6.     buckets     unsafe.Pointer // 迭代开始时的 buckets 数组指针（用于保证遍历稳定）
7.     bptr        *bmap          // 当前遍历的 bucket 指针
8.     overflow    *[]*bmap       // 存储当前 hmap.buckets 可能存在的溢出桶，防止 GC 误清理
9.     oldoverflow *[]*bmap       // 存储旧 hmap.oldbuckets 可能存在的溢出桶，防止 GC 误清理
10.     startBucket uintptr        // 迭代开始的 bucket 位置（用于随机化遍历起点）
11.     offset      uint8          // 在 bucket 内的随机偏移量（防止总是从 slot 0 开始，增强安全性）
12.     wrapped     bool           // 是否已经遍历完所有 bucket 并回绕到起始位置
13.     B           uint8          // 当前 map 的 B 值（`2^B` 代表 bucket 数量）
14.     i           uint8          // 当前 bucket 内的 key-value 索引（用于迭代 bucket 内部的槽位）
15.     bucket      uintptr        // 当前遍历到的 bucket 索引（相对 `buckets` 起始位置）
16.     checkBucket uintptr        // 用于 double-checking bucket 迭代的一致性，避免 map 变化影响遍历
17. }

复制代码

字段详细说明：

4.2、遍历主流程


Go对map的遍历出发点是随机的，它防止每次遍历都从slot 0开始，增强了一定的安全性，这也是为什么你使用for range去遍历map的时候，不能保证每次一次遍历都结果都是相同的。

4.3、mapiterinit初始化迭代器


让我们进入mapiterinit流程，观察它的详细实现。

1. func mapiterinit(t *maptype, h *hmap, it *hiter) {
2.     //...
3.         it.t = t
4.         if h == nil || h.count == 0 {
5.                 return
6.         }
8.         if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {
9.                 throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go
10.         }
11.         it.h = h
13.         // grab snapshot of bucket state
14.         it.B = h.B
15.         it.buckets = h.buckets
16.         if t.Bucket.PtrBytes == 0 {
17.                 h.createOverflow()
18.                 it.overflow = h.extra.overflow
19.                 it.oldoverflow = h.extra.oldoverflow
20.         }
22.         // decide where to start
23.         r := uintptr(rand())
24.         it.startBucket = r & bucketMask(h.B)
25.         it.offset = uint8(r >> h.B & (bucketCnt - 1))
27.         // iterator state
28.         it.bucket = it.startBucket
30.         // Remember we have an iterator.
31.         // Can run concurrently with another mapiterinit().
32.         if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
33.                 atomic.Or8(&h.flags, iterator|oldIterator)
34.         }
36.         mapiternext(it)
37. }

复制代码

（1）若表为nil或者没有元素，则直接返回；记录一些初始参数

1. it.t = t
2.         if h == nil || h.count == 0 {
3.                 return
4.         }
6.         if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {
7.                 throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go
8.         }
9.         it.h = h
11.         // grab snapshot of bucket state
12.         it.B = h.B
13.         it.buckets = h.buckets

复制代码

（2）若表的桶不含有指针类型，那么它们大概会在遍历的过程中，若表发生了结构的变化，大概会取消对旧桶的引用，此时溢出桶就大概会被GC清理掉，所以当迭代器开始工作的时候，就需要将当前的溢出桶和旧的溢出桶保存在迭代器的结构中，保持对它们的引用。

1. if t.Bucket.PtrBytes == 0 {
2.                 // Allocate the current slice and remember pointers to both current and old.
3.                 // This preserves all relevant overflow buckets alive even if
4.                 // the table grows and/or overflow buckets are added to the table
5.                 // while we are iterating.
6.                 h.createOverflow()
7.                 it.overflow = h.extra.overflow
8.                 it.oldoverflow = h.extra.oldoverflow
9.         }

复制代码

（3）通过取随机数的方式，决定遍历的起始桶，以及桶的遍历的起始kv对的位置

1. // decide where to start
2.         r := uintptr(rand())
3.         it.startBucket = r & bucketMask(h.B)
4.         it.offset = uint8(r >> h.B & (bucketCnt - 1))
6.         // iterator state
7.         it.bucket = it.startBucket

复制代码

（4）进入遍历流程

1. mapiternext(it)

复制代码

4.4、mapiternext

1. func mapiternext(it *hiter) {
2.         h := it.h
3.         //...
4.         if h.flags&hashWriting != 0 {
5.                 fatal("concurrent map iteration and map write")
6.         }
7.         t := it.t
8.         bucket := it.bucket
9.         b := it.bptr
10.         i := it.i
11.         checkBucket := it.checkBucket
13. next:
14.         if b == nil {
15.                 if bucket == it.startBucket && it.wrapped {
16.                         // end of iteration
17.                         it.key = nil
18.                         it.elem = nil
19.                         return
20.                 }
21.                 if h.growing() && it.B == h.B {
22.                         // Iterator was started in the middle of a grow, and the grow isn't done yet.
23.                         // If the bucket we're looking at hasn't been filled in yet (i.e. the old
24.                         // bucket hasn't been evacuated) then we need to iterate through the old
25.                         // bucket and only return the ones that will be migrated to this bucket.
26.                         oldbucket := bucket & it.h.oldbucketmask()
27.                         b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
28.                         if !evacuated(b) {
29.                                 checkBucket = bucket
30.                         } else {
31.                                 b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
32.                                 checkBucket = noCheck
33.                         }
34.                 } else {
35.                         b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
36.                         checkBucket = noCheck
37.                 }
38.                 bucket++
39.                 if bucket == bucketShift(it.B) {
40.                         bucket = 0
41.                         it.wrapped = true
42.                 }
43.                 i = 0
44.         }
45.         for ; i < bucketCnt; i++ {
46.                 offi := (i + it.offset) & (bucketCnt - 1)
47.                 if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
48.                         // TODO: emptyRest is hard to use here, as we start iterating
49.                         // in the middle of a bucket. It's feasible, just tricky.
50.                         continue
51.                 }
52.                 k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.KeySize))
53.                 if t.IndirectKey() {
54.                         k = *((*unsafe.Pointer)(k))
55.                 }
56.                 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize))
57.                 if checkBucket != noCheck && !h.sameSizeGrow() {
58.                         // Special case: iterator was started during a grow to a larger size
59.                         // and the grow is not done yet. We're working on a bucket whose
60.                         // oldbucket has not been evacuated yet. Or at least, it wasn't
61.                         // evacuated when we started the bucket. So we're iterating
62.                         // through the oldbucket, skipping any keys that will go
63.                         // to the other new bucket (each oldbucket expands to two
64.                         // buckets during a grow).
65.                         if t.ReflexiveKey() || t.Key.Equal(k, k) {
66.                                 // If the item in the oldbucket is not destined for
67.                                 // the current new bucket in the iteration, skip it.
68.                                 hash := t.Hasher(k, uintptr(h.hash0))
69.                                 if hash&bucketMask(it.B) != checkBucket {
70.                                         continue
71.                                 }
72.                         } else {
73.                                 // Hash isn't repeatable if k != k (NaNs).  We need a
74.                                 // repeatable and randomish choice of which direction
75.                                 // to send NaNs during evacuation. We'll use the low
76.                                 // bit of tophash to decide which way NaNs go.
77.                                 // NOTE: this case is why we need two evacuate tophash
78.                                 // values, evacuatedX and evacuatedY, that differ in
79.                                 // their low bit.
80.                                 if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
81.                                         continue
82.                                 }
83.                         }
84.                 }
85.                 if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
86.                         !(t.ReflexiveKey() || t.Key.Equal(k, k)) {
87.                         // This is the golden data, we can return it.
88.                         // OR
89.                         // key!=key, so the entry can't be deleted or updated, so we can just return it.
90.                         // That's lucky for us because when key!=key we can't look it up successfully.
91.                         it.key = k
92.                         if t.IndirectElem() {
93.                                 e = *((*unsafe.Pointer)(e))
94.                         }
95.                         it.elem = e
96.                 } else {
97.                         // The hash table has grown since the iterator was started.
98.                         // The golden data for this key is now somewhere else.
99.                         // Check the current hash table for the data.
100.                         // This code handles the case where the key
101.                         // has been deleted, updated, or deleted and reinserted.
102.                         // NOTE: we need to regrab the key as it has potentially been
103.                         // updated to an equal() but not identical key (e.g. +0.0 vs -0.0).
104.                         rk, re := mapaccessK(t, h, k)
105.                         if rk == nil {
106.                                 continue // key has been deleted
107.                         }
108.                         it.key = rk
109.                         it.elem = re
110.                 }
111.                 it.bucket = bucket
112.                 if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
113.                         it.bptr = b
114.                 }
115.                 it.i = i + 1
116.                 it.checkBucket = checkBucket
117.                 return
118.         }
119.         b = b.overflow(t)
120.         i = 0
121.         goto next
122. }

复制代码

（1）若处在并发写状态则fatal；初始化各项参数

1. if h.flags&hashWriting != 0 {
2.                 fatal("concurrent map iteration and map write")
3.         }
4.         t := it.t
5.         bucket := it.bucket
6.         b := it.bptr
7.         i := it.i
8.         checkBucket := it.checkBucket

复制代码

（2）外层主循环，遍历每一个bucket，当达到buckets的末尾的时候，标识wrapped为true，回到头部。

1. next:
2. if b == nil {
3.         //...
4.                         b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
5.     //...
6.         }
7.         bucket++
8.                 if bucket == bucketShift(it.B) {
9.                         bucket = 0
10.                         it.wrapped = true
11.                 }
12.         b = b.overflow(t)
13.         i = 0
14.         goto next

复制代码

（3）若遍历完全部的桶了，则退出函数

1. if bucket == it.startBucket && it.wrapped {
2.                         // end of iteration
3.                         it.key = nil
4.                         it.elem = nil
5.                         return
6.                 }

复制代码

（4）map大概正在处于扩容阶段，若处在扩容阶段，而且当前range的B和map的B任然相同（仍然是同一级数），那么说明便利的顺序没有发生改变。若桶处于旧桶数组，且数据没有迁移完成，那么需要将checkBucket置为当前桶号，需要对其便利防止漏掉数据。

1. if h.growing() && it.B == h.B {
2.                         oldbucket := bucket & it.h.oldbucketmask()
3.     //获取oldbucket在oldbuckets中的位置
4.                         b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
5.     //若数据还没有完成迁移，那么还需要遍历这个桶的K-V对
6.                         if !evacuated(b) {
7.                                 checkBucket = bucket
8.                         } else {
9.                 //否则，直接读取newbuckets
10.                                 b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
11.                 //表示bucket都迁移完了，不需要额外检查oldbuckets
12.                                 checkBucket = noCheck
13.                         }
14. } else {
15.             //没有扩容，直接从buckets读取
16.                         b = (*bmap)(add(it.buckets, bucket*uintptr(t.BucketSize)))
17.                         checkBucket = noCheck
18.                 }

复制代码

（5）开始遍历该bucket下的全部KV对，对于一个空的槽位，因为大概处在迁移过程，所以会存在evacuatedEmpty的标识，所以不能判断是不是背面都是空的，必须全部遍历一次。

1. for ; i < bucketCnt; i++ {
2.                 offi := (i + it.offset) & (bucketCnt - 1)
3.                 if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
4.                         // TODO: emptyRest is hard to use here, as we start iterating
5.                         // in the middle of a bucket. It's feasible, just tricky.
6.                         continue
7.                 }

复制代码

（6）获取槽位的KV

1. k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.KeySize))
2.                 if t.IndirectKey() {
3.                         k = *((*unsafe.Pointer)(k))
4.                 }
5.                 e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.KeySize)+uintptr(offi)*uintptr(t.ValueSize))

复制代码

（7）对于map正在实施等量扩容的环境下，如果当前的key颠末重新到hash映射，会被映射到另一个桶中，那这时候我们也应该严酷按照新桶的顺序来遍历，所以跳过这个key。例如，我们现在正在遍历桶3的一个KV对，但是这个KV对将会被迁移至桶7，那我们也该在遍历桶7的时候再获取它，而不是现在获取。

1. if checkBucket != noCheck && !h.sameSizeGrow() {
2.                         if t.ReflexiveKey() || t.Key.Equal(k, k) {
3.                                 hash := t.Hasher(k, uintptr(h.hash0))
4.                                 if hash&bucketMask(it.B) != checkBucket {
5.                                         continue
6.                                 }
7.                         } else {
8.                                 if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
9.                                         continue
10.                                 }
11.                         }
12.                 }

复制代码

（8）通过读流程的mapaccessK方法来读取这个K-V对，通过迭代器hiter的key、value指针进行接收，用于对用户的遍历操纵进行响应。

1. rk, re := mapaccessK(t, h, k)
2.                         if rk == nil {
3.                                 continue // key has been deleted
4.                         }
5.                         it.key = rk
6.                         it.elem = re

复制代码

   文章转载自：MelonTe
  原文链接：万字剖析Golang的map实现原理 - MelonTe - 博客园
  体验地址：引迈 - JNPF快速开发平台_低代码开发平台_零代码开发平台_流程计划器_表单引擎_工作流引擎_软件架构

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。