03.Golang Map源码分析（一、定义与实现原理）

Golang Map源码分析（一、定义与实现原理）

注意当前go版本代码为1.23

在go目录文件命名时我们会经常看见swiss和no_swiss的后缀，在 Go 语言的源码中，swiss 和 no_swiss 是与 map 实现相关的两种不同的优化策略或机制。它们主要用于处理 map 中键值对的存储和查找优化。以下是它们之间的主要区别：

  1. Swiss Table（瑞士表）机制
  • swiss 是指瑞士表（Swiss Table）机制，这是一种用于提高哈希表查找效率的优化技术。
  • 瑞士表是一个复杂的哈希表结构，旨在通过使用一些高级技术（如位操作和稀疏存储）来加速键值对的查找。
  • 瑞士表的核心思想是通过一个紧凑的、稀疏的表结构来存储键值对，同时通过位运算快速定位键值对的位置。
  • 瑞士表机制通常用于需要高效查找和插入的场景，特别是在键的分布比较稀疏或者冲突较多的情况下。
  1. No Swiss Table 机制
  • no_swiss 表示不使用瑞士表（no swiss table）机制。
  • 在 no_swiss 情况下，Go 使用更为简单的哈希表结构和算法来处理键值对的存储和查找。
  • 这种机制通常用于简单的、键的分布比较均匀的场景，或者是当瑞士表优化不能带来显著性能提升时。
  1. 实现细节
  • 在 Go 源码中，swiss 和 no_swiss 的区别主要体现在 map 的底层实现上。
  • 使用 swiss 机制时，Go 会使用更复杂的哈希表结构和算法。
  • 使用 no_swiss 机制时，Go 会回退到更传统的哈希表实现方式，可能包括简单的数组和链表结构。
  1. 性能和适用场景
  • **瑞士表机制 (swiss)**：在键的分布不均匀或者冲突较多的情况下，可以显著提高查找效率。适用于大规模、复杂场景下的 map 操作。
  • **非瑞士表机制 (no_swiss)**：在键的分布比较均匀且冲突较少的情况下，性能可能与瑞士表相当，但实现更简单，适用于常规场景。
  1. 源码中的标志
  • 在 Go 源码中，swiss 和 no_swiss 通常通过编译时标志或条件编译来控制。这样可以根据具体的需求和场景选择合适的机制。
  • 例如，在编译时可以通过条件编译选项来选择使用 swiss 或 no_swiss 机制。

定义

基础结构

Go 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
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
}

buckets 是一个指针，最终它指向的是一个结构体：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// bmap 是Go语言中map的桶结构，每个`hmap`包含多个这样的桶。
type bmap struct {
    // tophash 通常包含这个桶中每个键的哈希值的高字节。
    // 如果 tophash[0] < minTopHash, 则 tophash[0]表示桶的迁移状态。
    tophash [abi.OldMapBucketCount]uint8

    // 接下来是 bucketCnt 个键，然后是 bucketCnt 个元素。
    // 注意：将所有的键打包在一起，然后是所有的元素，这样做相比于交替排列键和元素（键/元素/键/元素/...） 
    // 会使代码稍微复杂一些，但这样可以消除填充（padding），因为某些类型如 map[int64]int8 需要填充来对齐。
    // 在键和元素之后，是一个指向溢出桶的指针。
    
    // 注意：Go语言的源码中并未直接在这里展示键和元素的定义，
    // 实际上，键和元素是紧跟在 tophash 数组之后的内存区域里。
}

tophash 通常包含此 buckets 中每个键的哈希值的最高字节。 如果 tophash[0] < minTopHash，则 tophash[0] 是一个桶疏散状态。

