1
2

$ cat /proc/cpuinfo | grep aes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 clflush dts mmx fxsr sse sse2 ss ht syscall nx pdpe1gb rdtscp lm constant_tsc arch_perfmon pebs bts nopl xtopology tsc_reliable nonstop_tsc aperfmperf eagerfpu pni pclmulqdq ssse3 fma cx16 pcid sse4_1 sse4_2 x2apic movbe popcnt tsc_deadline_timer aes xsave avx f16c rdrand hypervisor lahf_lm abm 3dnowprefetch epb fsgsbase tsc_adjust bmi1 hle avx2 smep bmi2 invpcid rtm rdseed adx smap xsaveopt dtherm ida arat pln pts

1
2
3

// Hashing algorithm inspired by
//   xxhash: https://code.google.com/p/xxhash/
// cityhash: https://code.google.com/p/cityhash/

 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

const (
	// 一个桶中最多能装载的键值对的个数为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，以下列出的就是一些特殊状态值。

	// 表示cell为空，并且比它高索引位的cell或者overflows中的cell都是空的。（初始化bucket时，就是该状态）
	emptyRest = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows.
	// 空的cell，cell已经被搬迁到新的bucket
	emptyOne = 1 // this cell is empty
	// 键值对已经搬迁完毕，key在新buckets数组的前半部分
	evacuatedX = 2 // key/elem is valid.  Entry has been evacuated to first half of larger table.
	// 键值对已经搬迁完毕，key在新buckets数组的后半部分
	evacuatedY = 3 // same as above, but evacuated to second half of larger table.
	// cell为空，整个bucket已经搬迁完毕
	evacuatedEmpty = 4 // cell is empty, bucket is evacuated.
	// tophash的最小正常值
	minTopHash = 5 // minimum tophash for a normal filled cell.

	// flags
	// 可能有迭代器在使用buckets
	iterator = 1 // there may be an iterator using buckets
	// 可能有迭代器在使用oldbuckets
	oldIterator = 2 // there may be an iterator using oldbuckets
	// 有协程正在向map写入key
	hashWriting = 4 // a goroutine is writing to the map
	// 等量扩容
	sameSizeGrow = 8 // the current map growth is to a new map of the same size

	// 用于迭代器检查的bucket ID
	noCheck = 1<<(8*sys.PtrSize) - 1
)

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// A header for a Go map.
type hmap struct {
	// Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
	// Make sure this stays in sync with the compiler's definition.
	// 键值对的数量
	count int // # live cells == size of map.  Must be first (used by len() builtin)
	// 标识状态
	flags uint8
	// 2^B = len(buckets)
	B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	// 溢出桶里bmap大致数量
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	// hash因子
	hash0 uint32 // hash seed
	// 指向一个数组（连续内存空间），数组类型为[]bmap，bmap类型就是存在键值对的结构
	buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
	// 扩容时，存放之前的buckets
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
	// 分流次数，成倍扩容分流操作计数的字段
	nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
	// 溢出桶结构，正常桶里面某个bmap存满了，会使用这里面的内存空间存放键值对
	extra *mapextra // optional fields
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

// mapextra holds fields that are not present on all maps.
type mapextra struct {
	// If both key and elem do not contain pointers and are inline, then we mark bucket
	// type as containing no pointers. This avoids scanning such maps.
	// However, bmap.overflow is a pointer. In order to keep overflow buckets
	// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
	// overflow and oldoverflow are only used if key and elem do not contain pointers.
	// overflow contains overflow buckets for hmap.buckets.
	// oldoverflow contains overflow buckets for hmap.oldbuckets.
	// The indirection allows to store a pointer to the slice in hiter.
	// 溢出桶，当正常桶存满后就使用hmap.extra.overflow的bmap
	// bmap.overflow是指针类型，存放了对应使用的hmap.extra.overflow里的bmap地址
	overflow *[]*bmap
	// 扩容时存放之前的overflow
	oldoverflow *[]*bmap

	// nextOverflow holds a pointer to a free overflow bucket.
	// 指向溢出桶里下一个可以使用的bmap
	nextOverflow *bmap
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// A bucket for a Go map.
type bmap struct {
	// tophash generally contains the top byte of the hash value
	// for each key in this bucket. If tophash[0] < minTopHash,
	// tophash[0] is a bucket evacuation state instead.
	// tophash包含此桶中每个键的哈希值最高字节（高8位）信息（也就是前面所述的high-order bits）。
	// 如果tophash[0] < minTopHash，tophash[0]则代表桶的搬迁（evacuation）状态。
	tophash [bucketCnt]uint8
	// Followed by bucketCnt keys and then bucketCnt elems.
	// NOTE: packing all the keys together and then all the elems together makes the
	// code a bit more complicated than alternating key/elem/key/elem/... but it allows
	// us to eliminate padding which would be needed for, e.g., map[int64]int8.
	// Followed by an overflow pointer.
}

1
2
3
4
5
6

type bmap struct {
    topbits  [8]uint8		// 长度为8的数组，元素为：key获取的hash的高8位，遍历时对比使用，提高性能。
    keys     [8]keytype		// 长度为8的数组，[]keytype，元素为：具体的key值
    values   [8]valuetype	// 长度为8的数组，[]elemtype，元素为：键值对的key对应的值
    overflow uintptr		// 指向hmap.extra.overflow溢出桶里的`bmap`，上面字段长度为8，最多存8组键值对，存满了就往这项的这个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

// bmap makes the map bucket type given the type of the map.
func bmap(t *types.Type) *types.Type {
   ...
   field := make([]*types.Field, 0, 5)

   // The first field is: uint8 topbits[BUCKETSIZE].
   arr := types.NewArray(types.Types[TUINT8], BUCKETSIZE)
   field = append(field, makefield("topbits", arr))

   arr = types.NewArray(keytype, BUCKETSIZE)
   arr.SetNoalg(true)
   keys := makefield("keys", arr)
   field = append(field, keys)

   arr = types.NewArray(elemtype, BUCKETSIZE)
   arr.SetNoalg(true)
   elems := makefield("elems", arr)
   field = append(field, elems)

   // If keys and elems have no pointers, the map implementation
   // can keep a list of overflow pointers on the side so that
   // buckets can be marked as having no pointers.
   // Arrange for the bucket to have no pointers by changing
   // the type of the overflow field to uintptr in this case.
   // See comment on hmap.overflow in runtime/map.go.
   otyp := types.NewPtr(bucket)
   if !types.Haspointers(elemtype) && !types.Haspointers(keytype) {
      otyp = types.Types[TUINTPTR]
   }
   overflow := makefield("overflow", otyp)
   field = append(field, overflow)

   t.MapType().Bucket = bucket

   bucket.StructType().Map = t
   return bucket
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

type maptype struct {
	typ    _type
	key    *_type
	elem   *_type
	bucket *_type // internal type representing a hash bucket
	// function for hashing keys (ptr to key, seed) -> hash
	// 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
}

1
2

make(map[k]v)
make(map[k]v,hint)

 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

func makemap(t *maptype, hint int, h *hmap) *hmap {
	// math.MulUintptr返回hint与t.bucket.size的乘积，并判断该乘积是否溢出。
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	// initialize Hmap
	if h == nil {
		h = new(hmap)
	}
	// 得到哈希种子
	h.hash0 = fastrand()

	// Find the size parameter B which will hold the requested # of elements.
	// For hint < 0 overLoadFactor returns false since hint < bucketCnt.
	// 根据输入的元素个数hint，找到能装下这些元素的B值
	B := uint8(0)
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// 分配初始哈希表
	// 如果 B==0，那么buckets字段会在后续的mapassign方法中lazily分配
	// 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
		// makeBucketArray创建一个map的底层保存buckets的数组，至少会分配 B^2 的大小
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		if nextOverflow != nil {
			h.extra = new(mapextra)
			h.extra.nextOverflow = nextOverflow
		}
	}

	return h
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

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
}

1

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

1
2
3
4
5
6
7
8

// tophash calculates the tophash value for hash.
func tophash(hash uintptr) uint8 {
   top := uint8(hash >> (sys.PtrSize*8 - 8))
   if top < minTopHash {
      top += minTopHash
   }
   return top
}

 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

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	// 如果map为空或元素个数为0，返回零值
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
		return unsafe.Pointer(&zeroVal[0])
	}
	// 如果flag为hashWriting，则报错，表示map不是并发安全的
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	// 不同类型的key，会使用不同的hash算法，在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中的数据可能还未搬迁到新的bucket中
	// 所以要先在老的bucket中查找
	if c := h.oldbuckets; c != nil {
		if !h.sameSizeGrow() {
			// There used to be half as many buckets; mask down one more power of two.
			m >>= 1
		}
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		// 如果在oldbuckets中的tophash[0]的值，为evacuatedX，evacuatedY，evacuatedEmpty其中之一
		// 则evacuated()返回为true，代表搬迁完成
		// 因此，只有当搬迁未完成时，未完成时，才会从此oldbuckets中遍历
		if !evacuated(oldb) {
			b = oldb
		}
	}

	// 取出当前key的tophash值
	top := tophash(hash)
	// 以下是查找的核心逻辑
	// 双重循环遍历：外层循环是从桶到溢出桶遍历；内层是桶中的cell遍历
	// 跳出循环的条件有三种：第一种是找到key值；第二种是当前桶无溢出桶；第三种是当前桶中有cell位的tophash=emptyRest，代表桶还未使用，无需遍历
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))
			}
			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
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}

