map其实就是一个hash table，今天我们来看一下go中map的实现，相关代码位于runtime/map.go中。

结构定义

我们首先来看一下map的相关结构定义

1
2
3
4
5
6
7
8
9
10
11
12
13
type hmap struct {
	count     int // 当前map中存放的元素，我们可以通过内置函数`len`来获取
	flags     uint8
	B         uint8  // 当前map的backet数量为2^B，其中最大能够存放loadFactor * 2^B个元素，当超过这个阈值时就会进行扩容，loadFactor默认为13/2，这个值是全局定义的常量
	noverflow uint16 // 总的overflow的数量
	hash0     uint32 // hash seed

	buckets    unsafe.Pointer // bucket数组，长度为2^B，这里bucket实际是bmap
	oldbuckets unsafe.Pointer // 如果发生扩容，旧的buckets就会保存到oldbuckets，在后续的操作中会慢慢迁移到新的buckets中
	nevacuate  uintptr        // 扩容时需要从原来的buckets将数据迁移到新的buckets中，该字段表示小于该数值的buckets当前都已经迁移完成

	extra *mapextra // 如果map中保存的key和value都没有包含指针，那么gc时就不需要对buckets里面的内容进行扫描，但是每个bucket本质上是一个链表，buckets头部保存的是每个bucket链表的头节点，这时候会将每个链表的后续节点保存到该字段内，从而gc时可以对这些后续节点进行扫描，防止被回收
}

map的key和value，如果都没有包含指针，那么会对其进行优化，gc的时候就不需要去扫描每个键值对了

上面extra字段对应的mapextra类型：

1
2
3
4
5
6
7
type mapextra struct {
	overflow    *[]*bmap // 对应buckets
	oldoverflow *[]*bmap // 对应oldbuckets

	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap // 分配bmap时，可能会预先分配一些，当需要时可以直接从这里获取
}

上面说的，每个bucket实际上是一个bmap链表，而hmap中的buckets是一个bmap链表数组，这实际上就是开散列。和普通的开散列不同的是，一个bmap中保存了8个键值对，下面来看一下bmap的定义：

1
2
3
4
5
6
7
8
9
10
11
// A bucket for a Go map.
// bucket实际上是一个bmap
type bmap struct {
	// 这里bucketCnt是一个全局声明的常量，大小为8，也就是限制每个bmap中保存8个键值对
    // 当判断一个key是否在当前bmap中时，会先获取这个key的hash的高8位，然后在tophash中查找是否有匹配的索引，如果有再进一步比较key是否相同，如果当前bmap中没有找到，则到下一个bmap中查找
	tophash [bucketCnt]uint8
	// tophash后面紧跟着保存在当前bmap中的8个key和8个value
    // 因为不同类型的key和value内存大小是不同的，这里需要在运行时根据指针运算来访问
    // 在bmap中是按照 `k1,k2,..,k8,v1,v2,...,v8` 这样来排列的，而不是按照直观上的`k1,v1,k2,v2,...,k8,v8`这样来排列，主要是为了减少内存对齐时额外的内存开销
    // 8个键值对之后还有一个overflow指针，用来链接下一个bmap，正如上面说的，每个bucket实际上是一个bmap链表，这里通过overflow链接的这些bmap被称为`overflow bucket`
}