但这只是表面(src/runtime/map_noswiss.go)的结构，map 在编译时即确定了 map 中 key、value 及桶的大小，因此在运行时仅仅通过指针操作就可以找到特定位置的元素。编译期动态地创建一个新的结构：

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
type bmap struct {
    // topbits 存储每个键的哈希值的高 8 位信息。
    // 当哈希表执行查找操作时，首先比较这些高位信息，
    // 以快速排除不匹配的键，从而减少后续的比较次数。
    // 数组长度为 8，意味着每个桶最多可以存储 8 个键值对。
    topbits  [8]uint8 // 顶层位图，用于快速判断 key 是否存在。每个 bit 对应 keys 数组中的一个元素，如果 bit 为 1，表示对应的 key 存在；如果 bit 为 0，表示对应的 key 不存在。
    keys     [8]keytype  // 键数组，存储 map 的键。最多可以存储 8 个键。
    values   [8]valuetype // 值数组，存储 map 的值。与 keys 数组一一对应，keys[i] 对应的值为 values[i]。
    pad      uintptr    // 填充字段，用于内存对齐。uintptr 的大小与指针大小相同，在 32 位系统上为 4 字节，在 64 位系统上为 8 字节。
    overflow uintptr    // 溢出指针，指向下一个 bmap。当当前 bmap 存储满了 8 个键值对时，会创建一个新的 bmap，并将 overflow 指针指向新的 bmap。这样就形成了一个 bmap 的链表，可以存储超过 8 个键值对。
}


// 更加详细的解释：
// 1. topbits:  这是一个长度为 8 的 uint8 数组，用作位图。每个 uint8 可以表示 8 个键的存在状态，因此总共可以表示 8 * 8 = 64 个键。但在 bmap 结构体中，只使用了前 8 个键的空间，由 keys 和 values 数组体现。topbits 的作用是快速判断某个 key 是否存在于当前的 bmap 中。例如，要检查 keys[3] 是否存在，只需检查 topbits[0] 的第 4 个 bit（从 0 开始计数）是否为 1。

// 2. keys 和 values: 这两个数组分别存储键和值。它们的大小都是 8，这意味着一个 bmap 最多可以存储 8 个键值对。keys 的类型是 keytype，values 的类型是 valuetype，这两个类型可以根据实际存储的数据类型进行定义。

// 3. pad:  这是一个填充字段，用于内存对齐。Go 语言的 runtime 会根据数据类型的对齐要求进行填充，以提高内存访问效率。  bmap 的大小必须是机器字长的倍数。在 64 位架构上，机器字长是 8 字节。由于 `topbits` (8 字节) + `keys` (8 * keytype 的大小) + `values` (8 * valuetype 的大小) 的总大小可能不是 8 的倍数，因此需要 `pad` 来进行填充，保证 `overflow` 字段的地址是对齐的。  `pad` 的大小会根据 `keytype` 和 `valuetype` 的大小自动调整。

// 4. overflow: 这是一个指向下一个 bmap 的指针。当一个 bmap 满了（存储了 8 个键值对），并且需要插入新的键值对时，Go runtime 会分配一个新的 bmap，并将当前 bmap 的 overflow 指针指向新的 bmap。  这形成了一个类似链表的结构，允许 map 存储超过 8 个键值对。 通过这种溢出机制，Go 的 map 可以动态增长以容纳任意数量的元素。


//  示例：假设 keytype 和 valuetype 都是 uint32

//  如果一个 bmap 存储了 3 个键值对： key1, key2, key3，对应的值分别是 value1, value2, value3. 那么：

//  * topbits[0] 的值可能是 0b00000111  (表示前三个 key 存在)
//  * keys[0] = key1; values[0] = value1
//  * keys[1] = key2; values[1] = value2
//  * keys[2] = key3; values[2] = value3
//  * keys[3] 到 keys[7] 的值是未定义的
//  * values[3] 到 values[7] 的值是未定义的
//  * pad 的值由编译器决定，确保内存对齐
//  * 如果后续还有新的键值对插入，并且当前 bmap 已经满了，那么 runtime 会分配一个新的 bmap，并将当前 bmap 的 overflow 指针指向新的 bmap。

bmap 就是我们常说的“桶”，桶里面会最多装 8 个 key，这些 key 之所以会落入同一个桶，是因为它们经过哈希计算后，哈希结果是“一类”的。在桶内，又会根据 key 计算出来的 hash 值的高 8 位来决定 key 到底落入桶内的哪个位置（一个桶内最多有8个位置）。

来一个整体的图：

hashmap bmap

当 map 的 key 和 value 都不是指针，并且 size 都小于 128 字节的情况下，会把 bmap 标记为不含指针，这样可以避免 gc 时扫描整个 hmap。但是，我们看 bmap 其实有一个 overflow 的字段，是指针类型的，破坏了 bmap 不含指针的设想，这时会把 overflow 移动到 extra 字段来。