1
2
3
4

// key的定位公式
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// value的定位公式
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))

  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
125
126
127
128
129
130
131
132
133
134
135
136

// 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 {
	if h == nil {
		panic(plainError("assignment to entry in nil map"))
	}
	// 如果有其他goroutine正在写map，会抛错
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
	// 通过key和哈希种子，计算哈希值
	hash := t.hasher(key, uintptr(h.hash0))

	// Set hashWriting after calling t.hasher, since t.hasher may panic,
	// in which case we have not actually done a write.
	// 设置写标识位
	h.flags ^= hashWriting

	if h.buckets == nil {
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}

again:
	// 通过hash与bucketMask按位与操作，返回在buckets数组的第几号桶
	bucket := hash & bucketMask(h.B)
	// 如果map正在搬迁（即m.oldbuckets!=nil）中，则先进行搬迁工作
	if h.growing() {
		growWork(t, h, bucket)
	}
	// 计算出上面求出的第几号桶的内存位置
	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]
			// 所以如果后面再插入的话，会尽量往前面的位置插
			// 在循环的时候还要顺便把前面的空位置先记下来，因为有可能在后面找到相等的key
			if b.tophash[i] != top {
				// 如果cell位为空，那么就可以在对应位置进行插入
				if isEmpty(b.tophash[i]) && inserti == nil {
					// 赋值当前hash的高8位，标记写入成功
					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
			}
			// already have a mapping for key. Update it.
			// 如果已经有该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))
			goto done
		}
		// 正常桶的bmap遍历完了，继续遍历溢出桶的bmap，如果有的话
		ovf := b.overflow(t)
		if ovf == nil {
			break
		}
		b = ovf
	}

	// 在已有的桶和溢出桶中都未找到合适的cell供key写入，那么有可能会触发以下两种情况
	// 1、判断当前map的装载因子是否达到设定的6.5阈值，或者当前map的溢出桶数量是否过多，如果存在这两种情况，进行扩容操作。
	// hashGrow()实际并未完成扩容，对哈希表数据的搬迁(复制)操作是通过growWork()来完成的
	// 重新进入again逻辑，在完成growWork()操作后，再次遍历新的桶
	// Did not find mapping for key. Allocate new cell & add entry.

	// If we hit the max load factor or we have too many overflow buckets,
	// and we're not already in the middle of growing, start growing.
	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
	}

	// 2、为当前桶新建新的溢出桶，并将tophash，key插入到新建溢出桶的对应内存的0号位置
	if inserti == nil {
		// all current buckets are full, allocate a new one.
		// 分配新的bmap写
		newb := h.newoverflow(t, b)
		inserti = &newb.tophash[0]
		insertk = add(unsafe.Pointer(newb), dataOffset)
		elem = add(insertk, bucketCnt*uintptr(t.keysize))
	}

	// store new key/elem at insert position
	// 在插入位置存入新的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
}

  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

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
		return
	}
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}

	// 计算key的哈希值
	hash := t.hasher(key, uintptr(h.hash0))

	// Set hashWriting after calling t.hasher, since t.hasher 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)))
	bOrig := b
	top := tophash(hash)