因为bmap链接下一个bmap的overflow指针在末尾，而不同类型的key和value的内存大小又不同，因此无法直接获取到下一个bmap的地址，前面说过，当key和value不包含指针的时候，gc时不需要扫描这些键值对；但是又需要扫描这些bmap，因此这种情况下会把这些bmap存到mapextra字段中的`overflow和oldoverflow中，这样gc时直接遍历这两个切片就好了。
那为什么不把overflow放到bmap头部呢？个人觉得可能是为了让内存访问更友好吧，连续的内存访问肯定更加高效。

如上面bmap所见，键值对并没有显示声明出来，而是需要在运行时根据指针运算来访问，这里来看一下一个全局声明的常量dataOffset，这个常量在后续会经常看到：

1
2
3
4
5
6
7
8
const(
    ...
	dataOffset = unsafe.Offsetof(struct {
		b bmap
		v int64
	}{}.v)
    ...
)

因为bmap实际上只声明了一个uint8类型的数组，因此这里v字段的偏移量就是实际bmap中第一个key值的偏移量

这里假设bmap的地址是bptr，key的类型大小是ksize，val的类型大小是vsize，那么访问第i个key和val的地址可以通过下面公式计算（i从0开始计算）：

1
2
ith key: bptr + dataOffset + i * ksize
ith val: bptr + dataOffset + bucketCnt * ksize + i * vsize

至此，我们对map的结构有了一个大体的了解，其键值对的存储结构大致可以用下图来描述：

1
2
3
4
5
6
7
8
9
10
11
    bucket数组         bmap中的overflow指向下一个bmap 
  实际上是bmap数组    这些由overflow引用的bucket被称作overflow bucket
|-----------------|  |-----------------|
|k1,..,k8,v1,..,v8|->|k1,..,k8,v1,..,v8|-> ...		  
|-----------------|  |-----------------|
|k1,..,k8,v1,..,v8|-> ...
|-----------------|
|k1,..,k8,v1,..,v8|-> ...
|-----------------|
|k1,..,k8,v1,..,v8|-> ...
|-----------------|

从上面可以看到，一个bucket实际上是一个bmap，而且bmap可以通过overflow指针来形成链表，这些通过overflow引用的bmap被称作overflow bucket，而buckets中bmap的称为bucket。bucket实际上也可以认为是整条bmap链表，比如扩容时的bucket迁移，实际上就是迁移整条bmap链表。

map创建

当我们使用make创建map时，可以指定一个size参数，当我们没有指定size时，或者size在编译时已知是一个不大于8的数值时（也就是size是一个常量），会通过makemap_small来创建一个map：

1
2
3
4
5
6
7
8
// makehmap_small implements Go map creation for make(map[k]v) and
// make(map[k]v, hint) when hint is known to be at most bucketCnt
// at compile time and the map needs to be allocated on the heap.
func makemap_small() *hmap {
	h := new(hmap)
	h.hash0 = fastrand() // 初始化hash seed
	return h
}

可以看到，通过makemap_small创建的map，此时的B是0，buckets是nil，在第一次写入的时候才会去创建具体的buckets

对应的，当我们指定了一个合适的size时，会通过另一个函数来创建map：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
// makemap implements Go map creation for make(map[k]v, hint).
// If the compiler has determined that the map or the first bucket
// can be created on the stack, h and/or bucket may be non-nil.
// If h != nil, the map can be created directly in h.
// If h.buckets != nil, bucket pointed to can be used as the first bucket.
func makemap(t *maptype, hint int, h *hmap) *hmap {
    // 如果小于0或者过大，则设为0
	if hint < 0 || hint > int(maxSliceCap(t.bucket.size)) {
		hint = 0
	}

	// initialize Hmap
    // 编译器可能会进行优化，在栈上创建map，因此h可能不为空
	if h == nil {
		h = new(hmap)
	}
	h.hash0 = fastrand()

	// find size parameter which will hold the requested # of elements
	B := uint8(0)
    // 根据传入的size来计算B的大小，这里的B是buckets的数量，前文说过，map最多可以容纳 0.65*2^B 个键值对，当超过这个阈值时，会执行扩容
	for overLoadFactor(hint, B) { 
		B++
	}
	h.B = B

	// allocate initial hash table
	// if B == 0, the buckets field is allocated lazily later (in mapassign)
	// If hint is large zeroing this memory could take a while.
	if h.B != 0 {
		var nextOverflow *bmap
        // 创建bucket数组，这里可能会预先分配几个bmap，后续可以直接使用而不需要执行内存分配
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

当我们创建一个map时，如果map中要存储的键值对数据可以估计的话，最好在创建的时候指定好size，这样可以预先分配好bucket的数量。

map的访问

通常我们对map的访问有get、set、delete、和for range操作，在分析具体的实现下时，我们要先来了解一下如果定位一个key的位置，这里先不涉及在执行扩容时的场景。

我们再回顾一下图：

1
2
3
4
5
6
7
8
9
10
11
    bucket数组         bmap中的overflow指向下一个bmap 
  实际上是bmap数组    这些由overflow引用的bucket被称作overflow bucket
|-----------------|  |-----------------|
|k1,..,k8,v1,..,v8|->|k1,..,k8,v1,..,v8|-> ...		  
|-----------------|  |-----------------|
|k1,..,k8,v1,..,v8|-> ...
|-----------------|
|k1,..,k8,v1,..,v8|-> ...
|-----------------|
|k1,..,k8,v1,..,v8|-> ...
|-----------------|

要定位一个key，我们需要先确定这个key是落在哪个bucket中，也就是哪一条bmap链表中，通过计算key的哈希值，然后通过hash%bucket数量的来定位 ，具体的逻辑如下：

1
2
3
4
5
alg := t.key.alg // 这里的t是map的类型描述
hash := alg.hash(key, uintptr(h.hash0)) // 计算hash值
m := bucketMask(h.B) // 这里的m为 1<<B-1
// 这里的hash&m等价于求模操作
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))

当定位到具体的bucket后，只需要从头开始遍历该bmap链表，因为bmap中有个tophash数组，保存了每个key对应的哈希值的高八位，因此我们不需要挨个对每个key进行比较，只需要先比较哈希值的高八位是否相同就行了，如果相同才接着比较key是否相等，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
top := tophash(hash) // 取key的hash值的高八位
	// 这里b是一个bmap指针，如果当前bmap没有，则查找下一个bmap
	for ; b != nil; b = b.overflow(t) { 
        // 遍历当前bmap，这里bucketCnt是常量8，限制一个bmap中最多只有8个键值对
		for i := uintptr(0); i < bucketCnt; i++ {
            // 先比较哈希值高八位，如果不相等则continue
			if b.tophash[i] != top {
				continue
			}
            // 计算当前的key的位置
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            // 是否间接存储（存储的是实际key的地址）
			if t.indirectkey {
				k = *((*unsafe.Pointer)(k))
			}
            // 比较key是否相等
			if alg.equal(key, k) {
				......
			}
		}
	}
get

与get相关的方法有多个：

1
2
3
4
5
6
// val := m[key]
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
// val,has := m[key]
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) 
// for-range时，用于获取key和val
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer)

这三个方法大同小异，这里只分析第一个方法：

先看该函数的注释，如果key不存在时，返回的是对应的val类型的空值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the value type if
// the key is not in the map.
// NOTE: The returned pointer may keep the whole map live, so don't
// hold onto it for very long.
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 如果我们访问的map是nil或者map中没有存储内容，直接返回零值
	if h == nil || h.count == 0 {
		return unsafe.Pointer(&zeroVal[0])
	}
    // map不是并发安全的，如果存在写操作则panic，因此我们需要在多个goroutine对map进行并发读写时，需要加锁保护
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	alg := t.key.alg
    // 计算key的哈希值
	hash := alg.hash(key, uintptr(h.hash0))
    // 获取buckets数组长度的掩码
	m := bucketMask(h.B)
    // 定位key所在的bucket
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    // 当前是否处于扩容操作，当发生扩容操作时，或重新分配buckets数组，并且需要将旧的buckets内的键值对迁移到新的buckets数组中，这个迁移过程不是一次性完成的而是分批完成的
	if c := h.oldbuckets; c != nil {
       	// 扩容操作有两种：第一种，如果是因为当前的键值对数量已经达到了阈值0.65*2^B，则会触发扩容，这时候新的buckets数组的数量为原来的2倍；第二种是当前键值对数量并没有达到阈值，但是当前存在太多的overflow bucket，可能是因为之前存储了太多的键值对，但是后面又被删除掉了，这时候有的bucket链表会比较长，但是实际上存储的键值对比较稀疏，这样会影响查找效率，这种情况会触发sameSizeGrow，即扩容时buckets数组长度与原来一致
        // 如果是前一种，则原先的buckets数量的掩码是m>>1
		if !h.sameSizeGrow() {
			// There used to be half as many buckets; mask down one more power of two.
			m >>= 1
		}
        // 计算该key落在的oldbuckets中的哪个bucket中
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
        // 如果当前bucket还没有迁移，则在该bucket中查询，迁移操作是按照bucket为单位进行的
		if !evacuated(oldb) {
			b = oldb
		}
	}
    // 获取哈希值高八位
	top := tophash(hash)
    // 遍历bmap链表
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
            // 比较哈希值高八位
			if b.tophash[i] != top {
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey {
				k = *((*unsafe.Pointer)(k))
			}
            // 比较key是否相等
			if alg.equal(key, k) {
                // 获取key对应的val，这里的计算公式在前面结构定义一节中已经说明过
				v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                // 如果这里存储的是val的地址
				if t.indirectvalue {
					v = *((*unsafe.Pointer)(v))
				}
				return v
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}
set

set操作对应的方法是mapassign，这个方法为指定的key分配一个用于存放val的槽，或者返回已经存在的槽，新的val直接写入这个槽中，即完成了map的set操作。

在写入时，因为可能该key已经存在，因此需要先遍历目标bucket的bmap链表，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
// Like mapaccess, but allocates a slot for the key if it is not present in the map.
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	// 不允许写入空map
    if h == nil {
		panic(plainError("assignment to entry in nil map"))
	}
    // 如果有并发写操作，直接panic
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
	alg := t.key.alg
    // 计算key的哈希值
	hash := alg.hash(key, uintptr(h.hash0))

	// Set hashWriting after calling alg.hash, since alg.hash may panic,
	// in which case we have not actually done a write.
    // 设置写标志
	h.flags |= hashWriting
	// 如果buckets数组为空，则会创建一个长度为1的buckets数组
	if h.buckets == nil {
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}

again:
    // 计算目标bucket在buckets数组中的索引
	bucket := hash & bucketMask(h.B)
    // 如果当前正在执行扩容操作，则会执行迁移操作，前面说过扩容时的迁移操作是分批进行的，而迁移是按照bucket为单位进行的，而触发迁移的时机是执行写操作
	if h.growing() {
        // 该函数会执行迁移操作，迁移的目标是bucket%len_of_oldbuckets
		growWork(t, h, bucket) 
	}
    // 计算要写入的bucket
	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
    // 计算哈希值高八位
	top := tophash(hash)
	// 在bmap中要插入的索引，如果前文所说，一个bmap最多可以有8个键值对
	var inserti *uint8
    // 要插入key的地址
	var insertk unsafe.Pointer
    // 对应的val的地址
	var val unsafe.Pointer
    // 因为前面已经执行过扩容操作，因此写入只需要对新的bucket进行操作
	for {
        // 遍历当前bmap
		for i := uintptr(0); i < bucketCnt; i++ {
            // 高八位哈希值不相同
			if b.tophash[i] != top {
                // 对第一个遇到的空槽，设置为待定槽，因为可能在后续遍历中发现当前key已经存在，则直接返回对应的val就好了
				if b.tophash[i] == empty && inserti == nil {
					inserti = &b.tophash[i]
					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
					val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
				}
				continue
			}
            // 这里说明哈希值高八位一致，因此需要比较key是否相等
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey {
				k = *((*unsafe.Pointer)(k))
			}
            // 如果不相等，继续遍历下一个
			if !alg.equal(key, k) {
				continue
			}
			// 如果key已经存在，直接返回对应的val地址就好了
			if t.needkeyupdate {
				typedmemmove(t.key, k, key)
			}
			val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            // goto大法好
			goto done
		}
        // 当前bmap没有找到对应的key，则继续遍历下一个bmap
		ovf := b.overflow(t)
		if ovf == nil { // 如果当前bucket已经遍历完成，则跳出
			break
		}
		b = ovf
	}
	
    // 首先判断是否需要进行扩容：如果当前没有扩容操作正在执行并且数据达到阈值或者存在太多的bmap，则会触发扩容操作
	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
	}
	// 如果不需要扩容操作，并且没有可以使用的空槽，则需要分配一个新的overflow bucket，这里是分配在链表尾部，当前的b指向的就是整条bmap链表的最后一个节点
	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)
		val = add(insertk, bucketCnt*uintptr(t.keysize))
	}

	// store new key/value at insert position
    // 设置key
    // 这里针对是否需要对key或者val进行间接存储的处理
	if t.indirectkey {
		kmem := newobject(t.key)
		*(*unsafe.Pointer)(insertk) = kmem
		insertk = kmem
	}
	if t.indirectvalue {
		vmem := newobject(t.elem)
		*(*unsafe.Pointer)(val) = vmem
	}
	typedmemmove(t.key, insertk, key)
	*inserti = top
	h.count++	// map中元素数据加1

done:
    // 检查写操作标志位
	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
    // 清除写操作
	h.flags &^= hashWriting
	if t.indirectvalue {
		val = *((*unsafe.Pointer)(val))
	}
	return val
}
delete

删除操作流程如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
   if h == nil || h.count == 0 {
      return
   }
    // 设置写操作标志位
   if h.flags&hashWriting != 0 {
      throw("concurrent map writes")
   }

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

   // Set hashWriting after calling alg.hash, since alg.hash may panic,
   // in which case we have not actually done a write (delete).
   h.flags |= hashWriting

   bucket := hash & bucketMask(h.B)
    // 如果正在扩容，先执行迁移操作
   if h.growing() {
      growWork(t, h, bucket)
   }
   b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   top := tophash(hash)
search:
    // 查找要删除的可以，因为前面已经执行了迁移操作，因此这里只需要在新的bucket中查找即可
   for ; b != nil; b = b.overflow(t) {
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top {
            continue
         }
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         k2 := k
         if t.indirectkey {
            k2 = *((*unsafe.Pointer)(k2))
         }
         if !alg.equal(key, k2) {
            continue
         }
         // 执行清除操作
         // Only clear key if there are pointers in it.
         if t.indirectkey {
            *(*unsafe.Pointer)(k) = nil
         } else if t.key.kind&kindNoPointers == 0 {
            memclrHasPointers(k, t.key.size)
         }
         v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
         if t.indirectvalue {
            *(*unsafe.Pointer)(v) = nil
         } else if t.elem.kind&kindNoPointers == 0 {
            memclrHasPointers(v, t.elem.size)
         } else {
            memclrNoHeapPointers(v, t.elem.size)
         }
         b.tophash[i] = empty // 将tophash中的值设为empty，表示空槽
         h.count-- // 数量减一
         break search
      }
   }

   if h.flags&hashWriting == 0 {
      throw("concurrent map writes")
   }
   h.flags &^= hashWriting
}
for-range

执行for-range操作时，需要一个迭代器，我们先来看迭代器的声明：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// A hash iteration structure.
type hiter struct {
	key         unsafe.Pointer // key值，nil表示迭代结束
	value       unsafe.Pointer // val值
	t           *maptype
	h           *hmap
	buckets     unsafe.Pointer // bucket ptr at hash_iter initialization time
	bptr        *bmap          // 当前正在迭代的buckete的指针
	overflow    *[]*bmap       // keeps overflow buckets of hmap.buckets alive
	oldoverflow *[]*bmap       // keeps overflow buckets of hmap.oldbuckets alive
	startBucket uintptr        // 记录这次迭代从哪个bucket开始
	offset      uint8          // 记录这次迭代从hmap中的哪个offset开始
	wrapped     bool           // already wrapped around from end of bucket array to beginning
	B           uint8
	i           uint8
	bucket      uintptr
	checkBucket uintptr
}

hiter的创建：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
func mapiterinit(t *maptype, h *hmap, it *hiter) {
	if h == nil || h.count == 0 {
		return
	}

	it.t = t // 记录map类型信息
	it.h = h // 引用map

	// grab snapshot of bucket state
	it.B = h.B // 记录当前的B
	it.buckets = h.buckets // 记录当前的buckets
    // 如果当前map中的键值对没有指针
	if t.bucket.kind&kindNoPointers != 0 {
		// Allocate the current slice and remember pointers to both current and old.
		// This preserves all relevant overflow buckets alive even if
		// the table grows and/or overflow buckets are added to the table
		// while we are iterating.
		h.createOverflow()
		it.overflow = h.extra.overflow
		it.oldoverflow = h.extra.oldoverflow
	}

	// decide where to start
    // 这里随机选举一个开始迭代的位置，因此我们对map进行for-range操作，每次输出的序列都是不同的
	r := uintptr(fastrand())
	if h.B > 31-bucketCntBits {
		r += uintptr(fastrand()) << 31
	}
    // 设置开始的bucket和offset
	it.startBucket = r & bucketMask(h.B)
	it.offset = uint8(r >> h.B & (bucketCnt - 1))

	// 当前迭代的bucket索引
	it.bucket = it.startBucket

	// 设置迭代标志位
	if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
		atomic.Or8(&h.flags, iterator|oldIterator)
	}
	// 执行next操作
	mapiternext(it)
}

mapiternext方法用于推进迭代器前进到下一个键值对，对应逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

func mapiternext(it *hiter) {
	h := it.h
	if h.flags&hashWriting != 0 {
		throw("concurrent map iteration and map write")
	}
	t := it.t
	bucket := it.bucket
	b := it.bptr // 当前正在遍历的bucket
	i := it.i
	checkBucket := it.checkBucket
	alg := t.key.alg

next:
	if b == nil { // 如果it.bptr还没有初始化，需要根据it.bucket进行初始化，第一次执行或者每次遍历完一个bucket都会清空bptr
		if bucket == it.startBucket && it.wrapped {
			// end of iteration
			it.key = nil
			it.value = nil
			return
		}
        // 如果正在执行扩容，并且迭代是在扩容之后开始的，这时候如果旧的bucket还没有迁移到新的bucket中，那么需要到旧的bucket中遍历
		if h.growing() && it.B == h.B {
            // 获取当前要迭代的bucket对应的oldbucket
			oldbucket := bucket & it.h.oldbucketmask()
			b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
            // 如果oldbucket中的元素还没有迁移到新的bucket中
			if !evacuated(b) {
				checkBucket = bucket // oldbucket中的键值对迁移到新的bucket中时，可能会迁移到两个bucket中，比如原来长度是4，hash%4等于3，限制长度是8，hash%8可能为4也可能为7，这里的checkBucket记录当前正在遍历h.buckets数组中的哪个bucket，用于后面的判断
			} else {
                // 已经迁移完成，直接在新的bucket中遍历
				b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
				checkBucket = noCheck
			}
		} else { // 当前没有扩容操作，直接在新的bucket中遍历
			b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
			checkBucket = noCheck
		}
		bucket++ // 下一次遍历的bucket的索引
        // 因为开始迭代的bucket位置是随机的，如果越界了，从第一个bucket开始
		if bucket == bucketShift(it.B) {
			bucket = 0
			it.wrapped = true
		}
		i = 0
	}
    // 遍历bmap中键值对
	for ; i < bucketCnt; i++ {
        // 计算开始遍历的偏移位置
		offi := (i + it.offset) & (bucketCnt - 1)
        // 如果空槽，则跳过
		if b.tophash[offi] == empty || b.tophash[offi] == evacuatedEmpty {
			continue
		}
        // 获取key
		k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
		if t.indirectkey {
			k = *((*unsafe.Pointer)(k))
		}
        // 获取val
		v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize))
        // 如果正在执行扩容，并且正在遍历的bucket还没有迁移完成，并且扩容是由于键值对达到阈值触发的，这时候扩容后的buckets数组的长度为原来的两倍，原来的一个bucket中的键值对迁移时会迁移到新的两个bucket中，因为目标bucket是通过哈希取模计算的，而这时候bucket数组长度扩大了两倍，比如原理数组长度是4，取模后是3，现在数组长度是8，取模后可能为3也可能为7
		if checkBucket != noCheck && !h.sameSizeGrow() {
            // 如果key==key，正常都是走这个逻辑
			if t.reflexivekey || alg.equal(k, k) { 
				// 如果当前的key不是落在当前的bucket中的，比如现在正在遍历的bucket为3，但是key现在的hash是7，以后迁移时将迁移到索引为7的bucket中，因此这个时候应该跳过这个key
				hash := alg.hash(k, uintptr(h.hash0))
				if hash&bucketMask(it.B) != checkBucket {
					continue
				}
			} else { // key != key的情况，比如math.NaN() != math.NaN()
				if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
					continue
				}
			} 
		}
        // 走到这里，可能有一种情况，在迭代开始之后发生了扩容（比如我们在for-range里面插入新的键值对，这时候触发了迁移），这时候迭代的是扩容之前的键值对，即只会迭代当前的oldbuckets里面键值对，这时候如果这些键值对还没有发生迁移或者说key是不可比较的，比如key为math.NAN()，因为key!=key，因此这个key不会被删除或者更新，可以直接返回
		if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
			!(t.reflexivekey || alg.equal(k, k)) {
			it.key = k
			if t.indirectvalue {
				v = *((*unsafe.Pointer)(v))
			}
			it.value = v
		} else { // 走到这里说明发生了迁移，使用mapaccessK来获取
			rk, rv := mapaccessK(t, h, k)
			if rk == nil { // 已经被删除了
				continue // key has been deleted
			}
			it.key = rk
			it.value = rv
		}
        // 更新迭代器状态
		it.bucket = bucket
		if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
			it.bptr = b
		}
		it.i = i + 1
		it.checkBucket = checkBucket
		return
	}
    // 当前bmap遍历完成，遍历下一个bmap，如果已经是bmap链表的最后一个节点，则返回的b为nil，这时候会触发遍历下一个bucket
	b = b.overflow(t)
	i = 0
	goto next
}

扩容

当写入时，如果当前bucket已经满了，则会触发扩容检查，如果当前不处于扩容状态并且满足：

  • 当前键值对个数已经达到 6.5*2^B
  • 当前overflow bucket数量达到1<<(B&15)，这里的B如果大于15，按照15计算

下面看一下开始扩容的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
func hashGrow(t *maptype, h *hmap) {
	// If we've hit the load factor, get bigger.
	// Otherwise, there are too many overflow buckets,
	// so keep the same number of buckets and "grow" laterally.
	bigger := uint8(1)
    // 如果键值对数量没有达到阈值，则说明是overflow bucket数量过多触发的
	if !overLoadFactor(h.count+1, h.B) {
		bigger = 0 // 这里将bigger设置成了0
		// 设置标志位，用于后续区分是哪种情况触发的扩容
		// 如果是overflow bucket数量过多触发的，实际上并不会增加bucket的数量
		// 因此称作sameSizeGrow
		h.flags |= sameSizeGrow
	}

	// 保存原来的buckets到oldbuckets
	oldbuckets := h.buckets
	// 分配新的buckets
	// 如果是键值对达到阈值触发的扩容，bucket数量为原来的2倍，也就是扩展buckets数组
	// 否则维持原来的数量
	newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
	// 设置更新迭代标志位
	flags := h.flags &^ (iterator | oldIterator)
	if h.flags&iterator != 0 {
		flags |= oldIterator
	}
	// commit the grow (atomic wrt gc)
    // 更新hmap字段
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	h.nevacuate = 0
	h.noverflow = 0

	if h.extra != nil && h.extra.overflow != nil {
		// Promote current overflow buckets to the old generation.
		if h.extra.oldoverflow != nil {
			throw("oldoverflow is not nil")
		}
		h.extra.oldoverflow = h.extra.overflow
		h.extra.overflow = nil
	}
	if nextOverflow != nil {
		if h.extra == nil {
			h.extra = new(mapextra)
		}
		h.extra.nextOverflow = nextOverflow
	}

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

再来看一下bucket的迁移操作：

1
2
3
4
5
6
7
8
9
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 迁移正在使用的bucket对应的oldbucket的数据
	evacuate(t, h, bucket&h.oldbucketmask())

	// 继续对h.nevacuate对应的bucket进行迁移，让迁移尽快完成
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

从上面可以看到，一次growwork最多可以迁移两个bucket，这样可以尽早完成扩容之后的迁移

接着看一下evacuate的逻辑：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    // 计算要进行迁移的bucket
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
	newbit := h.noldbuckets() // 获取oldbuckets数组的长度
    // 如果还没有执行过迁移
	if !evacuated(b) {
		// 一个oldbucket中的key可能迁移到两个新的bucket中，这里使用x来表示低位目标bucket，y表示高位目标bucket
		var xy [2]evacDst
		x := &xy[0]
        // 低位目标bucket的索引和当前要迁移的oldbucket的索引一致
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
		x.k = add(unsafe.Pointer(x.b), dataOffset)
		x.v = add(x.k, bucketCnt*uintptr(t.keysize))
		// 如果是sameSizeGrow，buckets长度没有变化，则不会有高位目标bucket
		if !h.sameSizeGrow() {
			// Only calculate y pointers if we're growing bigger.
			// Otherwise GC can see bad pointers.
			y := &xy[1]
            // 计算高位目标bucket
			y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
			y.k = add(unsafe.Pointer(y.b), dataOffset)
			y.v = add(y.k, bucketCnt*uintptr(t.keysize))
		}
		// 遍历bucket对应的bmap链表
		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			v := add(k, bucketCnt*uintptr(t.keysize))
			for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
				top := b.tophash[i]
				if top == empty { // 空槽，没有键值对
					b.tophash[i] = evacuatedEmpty
					continue
				}
				if top < minTopHash {
					throw("bad map state")
				}
				k2 := k
				if t.indirectkey {
					k2 = *((*unsafe.Pointer)(k2))
				}
				var useY uint8
                // 不是sameSizeGrow，说明可能会迁移到高位目标bucket
				if !h.sameSizeGrow() {
					hash := t.key.alg.hash(k2, uintptr(h.hash0))
                    // 存在迭代器，并且key!=key(NaNs)，一般不会走这个分支
					if h.flags&iterator != 0 && !t.reflexivekey && !t.key.alg.equal(k2, k2) {
						useY = top & 1
						top = tophash(hash)
					} else {
                        // 比如hash是7，oldbuckets长度是4，现在是8，原来bucket是3，现在应该迁移到7这个bucket，这种情况hash&newbit=newbit    
						if hash&newbit != 0 {
							useY = 1
						}
					}
				}
                // 这里是对全局常量进行检查：evacuatedY=evacuatedX+1
                // evacuatedX标记迁移到低位目标bucket
                // evacuatedY标记迁移到高位目标bucket
				if evacuatedX+1 != evacuatedY {
					throw("bad evacuatedN")
				}
				// 对当前槽进行标记，表示已经完成迁移
				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
                // 根据是否迁移到高位bucket选择目标bucket
				dst := &xy[useY]                 // evacuation destination
				// 如果当前bmap满了，创建新的bmap
				if dst.i == bucketCnt {
					dst.b = h.newoverflow(t, dst.b)
					dst.i = 0
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
					dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
				}
                // 执行键值对迁移
				dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
				if t.indirectkey {
					*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
				} else {
					typedmemmove(t.key, dst.k, k) // copy value
				}
				if t.indirectvalue {
					*(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v)
				} else {
					typedmemmove(t.elem, dst.v, v)
				}
              	// 更新迁移目标状态
				dst.i++
				// These updates might push these pointers past the end of the
				// key or value arrays.  That's ok, as we have the overflow pointer
				// at the end of the bucket to protect against pointing past the
				// end of the bucket.
				dst.k = add(dst.k, uintptr(t.keysize))
				dst.v = add(dst.v, uintptr(t.valuesize))
			}
		}
		// Unlink the overflow buckets & clear key/value to help GC.
        // 如果不存在对oldbuckets的迭代器并且键值对中包含指针，在oldbuckets清除当前迁移的bucket，帮助尽快gc掉这些没有用的内存
		if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
			// Preserve b.tophash because the evacuation
			// state is maintained there.
			ptr := add(b, dataOffset)
			n := uintptr(t.bucketsize) - dataOffset
			memclrHasPointers(ptr, n)
		}
	}
	// 如果当前迁移的bucket等于h.nevacuate则更新h.nevacuate的值
    // 如果所有bucket都已经迁移完成，则消除扩容状态
	if oldbucket == h.nevacuate {
		advanceEvacuationMark(h, t, newbit)
	}
}