05.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
}

上一篇文章我们介绍了go map初始化、，接下来我们看看map的基础操作是如何实现的吧

基础操作

写入

通过汇编语言可以看到，向 map 中插入或者修改 key，最终调用的是 mapassign 函数。

实际上插入或修改 key 的语法是一样的，只不过前者操作的 key 在 map 中不存在，而后者操作的 key 存在 map 中。

mapassign 有一个系列的函数，根据 key 类型的不同，编译器会将其优化为相应的“快速函数”。

key 类型 插入
uint32 mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
uint64 mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
string mapassign_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer

我们只用研究最一般的赋值函数 mapassign。

整体流程与读取比较相似，可以将其分成几个部分依次分析，首先是函数会根据传入的键拿到对应的哈希和桶：

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
// mapassign 函数是 Go 语言运行时中用于在 map 中赋值的关键函数。它处理了 map 的插入和更新操作，包括哈希计算、桶查找、冲突解决、扩容等重要步骤。
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
        // t: map 的类型信息，包含键和值的类型等。
        // h: 指向 hmap 结构的指针，hmap 是 map 的运行时表示。
        // key: 指向要赋值的键的指针。

        // 返回值：指向与键关联的值的指针。

        // .........前置检查
        
        // 计算键的哈希值
        hash := t.Hasher(key, uintptr(h.hash0))

       // 在计算哈希后设置写入标志，如果哈希计算过程中发生panic，不会错误地标记为写入
        h.flags ^= hashWriting

        // 如果桶数组为 nil，则初始化桶数组
        if h.buckets == nil {
                // 分配一个新的桶数组，初始容量为 1。
                h.buckets = newobject(t.Bucket) // newarray(t.Bucket, 1)
        }

again:
        // 计算键对应的 bucket
        bucket := hash & bucketMask(h.B)
        // 如果哈希表正在扩容，执行扩容操作
        if h.growing() {
                growWork(t, h, bucket)
        }
        // 获取 bucket 的指针
        b := (*bmap)(add(h.buckets, bucket*uintptr(t.BucketSize)))
        // 计算键哈希值的高 8 位（tophash）
        top := tophash(hash)


        // 初始化插入位置相关的变量,（inserti）指向 key 的 hash 值在 tophash 数组所处的位置，另一个(insertk)指向 cell 的位置（也就是 key 最终放置的地址）
        var inserti *uint8        // 指向要插入 tophash 的位置的指针
        var insertk unsafe.Pointer // 指向要插入键的位置的指针
        var elem unsafe.Pointer    // 指向要插入值的位置的指针

bucketloop:
        // 遍历桶中的槽位
        for {
                for i := uintptr(0); i < abi.OldMapBucketCount; i++ {
                        // 如果当前位置的 tophash 不匹配
                        if b.tophash[i] != top {
                                if isEmpty(b.tophash[i]) && inserti == nil {
                                        // 找到一个空位，用于后续准备插入
                                        inserti = &b.tophash[i]
                                        insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
                                        elem = add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
                                }
                                if b.tophash[i] == emptyRest {
                                        break bucketloop  // 已经到bucket的末尾或下一个bucket
                                }
                                continue
                        }
                        // 匹配 tophash，检查键是否真正匹配
                        k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.KeySize))
                        if t.IndirectKey() {
                                k = *((*unsafe.Pointer)(k))
                        }
                        if !t.Key.Equal(key, k) {
                                continue
                        }
                        // 找到键，更新值
                        if t.NeedKeyUpdate() {
                                // runtime.typedmemmove 将键移动到对应的内存空间中并返回键对应值的地址 val
                                typedmemmove(t.Key, k, key)
                        }
                        elem = add(unsafe.Pointer(b), dataOffset+abi.OldMapBucketCount*uintptr(t.KeySize)+i*uintptr(t.ValueSize))
                        goto done
                }
                // 如果当前bucket已满，移动到overflow bucket
                ovf := b.overflow(t)
                if ovf == nil {
                        break
                }
                b = ovf
        }

        // 如果没有找到键，需要插入新键值对
        // 如果需要增长表，或溢出桶过多，开始增长
        if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
                hashGrow(t, h)
                goto again  // 表增长后，数据位置可能改变，重新尝试
        }

        if inserti == nil {
                // 如果所有bucket都满了，创建新的overflow bucket
                newb := h.newoverflow(t, b)
                inserti = &newb.tophash[0]
                insertk = add(unsafe.Pointer(newb), dataOffset)
                elem = add(insertk, abi.OldMapBucketCount*uintptr(t.KeySize))
        }

        // 在找到的位置存储新的键和元素
        if t.IndirectKey() {
                kmem := newobject(t.Key)
                *(*unsafe.Pointer)(insertk) = kmem
                insertk = kmem
        }
        if t.IndirectElem() {
                vmem := newobject(t.Elem)
                *(*unsafe.Pointer)(elem) = vmem
        }
        // runtime.typedmemmove 将键移动到对应的内存空间中并返回键对应值的地址 val
        typedmemmove(t.Key, insertk, key)
        *inserti = top
        h.count++

