基本数据结构map源码剖析

1

index := hash("author") % array.len

1

index := hash("Key6") % array.len

1

装载因子:=元素数量÷桶数量

 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

// 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.
	// 元素个数，调用 len(map) 时，直接返回此值
	count     int // # live cells == size of map.  Must be first (used by len() builtin)
	//标志位
	// iterator     = 1 // 可能有遍历用buckets
	// oldIterator  = 2 // 可能有遍历用oldbuckets，用于扩容期间
	// hashWriting  = 4 // 标记写，用于并发读写检测
	// sameSizeGrow = 8 // 用于等大小buckets扩容，减少overflow桶
	flags     uint8
	// buckets 的对数 log_2
	// B 表示当前哈希表持有的 buckets 数量，但是因为哈希表中桶的数量都 2 的倍数，所以该字段会存储对数，也就是 `len(buckets) == 2^B`；
	B         uint8  // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
	// overflow 的 bucket 近似数
	noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
	// 计算 key 的哈希的时候会传入哈希函数
	// hash0 是哈希的种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入；
	hash0     uint32 // hash seed
	// 指向 buckets 数组，大小为 2^B
   	// 如果元素个数为0，就为 nil
	// 指向第一个桶的指针 是一个连续的地址 因为是个数组
  	// 这里面存的是 *bmap
	buckets    unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
	// 扩容的时候，buckets 长度会是 oldbuckets 的两倍
	// oldbuckets 是哈希在扩容时用于保存之前 buckets 的字段，它的大小是当前 buckets 的一半
	// 旧桶第一个桶的指针，用于在扩容搬迁的时候未完成搬迁时保存之前的旧桶
	oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
	// 指示扩容进度，小于此地址的 buckets 迁移完成
	// 搬迁桶的进度 就是处于扩容搬迁时，目前搬到哪了
	nevacuate  uintptr        // progress counter for evacuation (buckets less than this have been evacuated)
	// 溢出桶  当bmap中存储的数据过多
  	// 单个bmap已经装满时就会使用 extra.nextOverflow 中桶存储溢出的数据。
  	// 溢出桶不一定会使用，因为他是个可选字段
	extra *mapextra // optional fields
}

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

// Maximum number of key/elem pairs a bucket can hold.
bucketCntBits = 3
bucketCnt     = 1 << bucketCntBits
// A bucket for a Go map.
type bmap struct {
	// 记录桶内8个单元的高8位hash值，或标记空桶状态，用于快速定位key
	// emptyRest      = 0 // 此单元为空，且更高索引的单元也为空
	// emptyOne       = 1 // 此单元为空
	// evacuatedX     = 2 // 用于表示扩容迁移到新桶前半段区间
	// evacuatedY     = 3 // 用于表示扩容迁移到新桶后半段区间
	// evacuatedEmpty = 4 // 用于表示此单元已迁移
	// minTopHash     = 5 // 最小的空桶标记值，小于其则是空桶标志
	// 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 [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
 7
 8
 9
10
11
12
13
14
15
16
17
18

// 实际存储k，v数据的桶
// 该结构体还有一些字段会在编译期添加
// 比如 下一个溢出桶的地址
// key，value所处的地址等
type bmap struct {
    // 这里存储可 Key的哈希值的高8位 例子 11111111 00000000
    // 用于在查找时快速的去判断当前Key是否存在这个桶里
    // 因此得出，每个桶只能存放8个Key-Value映射
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    // overflow 桶
    // otyp 类型为指针*Type,
    // 若keytype及elemtype不含指针，则为uintptr
    // 使bmap整体不含指针,避免gc去scan此类map
    overflow uintptr
}

1

map[int64]int8

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

// 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.
	// 如果key和value都不包含指针，而且是内联的，那么我们就将bucket类型标记为不包含指针。
 	// 这样就避免了对这类map的扫描。
 	// 然而，bmap.overflow 是一个指针。为了防止溢出桶被gc处理
 	// 我们在hmap.extra.overflow和hmap.extra.oldoverflow中存储所有溢出桶的指针。
 	// overflow和oldoverflow只在key和value不包含指针的情况下使用
	// 存储一个已经创建好了但是暂未使用的空bmap溢出桶
	overflow    *[]*bmap
	oldoverflow *[]*bmap

	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap
}

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