1
2
3
4
5
6
7
8
type mapextra struct {
	// overflow[0] contains overflow buckets for hmap.buckets.
	// overflow[1] contains overflow buckets for hmap.oldbuckets.
	overflow [2]*[]*bmap

	// nextOverflow 包含空闲的 overflow bucket，这是预分配的 bucket
	nextOverflow *bmap
}

bmap 是存放 k-v 的地方，我们把视角拉近，仔细看 bmap 的内部组成。

bmap struct

上图就是 bucket 的内存模型，HOB Hash 指的就是 top hash。 注意到 key 和 value 是各自放在一起的，并不是 key/value/key/value/... 这样的形式。源码里说明这样的好处是在某些情况下可以省略掉 padding 字段，节省内存空间。

例如，有这样一个类型的 map：

1
map[int64]int8

如果按照 key/value/key/value/... 这样的模式存储，那在每一个 key/value 对之后都要额外 padding 7 个字节；而将所有的 key，value 分别绑定到一起，这种形式 key/key/.../value/value/...，则只需要在最后添加 padding。

每个 bucket 设计成最多只能放 8 个 key-value 对，如果有第 9 个 key-value 落入当前的 bucket，那就需要再构建一个 bucket ，通过 overflow 指针连接起来。

哈希函数

map 的一个关键点在于，哈希函数的选择。在程序启动时，会检测 cpu 是否支持 aes，如果支持，则使用 aes hash，否则使用 memhash。这是在函数 alginit() 中完成，位于路径：src/runtime/alg.go 下。

key 定位过程

key 经过哈希计算后得到哈希值，共 64 个 bit 位（64位机，32位机就不讨论了，现在主流都是64位机），计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位。还记得前面提到过的 B 吗？如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。

例如，现在有一个 key 经过哈希函数计算后，得到的哈希结果是：

1
10010111 | 000011110110110010001111001010100010010110010101010 │ 01010

用最后的 5 个 bit 位，也就是 01010，值为 10，也就是 10 号桶。这个操作实际上就是取余操作，但是取余开销太大，所以代码实现上用的位操作代替。

再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，这是在寻找已有的 key。最开始桶内还没有 key，新加入的 key 会找到第一个空位，放入。

buckets 编号就是桶编号，当两个不同的 key 落在同一个桶中，也就是发生了哈希冲突。冲突的解决手段是用链表法：在 bucket 中，从前往后找到第一个空位。这样，在查找某个 key 时，先找到对应的桶，再去遍历 bucket 中的 key。

这里参考《Go 程序员面试笔试宝典》里的一张图

mapacess

上图中，假定 B = 5，所以 bucket 总数就是 2^5 = 32。首先计算出待查找 key 的哈希，使用低 5 位 00110，找到对应的 6 号 bucket，使用高 8 位 10010111，对应十进制 151，在 6 号 bucket 中寻找 tophash 值（HOB hash）为 151 的 key，找到了 2 号槽位，这样整个查找过程就结束了。

如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。

通过汇编语言可以看到，查找某个 key 的底层函数是 mapaccess 系列函数。这里我们直接看 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])
}
//

基于提供的 mapaccess1 函数源码，我们可以总结 map get 操作的整体过程如下：

1. 安全性和合法性检查:

  • 竞争检测: 如果启用了竞争检测（raceenabled），函数会记录对 map 和 key 的读取操作，以便检测潜在的并发数据竞争。
  • 内存清理器检查: 如果启用了内存清理器（如 MSAN 或 ASAN），函数会通知这些工具对 key 的读取操作，以便检查内存安全问题。
  • 空 map 或空桶处理: 如果 map 为空（h == nil）或没有任何元素（h.count == 0），则直接返回零值指针，并可能抛出一个 panic。
  • 并发安全检查: 检查 map 的 flags 是否指示正在进行写入操作（h.flags&hashWriting != 0）。如果正在写入，则表示存在并发读写冲突，函数会抛出 panic。

