04.Golang Map源码分析（二、基础操作之初始化、读取、删除）

Golang Map源码分析（二、基础操作之初始化、读取、写入、删除）

注意当前go版本代码为1.23

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
// A header for a Go map.
type hmap struct {
        // Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
        // Make sure this stays in sync with the compiler's definition.

        // count: map 中实际存储的键值对数量。
        // 必须是 hmap 结构体的第一个字段，因为内置函数 len() 会直接读取该字段。
        count int

        // flags: 用于存储 map 的状态标志，例如是否正在进行迭代、是否正在进行等量扩容等。
        flags uint8

        // B: buckets 数组大小的以 2 为底的对数。
        // 例如，B=5 表示 buckets 数组的大小为 2^5 = 32。
        // map 最多可以存储 loadFactor * 2^B 个键值对，loadFactor 是负载因子，默认为 6.5。
        B uint8

        // noverflow: 溢出桶的大致数量。
        // 这是一个近似值，因为在并发访问 map 时，noverflow 的更新可能会有延迟。
        // 详细的更新机制可以参考 incrnoverflow 函数的实现。
        noverflow uint16

        // hash0: 哈希种子，用于随机化键的哈希值。
        // 在创建 map 时，会生成一个随机的 hash0 值，用于防止哈希碰撞攻击。
        hash0 uint32


        // buckets: 指向 buckets 数组的指针。 buckets 数组的大小为 2^B。
        // 如果 count 为 0，则 buckets 可能为 nil。
        // 每个 bucket 存储多个键值对，具体数量由 bucketCnt 常量决定，通常为 8。
        buckets unsafe.Pointer

        // oldbuckets: 指向旧 buckets 数组的指针。
        // 仅在 map 扩容时使用。旧 buckets 数组的大小是新 buckets 数组的一半。
        // 在渐进式扩容过程中，键值对会逐渐从 oldbuckets 迁移到 buckets。
        oldbuckets unsafe.Pointer

        // nevacuate: 渐进式扩容的进度计数器。
        // 表示已经完成迁移的 buckets 数量。
        // buckets 数组中索引小于 nevacuate 的 bucket 都已经迁移到了新的 buckets 数组。
        nevacuate uintptr


        // extra: 指向 mapextra 结构体的指针，其中包含溢出桶和其他一些字段。
        // 如果没有溢出桶，则 extra 可能为 nil。
    	// extra.overflow：保存溢出桶链表
		// extra.oldoverflow：保存旧溢出桶链表
		// extra.nextOverflow：下一个空闲溢出桶地址
        extra *mapextra
}

上一篇文章我们介绍了map的结构与实现，接下来我们看看map的基础操作是如何实现的吧

基础操作

初始化

从语法层面上来说，创建 map 很简单：

1
2
3
4
5
6
7
8
9
10
11
12
mp := make(map[string]int)
// 指定长度
mp := make(map[string]int, 8)

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

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

通过汇编语言可以看到，实际上底层调用的是 makemap 函数，主要做的工作就是初始化 hmap 结构体的各种字段，例如计算 B 的大小，设置哈希种子 hash0 等等。

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
// makemap 函数实现了 Go 语言中 `make(map[k]v, hint)` 创建 map 的操作。
// 如果编译器确定 map 或第一个桶可以在栈上创建，那么 h 和/或 bucket 可能不为 nil。
// 如果 h 不为 nil，则可以直接在 h 中创建 map。
// 如果 h.buckets 不为 nil，则指向的 bucket 可以用作第一个桶。
func makemap(t *maptype, hint int, h *hmap) *hmap {
	// 计算 hint 个元素所需的内存大小，并检查是否溢出或超过最大分配限制。
	mem, overflow := math.MulUintptr(uintptr(hint), t.Bucket.Size_)
	if overflow || mem > maxAlloc {
		hint = 0 // 如果溢出或超过限制，将 hint 设置为 0。
	}

	// 初始化 Hmap
	if h == nil {
		h = new(hmap) // 如果 h 为 nil，则创建一个新的 hmap。
	}
	h.hash0 = uint32(rand()) // 生成一个随机的 hash0 值。

	// 找到合适的 B 值，它决定了 map 可以容纳的元素数量。
	// 当 hint < 0 时，overLoadFactor 返回 false，因为 hint < bucketCnt。
	B := uint8(0)
	for overLoadFactor(hint, B) { // 循环直到找到合适的 B 值。
		B++
	}
	h.B = B // 将 B 值存储到 hmap 中。

	// 分配初始的哈希表
	// 如果 B == 0，buckets 字段会在后续 (mapassign) 中延迟分配。
	// 如果 hint 很大，将这块内存清零可能会花费一些时间。
	if h.B != 0 {
		var nextOverflow *bmap
		h.buckets, nextOverflow = makeBucketArray(t, h.B, nil) // 创建桶数组。
		if nextOverflow != nil {
			h.extra = new(mapextra)             // 如果有溢出桶，则创建 mapextra。
			h.extra.nextOverflow = nextOverflow // 设置 nextOverflow。
		}
	}

	return h // 返回创建的 hmap。
}