// map.go里很多函数的第1个入参是这个结构，从成员来看很明显，此结构标示了键值对和桶的大小等必要信息
// 有了这个结构的信息，map.go的代码就可以与键值对的具体数据类型解耦
// 所以map.go用内存偏移量和unsafe.Pointer指针来直接对内存进行存取，而无需关心key或value的具体类型
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     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
3
4
5

hash := map[string]int{
	"1": 2,
	"3": 4,
	"5": 6,
}

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

func maplit(n *Node, m*Node, init *Nodes) {
	a := nod(OMAKE, nil, nil)
	a.Esc = n.Esc
	a.List.Set2(typenod(n.Type), nodintconst(int64(n.List.Len())))
	litas(m, a, init)

	entries := n.List.Slice()
	if len(entries) > 25 {
		...
		return
	}

	// Build list of var[c] = expr.
	// Use temporaries so that mapassign1 can have addressable key, elem.
	...
}

1
2
3
4

hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6

1
2
3
4
5
6

hash := make(map[string]int, 26)
vstatk := []string{"1", "2", "3", ... ， "26"}
vstatv := []int{1, 2, 3, ... , 26}
for i := 0; i < len(vstak); i++ {
    hash[vstatk[i]] = vstatv[i]
}

1
2
3
4
5
6

ageMp := make(map[string]int)
// 指定 map 长度
ageMp := make(map[string]int, 8)

// ageMp 为 nil，不能向其添加元素，会直接panic
var ageMp map[string]int

1
2
3
4
5
6
7
8

// makemap_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()
	return h
}

 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

// 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.
// 传入的三个参数分别为
// 1.map的类型即 key和value的类型信息等其他数据
// 2.长度 即 make 传入的len
// 3.hmap结构体 可以为nil
// 返回值为经过处理的 *hmap
func makemap(t *maptype, hint int, h *hmap) *hmap {
	// 校验一下需求的长度和类型占用字节数的乘积
  	// 是否超过内存限制
	mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
	if overflow || mem > maxAlloc {
		hint = 0
	}

	// initialize Hmap
	// 创建一个新的 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.
	// 找到一个 B，使得 map 的装载因子在正常范围内
	B := uint8(0)
	// 通过输入的长度 算出一个合适的B值
	for overLoadFactor(hint, B) {
		B++
	}
	h.B = B

	// 初始化 hash table
	// 如果 B 等于 0，那么 buckets 就会在赋值的时候再分配
	// 如果长度比较大，分配内存会花费长一点
	// 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.
	// 如果B不为0
	if h.B != 0 {
		var nextOverflow *bmap
		// 调用makeBucketArray 返回一个溢出bmap和开辟完内存的桶的首地址指针
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
		// 如果有溢出bmap
		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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow*bmap) {
	// 求出需要桶的个数 即返回 1<<B的值
	base := bucketShift(b)
	nbuckets := base
	// 如果需要的桶的个数小于4个 那么就不需要创建溢出bmap
  	// 为的是防止有可能不需要bmap的时候却创建了bmap
  	// 使其降低资源开销
	if b >= 4 {
		// 创建的溢出bmap的数量是1<<（B-4）个
    		// 获得所需的桶与溢出bmap的数量
		nbuckets += bucketShift(b - 4)
		// 计算类型 占用字节数 * 所需的桶与溢出bmap的数量的乘积
		sz := t.bucket.size * nbuckets
		// 获取对应长度的内存块的大小
		up := roundupsize(sz)
		if up != sz {
			nbuckets = up / t.bucket.size
		}
	}
	// 分配一个nbuckets 长度的bmap数组 返回首指针
    	// 正常情况下桶和溢出bmap是连续的
    	// 但是当溢出bmap过多的时候每次通过runtime.newobject申请的bmap
    	// 与最初创建的不一定是连续的了
	buckets = newarray(t.bucket, int(nbuckets))
	// 如果创建了溢出bmap
	if base != nbuckets {
	// 这里取巧了一点，预先分配的溢出桶的overflow都是nil,我们要想知道哪个溢出桶是
        // 最后一个，必须得给个标记，这里将last.overflow = buckets进行赋值，方便
        // 在分配overflow的时候能够高效的知道已经到了溢出桶的尾部。
	// 如果有溢出桶
    	// 就把溢出bmap设置为申请的bmap数组的 nbuckets-base处的那个当作空闲溢出bmap
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
		last.setoverflow(t, (*bmap)(buckets))
	}
	return buckets, nextOverflow
}

 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

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
}