2. 查找目标键值对:

  • 哈希计算: 使用 map 类型的 Hasher 函数计算给定 key 的哈希值（hash := t.Hasher(key, uintptr(h.hash0))）。
  • 桶索引计算: 根据哈希值计算桶的索引（m := bucketMask(h.B)），确定 key 应该存在于哪个桶中。
  • 桶地址计算: 根据桶索引计算桶的内存地址（b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.BucketSize)))）。
  • 扩容处理: 如果 map 正在进行扩容，则需要检查是否存在旧桶（c := h.oldbuckets; c != nil）。如果存在旧桶，则根据扩容状态（是否等大小扩容）调整桶索引，并检查旧桶是否已经被迁移。如果旧桶未迁移，则在旧桶中查找。
  • 桶遍历和键值匹配:
    • 获取哈希值高 8 位: 获取哈希值的高 8 位作为 tophash（top := tophash(hash)），用于快速比较。
    • 遍历桶和溢出桶: 遍历目标桶及其溢出桶（for ; b != nil; b = b.overflow(t)）。
    • 遍历桶内条目: 遍历桶内的每个条目（for i := uintptr(0); i < abi.OldMapBucketCount; i++）。
    • tophash 比较: 比较条目的 tophash 与计算出的 tophash 是否相等（if b.tophash[i] != top）。如果不相等，则继续下一个条目。如果 tophash 等于 emptyRest，则表示后续桶都为空，退出循环。
    • 键地址计算: 如果 tophash 匹配，则计算 key 的内存地址（k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))），并根据 key 类型（是否为指针）进行解引用。
    • 键值比较: 使用 map 类型的 Equal 方法比较计算出的 key 与桶中存储的 key 是否相等（if t.Key.Equal(key, k)）。
    • 值地址计算: 如果 key 相等，则计算 value 的内存地址（e := add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))），并根据 value 类型（是否为指针）进行解引用。
    • 返回 value 指针: 返回 value 的指针（return e）。

3. 未找到 key:

  • 如果遍历完所有桶都没有找到匹配的 key，则返回零值指针（return unsafe.Pointer(&zeroVal[0])）。

简而言之， map get 的过程就是：计算哈希值 -> 定位桶 -> 遍历桶内条目 -> 比较 tophash 和 key -> 返回 value 指针 (或零值指针)。

这里，再看一下定位 key 和 value 的方法以及整个循环的写法。

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))

b 是 bmap 的地址，这里 bmap 还是源码里定义的结构体，只包含一个 tophash 数组，经编译器扩充之后的结构体才包含 key，value，overflow 这些字段。dataOffset 是 key 相对于 bmap 起始地址的偏移：

1
2
3
4
dataOffset = unsafe.Offsetof(struct {
		b bmap
		v int64
	}{}.v)

因此 bucket 里 key 的起始地址就是 unsafe.Pointer(b)+dataOffset。第 i 个 key 的地址就要在此基础上跨过 i 个 key 的大小；而我们又知道，value 的地址是在所有 key 之后，因此第 i 个 value 的地址还需要加上所有 key 的偏移。理解了这些，上面 key 和 value 的定位公式就很好理解了。

再说整个大循环的写法，最外层是一个无限循环，通过

1
b = b.overflow(t)

遍历所有的 bucket，这相当于是一个 bucket 链表。

当定位到一个具体的 bucket 时，里层循环就是遍历这个 bucket 里所有的 cell，或者说所有的槽位，也就是 bucketCnt=8 个槽位。整个循环过程：

mapacess loop

再说一下 minTopHash，当一个 cell 的 tophash 值小于 minTopHash 时，标志这个 cell 的迁移状态。因为这个状态值是放在 tophash 数组里，为了和正常的哈希值区分开，会给 key 计算出来的哈希值一个增量：minTopHash。这样就能区分正常的 top hash 值和表示状态的哈希值。

下面的这几种状态就表征了 bucket 的情况：

1
2
3
4
5
6
7
8
9
// 可能的 tophash 值。我们保留了一些特殊标记的可能值。
// 每个桶（包括它的溢出桶，如果有的话）的所有条目要么都处于 evacuated* 状态，要么都不处于 evacuated* 状态
// （除了在 evacuate() 方法期间，它只在 map 写操作期间发生，因此在此期间没有人可以观察到 map）。
emptyRest      = 0 // 此 cell为空，并且在更高的索引或溢出桶中没有更多的非空单元格。
emptyOne       = 1 // 此 cell为空。
evacuatedX     = 2 // key,value 已经搬迁完毕，但是 key 都在新 bucket 前半部分，键/元素有效。条目已迁移到更大表的前半部分。
evacuatedY     = 3 // 同上，key 在后半部分，迁移到更大表的后半部分。
evacuatedEmpty = 4 // 单元格为空，桶已迁移。
minTopHash     = 5 // 普通填充单元格的最小 tophash 值。