// makeBucketArray 函数初始化 map 桶的底层数组。
//
// 参数：
//   t: map的类型信息。
//   b: 桶数组的级别，用于计算桶的数量。桶的数量大致为 2^b。
//   dirtyalloc: 可选的预分配内存块，如果非空，则会重用该内存块。
// 返回值：
//   buckets: 指向新桶数组的指针。
//   nextOverflow: 指向下一个可用的溢出桶的指针，如果不需要溢出桶，则为 nil。
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
	// 计算桶的基本数量，即 2^b。
	base := bucketShift(b)

	// 初始化桶的数量为基本数量。
	nbuckets := base

	// 对于较小的 b 值，溢出桶不太可能出现。
	// 为了避免计算的开销，直接使用基本数量的桶。
	if b >= 4 {
		// 添加估计需要的溢出桶的数量，
		// 用于插入此 b 值对应的元素数量的中位数。
		// 这里使用 b-4 是一个经验值，用于估计溢出桶的数量。
		nbuckets += bucketShift(b - 4)

		// 计算桶数组的总大小（字节）。
		sz := t.Bucket.Size_ * nbuckets

		// 对桶数组的大小进行向上取整，以确保内存对齐。
		// !t.Bucket.Pointers() 用于判断桶是否包含指针。
		// 如果桶包含指针，则向上取整到指针大小的倍数；否则向上取整到 8 字节的倍数。
		up := roundupsize(sz, !t.Bucket.Pointers())

		// 如果向上取整后的值与原始值不同，则更新桶的数量。
		if up != sz {
			nbuckets = up / t.Bucket.Size_
		}
	}

	// 如果没有提供预分配的内存块，则分配一个新的内存块。
	if dirtyalloc == nil {
		buckets = newarray(t.Bucket, int(nbuckets))
	} else {
		// 重用预分配的内存块 dirtyalloc。
		// dirtyalloc 之前由 newarray(t.Bucket, int(nbuckets)) 生成，
		// 但可能不为空，因此需要清空。
		buckets = dirtyalloc

		// 计算桶数组的总大小（字节）。
		size := t.Bucket.Size_ * nbuckets

		// 根据桶是否包含指针，使用不同的清空函数。
		if t.Bucket.Pointers() {
			// 如果桶包含指针，则使用 memclrHasPointers 清空内存，
			// 并将指针置为 nil，避免潜在的内存问题。
			memclrHasPointers(buckets, size)
		} else {
			// 如果桶不包含指针，则使用 memclrNoHeapPointers 清空内存。
			memclrNoHeapPointers(buckets, size)
		}
	}

	// 如果预分配了溢出桶，则设置 nextOverflow 指针和溢出桶的链接。
	if base != nbuckets {
		// 我们预分配了一些溢出桶。
		// 为了尽量减少跟踪这些溢出桶的开销，
		// 我们使用以下约定：如果预分配的溢出桶的 overflow 指针为 nil，
		// 则可以通过递增指针获得更多可用的溢出桶。
		// 最后一个溢出桶需要一个安全的非 nil 指针；这里使用 buckets。

		// nextOverflow 指向第一个溢出桶。
		nextOverflow = (*bmap)(add(buckets, base*uintptr(t.BucketSize)))

		// last 指向最后一个溢出桶。
		last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.BucketSize)))

		// 将最后一个溢出桶的 overflow 指针设置为指向 buckets，
		// 形成一个循环链表，方便后续分配溢出桶。
		last.setoverflow(t, (*bmap)(buckets))
	}

	// 返回桶数组指针和下一个可用的溢出桶指针。
	return buckets, nextOverflow
}