done:
        // 确保写入标志在操作结束时被正确清除
        if h.flags&hashWriting == 0 {
                fatal("concurrent map writes")
        }
        h.flags &^= hashWriting
        if t.IndirectElem() {
                elem = *((*unsafe.Pointer)(elem))
        }
        return elem
}

主要步骤总结：0.前置检查 -> 1.计算哈希值 ->2. 定位桶（如果map正在扩容，则优先进行桶对应的扩容操作） -> 3.遍历桶内条目 -> 4.1在桶中查找键，比较 tophash 和 key ，若找到则更新（更新后直接跳转步骤5），否则准备插入-> 4.2.插入新键值对，更新相关数据结构->5. 清除写入标志并返回值的指针

重点介绍一下步骤4.1与4.2：

4.1在桶中查找键

  • 遍历目标桶中的槽位，比较每个槽位的 tophash（哈希值的高8位）与目标 tophash。
  • 如果 tophash 不匹配，且槽位为空，记录该位置作为潜在的插入点。
  • 如果槽位为 emptyRest，表示已经到达桶的末尾，停止遍历。
  • 如果 tophash匹配，进一步比较键是否相同：
    • 若键相同，执行更新操作，将新值写入对应位置，然后跳转到完成步骤。
  • 如果当前桶遍历完仍未找到匹配的键，继续遍历溢出桶（overflow bucket）。

4.2.插入新键值对，更新相关数据结构

  • 如果在桶中没有找到匹配的键，则准备插入新键值对。

  • 在插入之前，检查是否需要对哈希表进行扩容：

    • 如果插入新键后负载因子超过阈值，或者溢出桶过多，触发哈希表的扩容操作（hashGrow），然后重新尝试插入操作。

  • 如果找到了空位，直接使用该位置。如果没有空位，创建一个新的溢出桶。

  • 将新键和值插入到找到的空位中：

    • 如果键或值是间接类型（IndirectKey 或 IndirectElem），则需要先分配内存。

  • 更新 tophash，增加计数器 count，表示成功插入了一个新键值对。

需注意，哈希并不会在 runtime.mapassign这个运行时函数中将值拷贝到桶中，该函数只会返回内存地址，真正的赋值操作是在编译期间插入的：

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

其中 24(SP) 是该函数返回的值地址，我们通过 LEAQ 指令将字符串的地址存储到寄存器 AX 中，MOVQ 指令将字符串 "88" 存储到了目标地址上完成了这次哈希的写入。

扩容

上面介绍写入过程时省略了扩容操作，随着哈希表中元素的逐渐增加，哈希的性能会逐渐恶化，所以map在写入时会map容量进行检查是否需要扩容，如果达到对应瓶颈，我们需要通过扩容更多的桶和更大的内存保证哈希的读写性能：

Go 语言采用一个 bucket 里装载 8 个 key，定位到某个 bucket 后，还需要再定位到具体的 key，这实际上又用了时间换空间。

当然，这样做，要有一个度，不然所有的 key 都落在了同一个 bucket 里，直接退化成了链表，各种操作的效率直接降为 O(n)，是不行的。

因此，需要有一个指标来衡量前面描述的情况，就是装载因子。

mapassign函数会在以下两种情况发生时触发哈希的扩容：

  1. 装载因子超过阈值，源码里定义的阈值是 6.5。
  2. 使用了太多溢出桶；overflow 的 bucket 数量过多：当 B 小于 15，也就是 bucket 总数 2^B 小于 2^15 时，如果 overflow 的 bucket 数量超过 2^B；当 B >= 15，也就是 bucket 总数 2^B 大于等于 2^15，如果 overflow 的 bucket 数量超过 2^15。