func initAlgAES() {
	useAeshash = true
	// Initialize with random data so hash collisions will be hard to engineer.
	getRandomData(aeskeysched[:])
}

1

10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

1
2

v     := hash[key] // => v     := *mapaccess1(maptype, hash, &key)
v, ok := hash[key] // => v, ok := mapaccess2(maptype, hash, &key)

  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

// mapaccess1 returns a pointer to h[key].  Never returns nil, instead
// it will return a reference to the zero object for the elem 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 {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		pc := funcPC(mapaccess1)
		racereadpc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled && h != nil {
		msanread(key, t.key.size)
	}
	// map为空或者元素数量为0时快速返回
	// 如果 h 什么都没有，返回零值
	if h == nil || h.count == 0 {
		// 同写入
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
		return unsafe.Pointer(&zeroVal[0])
	}
	// 写和读冲突
	// 在这里做并发判断，检测到并发写时，抛异常
	// 注意：go map的并发检测是伪检测，并不保证所有的并发都会被检测出来。而且这玩意是在运行期检测。
	// 所以对map有并发要求时，应使用sync.map来代替普通map，通过加锁来阻断并发冲突
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	// 计算哈希值，并且加入 hash0 引入随机性
	hash := t.hasher(key, uintptr(h.hash0))
	// 比如 B=5，那 m 就是31，二进制是全 1
	// 求 bucket num 时，将 hash 与 m 相与，
	// 达到 bucket num 由 hash 的低 8 位决定的效果
	m := bucketMask(h.B)
	// b 就是 bucket 的地址
	b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
	// oldbuckets 不为 nil，说明发生了扩容
	if c := h.oldbuckets; c != nil {
		// 如果不是同 size 扩容（看后面扩容的内容）
	    	// 对应条件 1 的解决方案
		if !h.sameSizeGrow() {
			// There used to be half as many buckets; mask down one more power of two.
			// 新 bucket 数量是老的 2 倍
			m >>= 1
		}
		// 求出 key 在老的 map 中的 bucket 位置
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
		// 如果 oldb 没有搬迁到新的 bucket
		// 那就在老的 bucket 中寻找
		if !evacuated(oldb) {
			// 处于扩容过程中，应该从oldbuckets中去获取数据
			b = oldb
		}
	}
	// 计算出高 8 位的 hash
	// 相当于右移 56 位，只取高8位
	top := tophash(hash)
bucketloop:
	// 遍历桶和其溢出桶
	for ; b != nil; b = b.overflow(t) {
		//遍历桶的tophash
		for i := uintptr(0); i < bucketCnt; i++ {
			 // tophash 不匹配，继续
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					// 提前返回，emptyRest表示在它之后不会存在非空值
					// 当前bucket内找完（还没找到），继续到 overflow bucket 里找
					break bucketloop
				}
				continue
			}
			// tophash 匹配，定位到 key 的位置
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			// key 是指针
			if t.indirectkey() {
				// 解引用
				k = *((*unsafe.Pointer)(k))
			}
			// 如果 key 相等
			// 防止仅top位相同的hash冲突
			if t.key.equal(key, k) {
				// 定位到 value 的位置
				e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				// value 解引用
				if t.indirectelem() {
					e = *((*unsafe.Pointer)(e))
				}
				return e
			}
		}
	}
	// overflow bucket 也找完了，说明没有目标 key
	// 返回零值
	return unsafe.Pointer(&zeroVal[0])
}
// bucketMask returns 1<<b - 1, optimized for code generation.
func bucketMask(b uint8) uintptr {
	return bucketShift(b) - 1
}
// bucketShift returns 1<<b, optimized for code generation.
func bucketShift(b uint8) uintptr {
	// Masking the shift amount allows overflow checks to be elided.
	return uintptr(1) << (b & (sys.PtrSize*8 - 1))
}
func (b *bmap) overflow(t *maptype) *bmap {
	return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize))
}

1
2
3
4
5

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

// value 定位公式
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))