hint 和 b（在代码中为 B）的意义如下：

  • hint (int): hint 参数表示 map 预期的元素个数。它作为创建 map 的初始容量的参考。makemap 函数会根据 hint 的值来确定初始桶的数量和大小，以尽量减少后续的扩容操作，提高性能。 需要注意的是，hint 只是一个建议值，Go 运行时并不保证最终创建的 map 的容量与 hint 完全一致。如果 hint 的值过大或者计算过程中发生溢出，hint 会被重置为 0。
  • B (uint8): B 决定了 map 的桶数组的大小。桶数组的大小为 2 的 B 次方。B 值越大，桶数组越大，可以容纳的元素越多，但同时也会占用更多的内存。B 的值是通过 overLoadFactor 函数计算得出的，该函数会根据 hint 值和当前的 B 值判断是否需要增加 B 的值。makemap 函数会不断增加 B 的值，直到找到一个合适的 B 值，使得 map 能够容纳 hint 个元素，并且负载因子不会过高。

makemap 函数的目标是创建一个合适的哈希表，以存储用户指定数量的元素。为了实现这个目标，它需要确定两个关键参数：

  1. 桶的数量： 桶的数量越多，哈希冲突的概率就越小，但同时也会占用更多的内存。
  2. 桶的大小： 每个桶可以存储多个键值对。桶越大，可以存储的键值对越多，但查找效率会降低。

hint 参数用于指导 makemap 函数确定桶的数量。makemap 函数会根据 hint 的值计算出一个合适的 B 值，然后使用 2 的 B 次方作为桶的数量。

overLoadFactor 函数用于判断当前的 B 值是否足够大。如果 hint 除以 2 的 B 次方（即桶的数量）的结果大于一个预定的负载因子，则说明当前的 B 值不够大，需要继续增加。

通过这种方式，makemap 函数可以根据 hint 的值动态地调整桶的数量，以确保 map 具有合适的容量和性能。

总而言之，hint 提供了一个创建 map 的容量建议，而 B 是 makemap 函数根据 hint 计算得出的一个内部参数，它决定了 map 底层桶数组的大小，从而影响 map 的性能和内存占用。

读取

上一篇文章《Golang Map源码分析（一、定义与实现原理）》已经提到过key定位过程，其实就是get操作的主要逻辑，总而言之， map get 的过程就是：前置检查 -> 计算哈希值 -> 定位桶 -> 遍历桶内条目 -> 比较 tophash 和 key -> 返回 value 指针 (或零值指针)。

主要源码如下 runtime.mapaccess1

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
// mapaccess1 返回一个指向 h[key] 的指针。永远不会返回 nil，
// 如果 key 不在地图中，它将返回一个指向 elem 类型零值的引用。
// 注意：返回的指针可能会使整个 map 保持活动状态，所以不要长时间持有它。
func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
	//.....
    
	// 处理空 map 或空桶的情况
	if h == nil || h.count == 0 {
		// 如果key不存在，则抛出key错误
		if err := mapKeyError(t, key); err != nil {
			panic(err) // 抛出panic，参见 issue 23734
		}
		// 返回零值的指针
		return unsafe.Pointer(&zeroVal[0])
	}

	// 并发安全检查：检测并发读写
	if h.flags&hashWriting != 0 {
		fatal("concurrent map read and map write") // 如果map正在写入，则抛出panic
	}

	// 计算哈希值，并且加入 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 { // 如果存在旧桶
		if !h.sameSizeGrow() {
			// 如果不是等大小扩容，则需要调整掩码
			m >>= 1
		}
        // 求出 key 在老的 map 中的 bucket 位置
		oldb := (*bmap)(add(c, (hash&m)*uintptr(t.BucketSize))) 
        // 如果 oldb 没有搬迁到新的 bucket
		// 那就在老的 bucket 中寻找
		if !evacuated(oldb) { // 如果旧桶还没有被迁移
			b = oldb // 使用旧桶
		}
	}

	// 计算出高 8 位的 hash
	// 相当于右移 56 位，只取高8位
	top := tophash(hash)

	// 循环遍历桶和溢出桶