search:
	for ; b != nil; b = b.overflow(t) {
		// 遍历桶
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break search
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			k2 := k
			if t.indirectkey() {
				k2 = *((*unsafe.Pointer)(k2))
			}
			if !t.key.equal(key, k2) {
				continue
			}
			// Only clear key if there are pointers in it.
			// 找到了key，开始清除key和对应的value
			if t.indirectkey() {
				// 如果指向的是指针，则指针置nil
				*(*unsafe.Pointer)(k) = nil
			} else if t.key.ptrdata != 0 {
				// 清除key的内存
				memclrHasPointers(k, t.key.size)
			}
			// 清除value
			e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
			if t.indirectelem() {
				*(*unsafe.Pointer)(e) = nil
			} else if t.elem.ptrdata != 0 {
				memclrHasPointers(e, t.elem.size)
			} else {
				memclrNoHeapPointers(e, t.elem.size)
			}
			// 标记当前桶的当前槽位为空
			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 {
				b.tophash[i] = emptyRest
				if i == 0 {
					if b == bOrig {
						break // beginning of initial bucket, we're done.
					}
					// Find previous bucket, continue at its last entry.
					c := b
					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
					}
					i = bucketCnt - 1
				} else {
					i--
				}
				if b.tophash[i] != emptyOne {
					break
				}
			}
		notLast:
			h.count--
			break search
		}
	}

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