对应扩容条件的源码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func overLoadFactor(count int, B uint8) bool {
	//abi.OldMapBucketCount: 这是一个为了兼容旧版本 Go 实现的常量。在较旧的版本中，map 的实现方式略有不同。这个常量确保了在新版本中，即使 count 很小，也能保持与旧版本的行为一致。
	//loadFactorNum 和 loadFactorDen: 这两个常量共同定义了 map 的目标负载因子。通过调整这两个常量的值，可以控制 map 的空间利用率和查找效率之间的平衡。 在 Go 1.18 及以后版本中, loadFactorNum/loadFactorDen 的值约为 6.5。
	//简而言之，overLoadFactor 函数的作用是：根据预期的元素数量 (count) 和桶的数量 (2 的 B 次方)，判断 map 的负载因子是否会超过预设值。如果超过，则返回 true，表示需要增加桶的数量 (增加 B 的值) 以降低负载因子。
    return count > abi.OldMapBucketCount && 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.
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 点：每个 bucket 有 8 个空位，在没有溢出，且所有的桶都装满了的情况下，装载因子算出来的结果是 8。因此当装载因子超过 6.5 时，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。

第 2 点：是对第 1 点的补充。就是说在装载因子比较小的情况下，这时候 map 的查找和插入效率也很低，而第 1 点识别不出来这种情况。表面现象就是计算装载因子的分子比较小，即 map 里元素总数少，但是 bucket 数量多（真实分配的 bucket 数量多，包括大量的 overflow bucket）。

对于命中条件 1，2 的限制，都会发生扩容。但是扩容的策略并不相同，毕竟两种条件应对的场景不同。

对于条件 1，元素太多，而 bucket 数量太少，很简单：将 B 加 1，bucket 最大数量（2^B）直接变成原来 bucket 数量的 2 倍。于是，就有新老 bucket 了。注意，这时候元素都在老 bucket 里，还没迁移到新的 bucket 来。而且，新 bucket 只是最大数量变为原来最大数量（2^B）的 2 倍（2^B * 2）。

对于条件 2，其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。这样，原来，在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间，提高 bucket 利用率，map 的查找和插入效率自然就会提升。

对于条件 2 的解决方案，曹大的博客里还提出了一个极端的情况：如果插入 map 的 key 哈希都一样，就会落到同一个 bucket 里，超过 8 个就会产生 overflow bucket，结果也会造成 overflow bucket 数过多。移动元素其实解决不了问题，因为这时整个哈希表已经退化成了一个链表，操作效率变成了 O(n)。

扩容的入口runtime.hashGrow：

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
//  src/runtime/hashGrow
func hashGrow(t *maptype, h *hmap) {
        // 当 map 中的元素数量超过负载因子时，需要进行扩容。
        // 扩容有两种方式：
        // 1. 桶数量翻倍 (bigger = 1)，用于元素数量显著增加的情况。
        // 2. 桶数量不变，整理溢出桶 (bigger = 0)，用于溢出桶过多的情况，减少溢出桶的数量，提高效率。

        // bigger 变量用于标记是否需要增加桶的数量。默认为 1，表示需要翻倍。B+1 相当于是原来 2 倍的空间
        bigger := uint8(1)

        //对应条件 2 ,查当前元素数量加一（假设即将插入一个新元素）是否超过负载因子,果没有超过负载因子，则选择整理溢出桶的方式，即不增加桶的数量。
        if !overLoadFactor(h.count+1, h.B) {
            	// 进行等量的内存扩容，所以bigger0=0, 变
                bigger = 0
                // 设置 sameSizeGrow 标志，表示这次扩容是整理溢出桶，桶数量不变。
                h.flags |= sameSizeGrow
        }

        // 保存旧的桶数组。将老 buckets 挂到 oldbuckets 上
        oldbuckets := h.buckets

        // 创建新的桶数组。
        // makeBucketArray 函数会根据新的桶数量 (h.B + bigger) 创建一个新的桶数组，并返回指向新桶数组的指针以及指向预创建的溢出桶的指针。
        newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

        // 清除迭代器相关的标志位，并保留 oldIterator 标志。
        // 如果当前有迭代器正在使用 map，则设置 oldIterator 标志，
        // 这样在后续的 evacuate 操作中可以正确处理迭代器。
        flags := h.flags &^ (iterator | oldIterator)
        if h.flags&iterator != 0 {
                flags |= oldIterator
        }

        // 提交扩容操作（原子操作，对垃圾回收器可见）。
        // 更新桶的数量。
        h.B += bigger
        // 更新标志位。
        h.flags = flags
        // 将旧的桶数组保存到 oldbuckets 中，用于后续的 evacuate 操作。
        h.oldbuckets = oldbuckets
        // 将新的桶数组设置为当前桶数组。
        h.buckets = newbuckets
        // 初始化 nevacuate 计数器，表示还没有迁移任何桶。
        h.nevacuate = 0
        // 初始化 noverflow 计数器，表示新的桶数组中还没有溢出桶。
        h.noverflow = 0

        // 如果存在溢出桶相关的信息，则处理溢出桶。
        if h.extra != nil && h.extra.overflow != nil {
                // 检查 oldoverflow 是否已经存在，如果存在则说明之前的扩容操作还没有完成，抛出异常。
                if h.extra.oldoverflow != nil {
                        throw("oldoverflow is not nil")
                }
                // 将当前的溢出桶列表移动到 oldoverflow 中，并将 overflow 置为空。
                // 这样在后续的 evacuate 操作中可以将旧的溢出桶中的元素迁移到新的桶数组中。
                h.extra.oldoverflow = h.extra.overflow
                h.extra.overflow = nil
        }

        // 如果预创建了溢出桶，则将其保存到 mapextra 结构中。
        if nextOverflow != nil {
                // 如果 mapextra 结构不存在，则创建一个新的。
                if h.extra == nil {
                        h.extra = new(mapextra)
                }
                // 将预创建的溢出桶保存到 nextOverflow 中。
                h.extra.nextOverflow = nextOverflow
        }

        // 哈希表数据的实际拷贝操作由 growWork() 和 evacuate() 函数增量完成。
        // growWork() 函数负责调度 evacuate() 函数，evacuate() 函数负责将旧桶中的元素迁移到新的桶数组中。
        // 这种增量拷贝的方式可以避免一次性拷贝大量数据导致的性能问题，
        // 并保证在扩容过程中 map 的正常使用。
}

哈希在扩容的过程中会通过 runtime.makeBucketArray 创建一组新桶和预创建的溢出桶，随后将原有的桶数组设置到 oldbuckets 上并将新的空桶设置到 buckets 上，溢出桶也使用了相同的逻辑更新，下图展示了触发扩容后的哈希,引自Go 语言设计与实现：

hashmap-hashgrow

我们在 runtime.hashGrow 中还看不出来等量扩容和翻倍扩容的太多区别，等量扩容创建的新桶数量只是和旧桶一样，该函数中只是创建了新的桶，并没有对数据进行拷贝和转移。哈希表的数据迁移的过程在是 runtime.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
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
// growWork 函数用于处理哈希表增长过程中的迁移工作
// 参数说明：
// t: map类型的描述符
// h: map的运行时表示
// bucket: 当前操作的bucket的地址
func growWork(t *maptype, h *hmap, bucket uintptr) {
	// 确保我们迁移与当前要使用的 bucket 对应的 oldbucket
	// bucket&h.oldbucketmask() 用于找到对应的旧 bucket
	// 这样做是为了确保当前要访问的 bucket 数据是最新的
	evacuate(t, h, bucket&h.oldbucketmask())

	// 如果 map 仍在增长过程中，则额外迁移一个 oldbucket
	// 这样做是为了逐步推进整个增长过程
	if h.growing() {
		// h.nevacuate 记录下一个需要被迁移的 bucket 编号
		// 通过这种渐进式迁移的方式，避免一次性迁移造成的性能问题
		evacuate(t, h, h.nevacuate)
	}
}


// evacuate 函数用于将旧bucket中的数据迁移到新bucket
// 参数说明：
// t: map类型的描述符
// h: map的运行时表示
// oldbucket: 需要迁移的旧bucket的序号
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
	// 获取旧bucket的指针
	b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.BucketSize)))
	// 计算新的bit位，用于决定数据迁移的目的地
	newbit := h.noldbuckets()
	// 如果bucket还没有被清空，则开始处理
	if !evacuated(b) {
		// xy用于存储迁移的目标位置
		// x表示低位bucket，y表示高位bucket（仅在容量翻倍时使用）
		var xy [2]evacDst
		x := &xy[0]
		// 设置x的bucket地址
		x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.BucketSize)))
		x.k = add(unsafe.Pointer(x.b), dataOffset)               // 键的起始地址
		x.e = add(x.k, abi.OldMapBucketCount*uintptr(t.KeySize)) // 元素的结束地址

		// 如果不是等量扩容，需要计算y的目标位置
		if !h.sameSizeGrow() {
			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, abi.OldMapBucketCount*uintptr(t.KeySize))
		}

		// 遍历bucket及其溢出bucket
		for ; b != nil; b = b.overflow(t) {
			k := add(unsafe.Pointer(b), dataOffset)               // 当前bucket中键的起始地址
			e := add(k, abi.OldMapBucketCount*uintptr(t.KeySize)) // 当前bucket中元素的结束地址
			// 遍历bucket中的每个cell
			for i := 0; i < abi.OldMapBucketCount; i, k, e = i+1, add(k, uintptr(t.KeySize)), add(e, uintptr(t.ValueSize)) {
               // 当前 cell 的 top hash 值
				top := b.tophash[i]
				// 如果cell为空，标记为已迁移
				if isEmpty(top) {
					b.tophash[i] = evacuatedEmpty
					continue
				}
				// 检查哈希表的状态是否正确
				if top < minTopHash {
					throw("bad map state")
				}
				// 处理key
				k2 := k
               // 如果 key 是指针，则解引用
				if t.IndirectKey() {
					k2 = *((*unsafe.Pointer)(k2))
				}

				// 决定是否使用y bucket（仅在容量翻倍时有效）
				var useY uint8
                // 如果不是等量扩容
				if !h.sameSizeGrow() {
					// 计算键的哈希值以决定迁移到哪个bucket
					hash := t.Hasher(k2, uintptr(h.hash0))
					if h.flags&iterator != 0 && !t.ReflexiveKey() && !t.Key.Equal(k2, k2) {
						useY = top & 1 // 对于某些特殊情况，使用tophash的低位决定
						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
				dst := &xy[useY] // 选择迁移目的地

				if dst.i == abi.OldMapBucketCount {
					dst.b = h.newoverflow(t, dst.b) // 如果当前目标bucket满了，创建或获取新的溢出bucket
					dst.i = 0
					dst.k = add(unsafe.Pointer(dst.b), dataOffset)
					dst.e = add(dst.k, abi.OldMapBucketCount*uintptr(t.KeySize))
				}
				// 设置目标bucket的tophash
				dst.b.tophash[dst.i&(abi.OldMapBucketCount-1)] = top

				// 判断key 是否指针
				if t.indirectkey {
					// 将原 key（是指针）复制到新位置
					*(*unsafe.Pointer)(xk) = k2 // copy pointer
				} else {
					// 将原 key（是值）复制到新位置
					typedmemmove(t.key, xk, k) // copy value
				}
				// value 是指针，操作同 key
				if t.IndirectElem() {
					*(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e) // 如果元素是间接的，复制元素指针
				} else {
					typedmemmove(t.Elem, dst.e, e) // 直接复制值
				}
				dst.i++
				// 更新键和元素的指针
				dst.k = add(dst.k, uintptr(t.KeySize))
				dst.e = add(dst.e, uintptr(t.ValueSize))
			}
		}
		// 清理旧bucket中的数据以帮助GC
		if h.flags&oldIterator == 0 && t.Bucket.Pointers() {
			b := add(h.oldbuckets, oldbucket*uintptr(t.BucketSize))
			// 保留tophash，因为它维护了转移状态
			ptr := add(b, dataOffset)
			n := uintptr(t.BucketSize) - dataOffset
			memclrHasPointers(ptr, n)
		}
	}

	// 如果当前处理的bucket是下一个要被转移的，更新转移标记
	if oldbucket == h.nevacuate {
		advanceEvacuationMark(h, t, newbit)
	}
}