1
2
3
4

dataOffset = unsafe.Offsetof(struct {
		b bmap
		v int64
	}{}.v)

1

b = b.overflow(t)

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

	// Possible tophash values. We reserve a few possibilities for special marks.
	// Each bucket (including its overflow buckets, if any) will have either all or none of its
	// entries in the evacuated* states (except during the evacuate() method, which only happens
	// during map writes and thus no one else can observe the map during that time).
	// tophash对应的位置为空，并且后续没有非空的值
	emptyRest      = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows.
	// tophash对应的位置为空，元素被删除后可能的标记值
	emptyOne       = 1 // this cell is empty
	// key/value是无效的，值被迁移到新table的前半段
	evacuatedX     = 2 // key/elem is valid.  Entry has been evacuated to first half of larger table.
	// key/value是无效的，值被迁移到新table的后半段
	evacuatedY     = 3 // same as above, but evacuated to second half of larger table.
	// tophash对应的值为空，但是表示正在迁移中
	evacuatedEmpty = 4 // cell is empty, bucket is evacuated.
	// 一个临界值，前面所有的值都代表一个特殊的含义，所以当top<5时，top+=5
	minTopHash     = 5 // minimum tophash for a normal filled cell.

1
2
3
4

func evacuated(b *bmap) bool {
	h := b.tophash[0]
	return h > emptyOne && h < minTopHash
}

 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

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		pc := funcPC(mapaccess2)
		racereadpc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled && h != nil {
		msanread(key, t.key.size)
	}
	if h == nil || h.count == 0 {
		if t.hashMightPanic() {
			t.hasher(key, 0) // see issue 23734
		}
		return unsafe.Pointer(&zeroVal[0]), false
	}
	if h.flags&hashWriting != 0 {
		throw("concurrent map read and map write")
	}
	hash := t.hasher(key, uintptr(h.hash0))
	m := bucketMask(h.B)
	b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
	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)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
		if !evacuated(oldb) {
			b = oldb
		}
	}
	top := tophash(hash)
bucketloop:
	for ; b != nil; b = b.overflow(t) {
		for i := uintptr(0); i < bucketCnt; i++ {
			if b.tophash[i] != top {
				if b.tophash[i] == emptyRest {
					break bucketloop
				}
				continue
			}
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if 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, true
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0]), false
}

  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
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211