1

loadFactor := count / (2^B)

1
2
3
4
5

// mapassign中触发扩容的时机
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
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
// 达到装载因子的临界点
func overLoadFactor(count int, B uint8) bool {
	return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// tooManyOverflowBuckets reports whether noverflow buckets is too many for a map with 1<<B buckets.
// Note that most of these overflow buckets must be in sparse use;
// if use was dense, then we'd have already triggered regular map growth.
// 判断溢出桶是否太多。
// 当桶总数<2^15时，如果溢出桶>=桶总数，则认为溢出桶过多。
// 当桶总数>2^15时，当溢出桶>=2^15，则认为溢出桶过多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
	// If the threshold is too low, we do extraneous work.
	// If the threshold is too high, maps that grow and shrink can hold on to lots of unused memory.
	// "too many" means (approximately) as many overflow buckets as regular buckets.
	// See incrnoverflow for more details.
	if B > 15 {
		B = 15
	}
	// The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
	return noverflow >= uint16(1)<<(B&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

// 没有真正搬迁，只是分配好新的buckets，并将老的buckets挂到oldbuckets字段上
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)
	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
	}
	// commit the grow (atomic wrt gc)
	// 提交grow
	h.B += bigger
	h.flags = flags
	h.oldbuckets = oldbuckets
	h.buckets = newbuckets
	// 搬迁进度为0
	h.nevacuate = 0
	// noverflow buckets数为0
	h.noverflow = 0

	// 如果发现hmap是通过extra字段来存储overflow buckets时
	if h.extra != nil && h.extra.overflow != nil {
		// Promote current overflow buckets to the old generation.
		if h.extra.oldoverflow != nil {
			throw("oldoverflow is not nil")
		}
		h.extra.oldoverflow = h.extra.overflow
		h.extra.overflow = nil
	}
	if nextOverflow != nil {
		if h.extra == nil {
			h.extra = new(mapextra)
		}
		h.extra.nextOverflow = nextOverflow
	}

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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