源码里判断这个 bucket 是否已经搬迁完毕，用到的函数：

1
2
3
4
func evacuated(b *bmap) bool {
	h := b.tophash[0]
	return h > empty && h < minTopHash
}

只取了 tophash 数组的第一个值，判断它是否在 0-5 之间。对比上面的常量，当 top hash 是 evacuatedEmpty、evacuatedX、evacuatedY 这三个值之一，说明此 bucket 中的 key 全部被搬迁到了新 bucket。

问题

1.go中slice 和 map 分别作为函数参数时有什么区别？

在 Go 中，slice 和 map 作为函数参数时，都以引用类型的方式传递。这意味着函数接收到的并非 slice 或 map 的副本，而是指向底层数据的指针。 因此，函数内部对 slice 或 map 的修改会影响到调用者传入的原始数据。 然而，它们之间仍然存在一些关键区别：

1. 数据结构和修改方式的区别:

  • Slice: Slice 是一个动态数组的引用，由指向底层数组的指针、长度和容量组成。 当你在函数内部修改 slice 的元素时，修改的是底层数组，因此调用者也能看到这些变化。 然而，如果在函数内部对 slice 进行切片操作或重新分配内存（例如 append 超过容量，导致重新分配底层数组），则会创建一个新的底层数组，原 slice 指向的底层数组保持不变。 这时，调用者看到的原始 slice 不会受到影响。
  • Map: Map 是一个哈希表的引用。 当你在函数内部修改 map 的键值对时，修改的是原始 map 的内容，调用者也能看到这些变化。 包括添加、修改或删除键值对。 你不需要担心像 slice 那样底层数组重新分配的问题。

2. 内存分配的影响:

  • Slice: 如果函数内对 slice 进行 append 操作，并且导致 slice 的容量超过了当前底层数组的容量，Go 会分配一个新的、更大的底层数组，并将原数组的内容复制到新数组中。 这会带来一定的内存分配和复制开销。 如果频繁进行这样的操作，可能会影响性能。
  • Map: Map 的扩容机制与 slice 类似，当 map 中的元素数量达到一定阈值时，Go 会重新分配内存并进行 rehash。 但这通常不会像 slice 的 append 操作那样频繁，因为 map 的初始容量和负载因子会影响扩容的频率。

3. nil 值的行为:

  • Slice: 将 nil slice 作为参数传递给函数，在函数内部可以对其进行 append 操作，这会创建一个新的底层数组。 函数返回后，调用者将看到一个新的、非 nil 的 slice。
  • Map: 将 nil map 作为参数传递给函数，在函数内部直接对其进行赋值或取值操作会导致运行时错误 (panic)。 必须先使用 make 函数初始化 map，然后才能进行操作。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func modifySlice(s []int) {
    //s[0] = 100         // 修改底层数组，调用者可见
    s = append(s, 200) // append 超过容量，创建新的底层数组，调用者不可见
    s = s[2:]          // 切片操作，创建新的 slice，调用者不可见

}

func modifyMap(m map[string]int) {
    m["a"] = 100 // 修改原始 map，调用者可见
    m["b"] = 200 // 修改原始 map，调用者可见
}

func main() {
    slice := []int{1, 2, 3}
    modifySlice(slice)
    fmt.Println(slice) // 输出: [1 2 3]  (append 和切片操作对原始 slice 无效)

    myMap := make(map[string]int)
    modifyMap(myMap)
    fmt.Println(myMap) // 输出: map[a:100 b:200] (修改对原始 map 可见)
 }

参考链接

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

2.《Go学习笔记》

3.Go 语言设计与实现

Golang
#原创 #编程语言 #Golang #源码分析
03.Golang Map源码分析（一、定义与实现原理）
https://blog.longpi1.com/2024/11/21/03-Golang-Map源码分析（一、定义与实现原理）/