runtime.evacuate 会将一个旧桶中的数据分流到两个新桶，所以它会创建两个用于保存分配上下文的 runtime.evacDst 结构体，这两个结构体分别指向了一个新桶：

hashmap-evacuate-destination

下面通过相关流程图（取自Go 程序员面试笔试宝典）来宏观地看一下扩容前后的变化。

扩容前，B = 2，共有 4 个 buckets，lowbits 表示 hash 值的低位。假设我们不关注其他 buckets 情况，专注在 2 号 bucket。并且假设 overflow 太多，触发了等量扩容（对应于前面的条件 2）。

扩容前

扩容完成后，overflow bucket 消失了，key 都集中到了一个 bucket，更为紧凑了，提高了查找的效率。

same size 扩容

假设触发了 2 倍的扩容，那么扩容完成后，老 buckets 中的 key 分裂到了 2 个 新的 bucket。一个在 x part，一个在 y 的 part。依据是 hash 的 lowbits。新 map 中 0-3 称为 x part，4-7 称为 y part。

2倍扩容

注意，上面的两张图忽略了其他 buckets 的搬迁情况，表示所有的 bucket 都搬迁完毕后的情形。实际上，我们知道，搬迁是一个“渐进”的过程，并不会一下子就全部搬迁完毕。所以在搬迁过程中，oldbuckets 指针还会指向原来老的 []bmap，并且已经搬迁完毕的 key 的 tophash 值会是一个状态值，表示 key 的搬迁去向。