func growWork(t *maptype, h *hmap, bucket uintptr) {
	// make sure we evacuate the oldbucket corresponding
	// to the bucket we're about to use
	// 为了确认搬迁的bucket是我们正在使用的bucket
	// 即如果当前key映射到老的bucket，那么就搬迁该bucket
	evacuate(t, h, bucket&h.oldbucketmask())

	// evacuate one more oldbucket to make progress on growing
	// 如果还未完成扩容
	if h.growing() {
		evacuate(t, h, h.nevacuate)
	}
}

  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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142

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: reuse overflow buckets instead of using new ones, if there
		// is no iterator using the old buckets.  (If !oldIterator.)

		// xy contains the x and y (low and high) evacuation destinations.
		// 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的相关信息
		if !h.sameSizeGrow() {
			// Only calculate y pointers if we're growing bigger.
			// Otherwise GC can see bad pointers.
			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，同样需要搬迁
		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)
			e := add(k, bucketCnt*uintptr(t.keysize))
			// 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
				}
				if top < minTopHash {
					throw("bad map state")
				}
				k2 := k
				if t.indirectkey() {
					k2 = *((*unsafe.Pointer)(k2))
				}
				var useY uint8
				// 如果是增量扩容
				if !h.sameSizeGrow() {
					// Compute hash to make our evacuation decision (whether we need
					// to send this key/elem to bucket x or bucket y).
					// 计算哈希值，判断当前的key和value是否需要搬迁到bucket x/y
					hash := t.hasher(k2, uintptr(h.hash0))
					if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
						// If key != key (NaNs), then the hash could be (and probably
						// will be) entirely different from the old hash. Moreover,
						// it isn't reproducible. Reproducibility is required in the
						// presence of iterators, as our evacuation decision must
						// match whatever decision the iterator made.
						// Fortunately, we have the freedom to send these keys either
						// way. Also, tophash is meaningless for these kinds of keys.
						// We let the low bit of tophash drive the evacuation decision.
						// We recompute a new random tophash for the next level so
						// these keys will get evenly distributed across all buckets
						// after multiple grows.
						// 有一种特殊情况：有一种key，每次对它的计算hash得到的结果不一样。
						// 这个key就是 math.NaN() 的结果，它的含义是not a number，类型是float64
						// 把它当做map的key时，会遇到一个问题：再次计算它的哈希值和它刚插入map时计算的哈希值不一样
						// 这个key是永远不会被Get操作获取的，当使用m[math.NaN()]语句时，是查不出结果的，这个key只有在遍历整个map时，才能被找到
						// 并且，可以向一个 map 插入多个数量的 math.NaN() 作为 key，它们并不会被互相覆盖。
						// 当搬迁碰到 math.NaN() 的 key 时，只通过 tophash 的最低位决定分配到 X part 还是 Y part（如果扩容后是原来 buckets 数量的 2 倍）。
						// 如果 tophash 的最低位是 0 ，分配到 X part；如果是 1 ，则分配到 Y part。
						useY = top & 1
						top = tophash(hash)
					} else {
						if hash&newbit != 0 {
							useY = 1
						}
					}
				}

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

				b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
				// useY要么为0，要么为1。这里就是选取在bucket x的起始内存位置，或者选择在bucket y的起始内存位置（只有增量同步才会有这个选择可能）。
				dst := &xy[useY] // evacuation destination

				// 如果目的地桶已经装满（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 // mask dst.i as an optimization, to avoid a bounds check
				// 如果待搬迁的key是指针，则复制指针
				if t.indirectkey() {
					*(*unsafe.Pointer)(dst.k) = k2 // copy pointer
				} else {
					typedmemmove(t.key, dst.k, k) // copy elem
				}
				if t.indirectelem() {
					*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
				} else {
					typedmemmove(t.elem, dst.e, e)
				}
				// 将当前搬迁目的桶的记录key/value的索引值（也可以理解为cell的索引值）加一
				dst.i++
				// These updates might push these pointers past the end of the
				// key or elem 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.
				// 由于桶的内存布局中在最后还有overflow的指针，所以这里不用担心更新有可能会超出key和value数组的指针地址。
				dst.k = add(dst.k, uintptr(t.keysize))
				dst.e = add(dst.e, uintptr(t.elemsize))
			}
		}
		// Unlink the overflow buckets & clear key/elem to help GC.
		// 如果没有协程在使用老的桶，就对老的桶进行清理，用于帮助GC
		if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
			b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
			// Preserve b.tophash because the evacuation
			// state is maintained there.
			// 只清除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)
	}
}