// Like mapaccess, but allocates a slot for the key if it is not present in the map.
// 该函数传入的参数分别为
// 1.map的类型即 key和value的类型信息等其他数据
// 2.那个map
// 3.key所在内存的地址
// 返回的参数为
// 1.找到的可用的可存储value的内存地址
// 返回后具体的赋值操作由汇编完成
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	//判断 hmap 是否已经初始化（是否为 nil）
	if h == nil {
		panic(plainError("assignment to entry in nil map"))
	}
	if raceenabled {
		callerpc := getcallerpc()
		pc := funcPC(mapassign)
		racewritepc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled {
		msanread(key, t.key.size)
	}
	//判断是否并发读写 map，若是则抛出异常
	if h.flags&hashWriting != 0 {
		throw("concurrent map writes")
	}
	// 求出这个key的哈希值
	hash := t.hasher(key, uintptr(h.hash0))
	// 函数首先会检查 map 的标志位 flags。如果 flags 的写标志位此时被置 1 了，说明有其他协程在执行“写”操作，进而导致程序 panic。这也说明了 map 对协程是不安全的。
	// Set hashWriting after calling t.hasher, since t.hasher may panic,
	// in which case we have not actually done a write.
	// 设置 flags 标志位，表示有一个 goroutine 正在写入数据。因为 alg.hash 有可能出现 panic 导致异常
	h.flags ^= hashWriting
	// 判断 buckets 是否为 nil，若是则调用 newobject 根据当前 bucket 大小进行分配
    	// 初始化时没有初始 buckets，那么它在第一次赋值时就会对 buckets 分配
	// 懒初始化，在前面初始化map时，B为0，桶数组放到这里来进行初始化
	if h.buckets == nil {
		h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
	}
	// 首先是函数会根据传入的键拿到对应的哈希和桶：
again:
	// 根据低八位计算得到 bucket 的内存地址
	// 算出这个key应该落到哪个bmap里
	bucket := hash & bucketMask(h.B)
	// 如果 map 处在扩容的过程中，那么当 key 定位到了某个 bucket 后，需要确保这个 bucket 对应的老 bucket 完成了迁移过程。即老 bucket 里的 key 都要迁移到新的 bucket 中来（分裂到 2 个新 bucket），才能在新的 bucket 中进行插入或者更新的操作。
	// 只有进行完了这个搬迁操作后，我们才能放心地在新 bucket 里定位 key 要安置的地址，再进行之后的操作。
	// 判断是否处于搬迁桶的状态
  	// 如果处于该状态则进行旧桶 -> 新桶的搬迁
	if h.growing() {
		growWork(t, h, bucket)
	}
	// 通过位移操作获得 bucket := hash & bucketMask(h.B) 这个桶的对象
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
	// 计算出key的哈希值之后的高8位哈希值
	top := tophash(hash)
	// 然后通过遍历比较桶中存储的 tophash 和键的哈希，如果找到了相同结果就会返回目标位置的地址。
	// 准备两个指针，一个（inserti）指向 key 的 hash 值在 tophash 数组所处的位置，另一个(insertk)指向 cell 的位置（也就是 key 最终放置的地址），当然，对应 value 的位置就很容易定位出来了。这三者实际上都是关联的，在 tophash 数组中的索引位置决定了 key 在整个 bucket 中的位置（共 8 个 key），而 value 的位置需要“跨过” 8 个 key 的长度。
	// 元素在bmap中tophash数组的地址
	var inserti *uint8
	// key的地址
	var insertk unsafe.Pointer
	// value 的地址
	var elem unsafe.Pointer
bucketloop:
	// for 循环会依次遍历正常桶和溢出桶中存储的数据，整个过程会分别判断 tophash 是否相等、key 是否相等，遍历结束后会从循环中跳出。
	for {
		// 遍历当前选中的bmap
		// 迭代 buckets 中的每一个 bucket（共 8 个）
		for i := uintptr(0); i < bucketCnt; i++ {
			// 对比 bucket.tophash 与 top（高八位）是否一致
			if b.tophash[i] != top {
				// 在循环的过程中，inserti 和 insertk 分别指向第一个找到的空闲的 cell。如果之后在 map 没有找到 key 的存在，也就是说原来 map 中没有此 key，这意味着插入新 key。那最终 key 的安置地址就是第一次发现的“空位”（tophash 是 empty）。
				// 若不一致，判断是否为空槽
				if isEmpty(b.tophash[i]) && inserti == nil {
					// 记录tophash中最早一次出现empty的情况，这里不一定是emptyRest，有可能是删除数据时的emptyOne状态
					inserti = &b.tophash[i]
					insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
					// 把该位置标识为可插入 tophash 位置,这里就是第一个可以插入数据的地方
					elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
				}
				// 如果 b.tophash[i] == emptyRest
        			// 代表后续的b.tophash没有 溢出bmap或者可遍历的b.tophash了
				if b.tophash[i] == emptyRest {
					// 跳出循环
					break bucketloop
				}
				continue
			}
			// 若是匹配（也就是原本已经存在），则进行更新。最后跳出并返回 value 的内存地址
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
			if t.indirectkey() {
				k = *((*unsafe.Pointer)(k))
			}
			// 计算当前k与传进来的key是否相等，有可能只是高位相等，则需要继续循环
			if !t.key.equal(key, k) {
				continue
			}
			// already have a mapping for key. Update it.
			// 如果相等那么就代表是更新操作
      			// 先把传入的key的赋值到k处
			if t.needkeyupdate() {
				typedmemmove(t.key, k, key)
			}
			// 计算出k对应value的地址
			elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
			// 直接跳转到结束
			goto done
		}
		// 判断是否迭代完毕，若是则结束迭代 buckets 并更新当前桶位置
		// 当前桶已经没有存储数据的位置了，则需要从overflow溢出桶中查询位置
		// 获取溢出bmap
    		// 代表在当前bmap里面么得找到可用的地址
		ovf := b.overflow(t)
		// 没有溢出bmap就跳出
		if ovf == nil {
			break
		}
		// 继续循环
		b = ovf
	}
	// 如果没找到可用的插槽，那么就创建一个
  	// 判断是否需要扩容
  	// 扩容条件为：
  	// 1.当装载因子>=6.5
  	// 2.溢出bmap过多
  	// 第二种情况只会出现在先大量的写然后再大量删除的情况
	// 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.
	// 在正式安置 key 之前，还要检查 map 的状态，看它是否需要进行扩容。如果满足扩容的条件，就主动触发一次扩容操作。
	// 这之后，整个之前的查找定位 key 的过程，还得再重新走一次。因为扩容之后，key 的分布都发生了变化。
	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
	}
	// 所有的当前桶都是满的，需要构建一个新的溢出桶
	// 如果这个 bucket 的 8 个 key 都已经放置满了，那在跳出循环后，发现 inserti 和 insertk 都是空，这时候需要在 bucket 后面挂上 overflow bucket.哈希会调用 runtime.hmap.newoverflow 创建新桶或者使用 runtime.hmap 预先在 noverflow 中创建好的桶来保存数据，新创建的桶不仅会被追加到已有桶的末尾，还会增加哈希表的 noverflow 计数器。
	// 经过前面迭代寻找动作，若没有找到可插入的位置，意味着当前的所有桶都满了，将重新分配一个新溢出桶用于插入动作。最后再在上一步申请的新插入位置，存储键值对，返回该值的内存地址
	if inserti == nil {
		// The current bucket and all the overflow buckets connected to it are full, allocate a new one.
		newb := h.newoverflow(t, b)
		inserti = &newb.tophash[0]
		insertk = add(unsafe.Pointer(newb), dataOffset)
		elem = add(insertk, bucketCnt*uintptr(t.keysize))
	}
	// 将新key/elem存储在插入位置
	// store new key/elem at insert position
	// 最后，会更新 map 相关的值，如果是插入新 key，map 的元素数量字段 count 值会加 1；在函数之初设置的 hashWriting 写标志出会清零。
	if t.indirectkey() {
		kmem := newobject(t.key)
		*(*unsafe.Pointer)(insertk) = kmem
		insertk = kmem
	}
	//引用类型分配value所需空间，同时把value在槽中对应的位置指向这个空间
	if t.indirectelem() {
		vmem := newobject(t.elem)
		*(*unsafe.Pointer)(elem) = vmem
	}
	//将key写入刚分配的空间
	typedmemmove(t.key, insertk, key)
	//更新标记位
	*inserti = top
	//元素个数+1
	h.count++