问题

map key为什么无序？

1.哈希表的实现机制

  • map 在底层是通过哈希表(hash table)实现的
  • key 通过哈希函数计算得到的哈希值决定了其在哈希表中的位置
  • 哈希值的计算结果本身就不保证与 key 的顺序有关
  • 当 map 容量需要扩展时,会触发扩容操作
  • 扩容后所有 key 会重新计算哈希值并分配到新的位置
  • 这个过程会改变原有的顺序

2.遍历实现

  • Go 在遍历 map 时会随机选择一个起始位置
  • 这样做是为了避免程序依赖 map 的遍历顺序
  • 每次遍历的顺序都可能不同

3.性能考虑

  • 无序可以提高查询和插入的效率
  • 不需要维护额外的顺序信息
  • 减少了内存开销

如果需要有序遍历 map,可以：

1
2
3
4
5
6
7
8
9
10
11
12
13
// 1. 将 key 提取到切片中排序
keys := make([]string, 0, len(m))
for k := range m {
    keys = append(keys, k)
}
sort.Strings(keys)

// 2. 按照排序后的 key 遍历
for _, k := range keys {
    fmt.Println(k, m[k])
}

// 3. 或使用有序的数据结构如 treemap

或者使用专门的有序 map 实现,如标准库中的 container/list 等。