bucketloop:
	for ; b != nil; b = b.overflow(t) { // 遍历桶及其溢出桶
		for i := uintptr(0); i < abi.OldMapBucketCount; i++ { // 遍历桶中的所有条目
			if b.tophash[i] != top { // 如果tophash不匹配
				if b.tophash[i] == emptyRest { // 如果是emptyRest，则表示后续桶都为空
					break bucketloop // 退出循环
				}
				continue // 继续下一个条目
			}

			// 计算 key 的地址
			k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
			if t.IndirectKey() { // 如果key是指针
				k = *((*unsafe.Pointer)(k)) // 解引用指针
			}

			// 比较 key 是否相等
			if t.Key.Equal(key, k) { // 使用类型的Equal方法比较key
				// 计算 value 的地址
				e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
				if t.IndirectElem() { // 如果value是指针
					e = *((*unsafe.Pointer)(e)) // 解引用指针
				}
				return e // 返回 value 的指针
			}
		}
	}
	return unsafe.Pointer(&zeroVal[0])
}
//

这里再补充一下get的两种实现方式

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

赋值语句左侧接受参数的个数会决定使用的运行时方法：

  • 当接受一个参数时，会使用 runtime.mapaccess1，该函数仅会返回一个指向目标值的指针；
  • 当接受两个参数时，会使用 runtime.mapaccess2，除了返回目标值之外，它还会返回一个用于表示当前键对应的值是否存在的 bool 值：

另外，根据 key 的不同类型，编译器还会将查找、插入、删除的函数用更具体的函数替换，以优化效率：

key 类型 查找
uint32 mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
uint32 mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool)
uint64 mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
uint64 mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool)
string mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer
string mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool)

这些函数的参数类型直接是具体的 uint32、unt64、string，在函数内部由于提前知晓了 key 的类型，所以内存布局是很清楚的，因此能节省很多操作，提高效率。

删除

源码位置：runtime.mapdelete 。

哈希表的删除逻辑与写入逻辑主要流程很相似

  1. 它首先会检查 h.flags 标志，如果发现写标位是 1，直接 panic，因为这表明有其他协程同时在进行写操作。
  2. 计算 key 的哈希，找到落入的 bucket。如果在删除期间遇到了哈希表的扩容，就会分流桶中的元素进行扩容，分流结束之后会找到桶中的目标元素完成键值对的删除工作。
  3. 找到对应位置后，对 key 或者 value 进行清除操作
  4. 最后，将 count 值减 1，将对应位置的 tophash 值置成 Empty。
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
// 从map中删除对应kv
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    // ...... 其他逻辑
    
	// 如果 map 为空
	if h == nil || h.count == 0 {
		// 检查 key 是否有效，若无效则抛出 panic
		if err := mapKeyError(t, key); err != nil {
			panic(err) // 参见 issue 23734
		}
		return
	}
	// 如果检测到并发写 map
	if h.flags&hashWriting != 0 {
		fatal("concurrent map writes")
	}

	// 使用哈希函数计算 key 的哈希值
	hash := t.Hasher(key, uintptr(h.hash0))

	// 在调用 hasher 后设置 hashWriting 标志，hasher 可能引发 panic
	// 在这种情况下，我们实际上没有执行写（删除）操作
	h.flags ^= hashWriting

	// 计算 bucket 的索引
	bucket := hash & bucketMask(h.B)
	// 如果在删除期间遇到了哈希表的扩容，就会分流桶中的元素，分流结束之后会找到桶中的目标元素完成键值对的删除工作。
	if h.growing() {
		growWork(t, h, bucket)
	}
	// 获取 bucket 地址
	b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
	bOrig := b
	// 获取 hash 的高8位
	top := tophash(hash)