done:
	// 再次校验并发写
	if h.flags&hashWriting == 0 {
		// 并发的写，标记在上面通过h.flags ^= hashWriting设置
		throw("concurrent map writes")
	}
	// 取消并发写的标记
	h.flags &^= hashWriting
	if t.indirectelem() {
		elem = *((*unsafe.Pointer)(elem))
	}
	// 返回可用的value 存放地址
  	// 随后的赋值操作会在汇编中进行
	return elem
}

func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
	var ovf *bmap
	if h.extra != nil && h.extra.nextOverflow != nil {
		// We have preallocated overflow buckets available.
		// See makeBucketArray for more details.
		ovf = h.extra.nextOverflow
		if ovf.overflow(t) == nil {
			// We're not at the end of the preallocated overflow buckets. Bump the pointer.
			h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
		} else {
			// This is the last preallocated overflow bucket.
			// Reset the overflow pointer on this bucket,
			// which was set to a non-nil sentinel value.
			ovf.setoverflow(t, nil)
			h.extra.nextOverflow = nil
		}
	} else {
		ovf = (*bmap)(newobject(t.bucket))
	}
	h.incrnoverflow()
	if t.bucket.ptrdata == 0 {
		h.createOverflow()
		*h.extra.overflow = append(*h.extra.overflow, ovf)
	}
	b.setoverflow(t, ovf)
	return ovf
}

1
2
3
4

00018 (+5) CALL runtime.mapassign_fast64(SB)
00020 (5) MOVQ 24(SP), DI               ;; DI = &value
00026 (5) LEAQ go.string."88"(SB), AX   ;; AX = &"88"
00027 (5) MOVQ AX, (DI)                 ;; *DI = AX

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