总之,map 的无序性是一种设计选择,在大多数场景下这种设计是合理的,因为它提供了更好的性能和实现简单性。如果确实需要有序性,可以在 map 之上构建额外的有序索引。

float 类型可以作为 map 的 key 吗

从语法上看，是可以的。Go 语言中只要是可比较的类型都可以作为 key。除开 slice，map，functions 这几种类型，其他类型都是 OK 的。具体包括：布尔值、数字、字符串、指针、通道、接口类型、结构体、只包含上述类型的数组。这些类型的共同特征是支持 == 和 != 操作符，k1 == k2 时，可认为 k1 和 k2 是同一个 key。如果是结构体，只有 hash 后的值相等以及字面值相等，才被认为是相同的 key。很多字面值相等的，hash出来的值不一定相等，比如引用。

顺便说一句，任何类型都可以作为 value，包括 map 类型。

  1. 精度问题：

    • 1.精度问题（浮点数在计算机中表示时，存在精度误差的问题。比如，0.1 + 0.2 可能不会精确等于 0.3，这使得浮点数的直接比较变得不可靠。在 map 中，键的等值比较是必须的，但由于浮点数的精度问题，直接比较两个浮点数是否相等可能会导致意外结果

  2. IEEE 754 标准：

    • Go 遵循 IEEE 754 浮点数标准，这个标准中包含了特殊值如 NaN（Not a Number）。NaN 和任何数（包括它自己）比较都返回 false，这使得 NaN 作为键会导致逻辑上的不一致。

      1
      2
      3
      4
      5
      6
      m := make(map[float64]int)
      m[math.NaN()] = 1
      m[math.NaN()] = 2

      // NaN != NaN
      fmt.Println(m[math.NaN()]) //返回0

  3. 哈希和等值比较：

    • map 需要键具有可哈希性和可比较性，以便能够一致地查找、插入和删除。浮点数由于其表示的不确定性，不适合直接用于需要精确匹配的场景中。

如何比较两个 map 相等

map 深度相等的条件：

1
2
3
1、都为 nil
2、非空、长度相等，指向同一个 map 实体对象
3、相应的 key 指向的 value “深度”相等

直接将使用 map1 == map2 是错误的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func compareMaps(map1, map2 map[string]int) bool {
    // 1. 比较长度
    if len(map1) != len(map2) {
        return false
    }

    // 2. 比较内容
    for k, v1 := range map1 {
        // 检查 key 是否存在
        v2, ok := map2[k]
        if !ok {
            return false
        }
        // 比较值
        if v1 != v2 {
            return false
        }
    }

    return true
}

参考链接

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

2.《Go学习笔记》

3.Go 语言设计与实现

Golang
#原创 #编程语言 #Golang #源码分析
05.Golang Map源码分析（三、基础操作之写入、扩容）
https://blog.longpi1.com/2024/11/28/05.Golang-Map源码分析（三、基础操作之写入、扩容）/