search:
	// 遍历 bucket 链
	for ; b != nil; b = b.overflow(t) {
		// 在 bucket 内查找
		for i := uintptr(0); i < abi.OldMapBucketCount; i++ {
			// 如果 tophash 不匹配
			if b.tophash[i] != top {
				// 如果已经到达 bucket 的末尾
				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
			}
			// 判断key 是否指针， 对 value 清零
			if t.IndirectKey() {
				// 将原 key（是指针）赋为nil
				*(*unsafe.Pointer)(k) = nil
			} else if t.Key.Pointers() {
				// 删除对应key（值）
				memclrHasPointers(k, t.Key.Size_)
			}
			// 计算值的地址并清除值
			e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
            // 判断 value 是否指针，对 value 清零
			if t.IndirectElem() {
				*(*unsafe.Pointer)(e) = nil
			} else if t.Elem.Pointers() {
				memclrHasPointers(e, t.Elem.Size_)
			} else {
				memclrNoHeapPointers(e, t.Elem.Size_)
			}
			// 标记这个槽位为空
			b.tophash[i] = emptyOne
			// 如果 bucket 结束于一系列 emptyOne 状态，将其改为 emptyRest
			// 这里的逻辑是优化 emptyOne 到 emptyRest 的转换
			if i == abi.OldMapBucketCount-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 // 回到初始 bucket，我们完成了
					}
					// 找到前一个 bucket，继续在其最后一个条目
					c := b
					for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
					}
					i = abi.OldMapBucketCount - 1
				} else {
					i--
				}
				if b.tophash[i] != emptyOne {
					break
				}
			}
		notLast:
			// 减少 map 中的元素计数
			h.count--
			// 如果 map 为空，重新设置哈希种子以防攻击者触发哈希碰撞
			if h.count == 0 {
				h.hash0 = uint32(rand())
			}
			break search
		}
	}

	// 确保没有并发的写操作
	if h.flags&hashWriting == 0 {
		fatal("concurrent map writes")
	}
	// 清除 hashWriting 标志
	h.flags &^= hashWriting
}

问题

可以对 map 的元素取地址吗

无法对 map 的 key 或 value 进行取址。以下代码不能通过编译：

1
2
3
4
5
6
7
8
9
package main

import "fmt"

func main() {
	m := make(map[string]int)

	fmt.Println(&m["test"])
}

编译报错：

1
./main.go:8:14: cannot take the address of m["qcrao"]

如果通过其他 hack 的方式，例如 unsafe.Pointer 等获取到了 key 或 value 的地址，也不能长期持有，因为一旦发生扩容，key 和 value 的位置就会改变，之前保存的地址也就失效了。

map 是线程安全的吗

map 不是线程安全的。

在查找、赋值、遍历、删除的过程中都会检测写标志，一旦发现写标志置位（等于1），则直接 panic。赋值和删除函数在检测完写标志是复位之后，先将写标志位置位，才会进行之后的操作。

1
2
3
4
// 检测写标志：
if h.flags&hashWriting == 0 {
		throw("concurrent map writes")
}
1
2
// 设置写标志：
h.flags |= hashWriting

参考链接

1.Go 程序员面试笔试宝典

2.《Go学习笔记》

3.Go 语言设计与实现

Golang
#原创 #编程语言 #Golang #源码分析
04.Golang Map源码分析（二、基础操作之初始化、读取、删除）
https://blog.longpi1.com/2024/11/25/04-Golang-Map源码分析（二、基础操作之初始化、读取、删除）/