func walkexpr(n *Node, init*Nodes) *Node {
	switch n.Op {
	case ODELETE:
		init.AppendNodes(&n.Ninit)
		map_ := n.List.First()
		key := n.List.Second()
		map_ = walkexpr(map_, init)
		key = walkexpr(key, init)

		t := map_.Type
		fast := mapfast(t)
		if fast == mapslow {
			key = nod(OADDR, key, nil)
		}
		n = mkcall1(mapfndel(mapdelete[fast], t), nil, init, typename(t), map_, key)
	}
}

  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

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
	if raceenabled && h != nil {
		callerpc := getcallerpc()
		pc := funcPC(mapdelete)
		racewritepc(unsafe.Pointer(h), callerpc, pc)
		raceReadObjectPC(t.key, key, callerpc, pc)
	}
	if msanenabled && h != nil {
		msanread(key, t.key.size)
	}
	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")
	}

	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)
	// 计算 key 的哈希，找到落入的 bucket。检查此 map 如果正在扩容的过程中，直接触发一次搬迁操作。
	if h.growing() {
		// 进行扩容
		growWork(t, h, bucket)
	}
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
	bOrig := b
	top := tophash(hash)
search:
	// 删除操作同样是两层循环，核心还是找到 key 的具体位置。寻找过程都是类似的，在 bucket 中挨个 cell 寻找。
	// 找到对应位置后，对 key 或者 value 进行“清零”操作：
	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
			// 对 key 清零
			if t.indirectkey() {
				k2 = *((*unsafe.Pointer)(k2))
			}
			if !t.key.equal(key, k2) {
				continue
			}
			// Only clear key if there are pointers in it.
			// 对 value 清零
			// key是指针的需要置空，方便GC
			if t.indirectkey() {
				*(*unsafe.Pointer)(k) = nil
			} else if t.key.ptrdata != 0 {
				memclrHasPointers(k, t.key.size)
			}
			e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
			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 {
				// 如果是该tophash的最后一个，则需要判断overflow中tophash的第一位是否是emptyRest
				if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
					goto notLast
				}
			} else {
				// 如果不是当前tophash的最后一个，则直接判断当前tophash的下一个是否是emptyRest
				if b.tophash[i+1] != emptyRest {
					goto notLast
				}
			}
			// 当前值之后不存在其他的数据，则置为emptyRest
             		// 需要把该位置之前除非空之外的所有emptyOne位置也置为emptyRest
			for {
				// 将对应位置的 tophash 值置成 Empty
				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:
			// 最后，将 count 值减 1。
			h.count--
			// Reset the hash seed to make it more difficult for attackers to
			// repeatedly trigger hash collisions. See issue 25237.
			if h.count == 0 {
				h.hash0 = fastrand()
			}
			break search
		}
	}
	// 抛出并发修改异常
	if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
	}
	h.flags &^= hashWriting
}

1

loadFactor := count / (2^B)

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

// overLoadFactor reports whether count items placed in 1<<B buckets is over loadFactor.
// 装载因子超过 6.5
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.
// overflow buckets 太多
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
52
53
54
55
56
57
58
59
60
61
62
63
64

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.
	// 需要扩容多少bmap
  	// 默认为翻倍扩容
  	// 此情况为装载因子>=6.5
	// B+1 相当于是原来 2 倍的空间
	bigger := uint8(1)
	// 对应条件 2
	if !overLoadFactor(h.count+1, h.B) {
		// 这里表示是溢出桶数量数量过多，但是map中元素数量还达不到过载，则无需增长桶数量
        	// 分配一个与之前一样的即可，将所有数据摊平，减少溢出桶的数量
		// 进行等量的内存扩容，所以 B 不变
		bigger = 0
		h.flags |= sameSizeGrow
	}
	// 将老 buckets 挂到 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
	// overflow buckets 数为 0
	h.noverflow = 0
	// 如果之前有溢出bmap的话，把原来所持有的溢出bmap也变成旧的溢出bmap
	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
	}
	// 如果扩容的新bmap列表存在可用溢出bmap
  	// 那就设置一下
	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().
	// 此处没有发现扩容时的数据搬迁（从旧bmap中拷贝原数据到新的bmap中）工作
 	// 因为哈希表数据的实际复制是由growWork()和evacuate()逐步完成的。
  	// 这两个函数的触发时机是在写/删除操作时触发
}