7.5 map:为什么遍历 map 是无序的
image
有的小伙伴没留意过 Go map 输出顺序,以为它是稳定的有序的;有的小伙伴知道是无序的,但却不知道为什么?有的却理解错误?今天我们将通过本文,揭开 for range map 的 “神秘” 面纱,看看它内部实现到底是怎么样的,输出顺序到底是怎么样?

前言

1
func main() {
2
m := make(map[int32]string)
3
m[0] = "EDDYCJY1"
4
m[1] = "EDDYCJY2"
5
m[2] = "EDDYCJY3"
6
m[3] = "EDDYCJY4"
7
m[4] = "EDDYCJY5"
8
9
for k, v := range m {
10
log.Printf("k: %v, v: %v", k, v)
11
}
12
}
Copied!
假设运行这段代码,输出结果是按顺序?还是无序输出呢?
1
2019/04/03 23:27:29 k: 3, v: EDDYCJY4
2
2019/04/03 23:27:29 k: 4, v: EDDYCJY5
3
2019/04/03 23:27:29 k: 0, v: EDDYCJY1
4
2019/04/03 23:27:29 k: 1, v: EDDYCJY2
5
2019/04/03 23:27:29 k: 2, v: EDDYCJY3
Copied!
从输出结果上来讲,是非固定顺序输出的,也就是每次都不一样(标题也讲了)。但这是为什么呢?
首先建议你先自己想想原因。其次我在面试时听过一些说法。有人说因为是哈希的所以就是无(乱)序等等说法。当时我是有点 ???
这也是这篇文章出现的原因,希望大家可以一起研讨一下,理清这个问题 :)

看一下汇编

1
...
2
0x009b 00155 (main.go:11) LEAQ type.map[int32]string(SB), AX
3
0x00a2 00162 (main.go:11) PCDATA $2, $0
4
0x00a2 00162 (main.go:11) MOVQ AX, (SP)
5
0x00a6 00166 (main.go:11) PCDATA $2, $2
6
0x00a6 00166 (main.go:11) LEAQ ""..autotmp_3+24(SP), AX
7
0x00ab 00171 (main.go:11) PCDATA $2, $0
8
0x00ab 00171 (main.go:11) MOVQ AX, 8(SP)
9
0x00b0 00176 (main.go:11) PCDATA $2, $2
10
0x00b0 00176 (main.go:11) LEAQ ""..autotmp_2+72(SP), AX
11
0x00b5 00181 (main.go:11) PCDATA $2, $0
12
0x00b5 00181 (main.go:11) MOVQ AX, 16(SP)
13
0x00ba 00186 (main.go:11) CALL runtime.mapiterinit(SB)
14
0x00bf 00191 (main.go:11) JMP 207
15
0x00c1 00193 (main.go:11) PCDATA $2, $2
16
0x00c1 00193 (main.go:11) LEAQ ""..autotmp_2+72(SP), AX
17
0x00c6 00198 (main.go:11) PCDATA $2, $0
18
0x00c6 00198 (main.go:11) MOVQ AX, (SP)
19
0x00ca 00202 (main.go:11) CALL runtime.mapiternext(SB)
20
0x00cf 00207 (main.go:11) CMPQ ""..autotmp_2+72(SP), $0
21
0x00d5 00213 (main.go:11) JNE 193
22
...
Copied!
我们大致看一下整体过程,重点处理 Go map 循环迭代的是两个 runtime 方法,如下:
  • runtime.mapiterinit
  • runtime.mapiternext
但你可能会想,明明用的是 for range 进行循环迭代,怎么出现了这两个函数,怎么回事?

看一下转换后

1
var hiter map_iteration_struct
2
for mapiterinit(type, range, &hiter); hiter.key != nil; mapiternext(&hiter) {
3
index_temp = *hiter.key
4
value_temp = *hiter.val
5
index = index_temp
6
value = value_temp
7
original body
8
}
Copied!
实际上编译器对于 slice 和 map 的循环迭代有不同的实现方式,并不是 for 一扔就完事了,还做了一些附加动作进行处理。而上述代码就是 for range map 在编译器展开后的伪实现

看一下源码

runtime.mapiterinit

1
func mapiterinit(t *maptype, h *hmap, it *hiter) {
2
...
3
it.t = t
4
it.h = h
5
it.B = h.B
6
it.buckets = h.buckets
7
if t.bucket.kind&kindNoPointers != 0 {
8
h.createOverflow()
9
it.overflow = h.extra.overflow
10
it.oldoverflow = h.extra.oldoverflow
11
}
12
13
r := uintptr(fastrand())
14
if h.B > 31-bucketCntBits {
15
r += uintptr(fastrand()) << 31
16
}
17
it.startBucket = r & bucketMask(h.B)
18
it.offset = uint8(r >> h.B & (bucketCnt - 1))
19
it.bucket = it.startBucket
20
...
21
22
mapiternext(it)
23
}
Copied!
通过对 mapiterinit 方法阅读,可得知其主要用途是在 map 进行遍历迭代时进行初始化动作。共有三个形参,用于读取当前哈希表的类型信息、当前哈希表的存储信息和当前遍历迭代的数据

为什么

咱们关注到源码中 fastrand 的部分,这个方法名,是不是迷之眼熟。没错,它是一个生成随机数的方法。再看看上下文:
1
...
2
// decide where to start
3
r := uintptr(fastrand())
4
if h.B > 31-bucketCntBits {
5
r += uintptr(fastrand()) << 31
6
}
7
it.startBucket = r & bucketMask(h.B)
8
it.offset = uint8(r >> h.B & (bucketCnt - 1))
9
10
// iterator state
11
it.bucket = it.startBucket
Copied!
在这段代码中,它生成了随机数。用于决定从哪里开始循环迭代。更具体的话就是根据随机数,选择一个桶位置作为起始点进行遍历迭代
因此每次重新 for range map,你见到的结果都是不一样的。那是因为它的起始位置根本就不固定!

runtime.mapiternext

1
func mapiternext(it *hiter) {
2
...
3
for ; i < bucketCnt; i++ {
4
...
5
k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
6
v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize))
7
...
8
if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
9
!(t.reflexivekey || alg.equal(k, k)) {
10
...
11
it.key = k
12
it.value = v
13
} else {
14
rk, rv := mapaccessK(t, h, k)
15
if rk == nil {
16
continue // key has been deleted
17
}
18
it.key = rk
19
it.value = rv
20
}
21
it.bucket = bucket
22
if it.bptr != b {
23
it.bptr = b
24
}
25
it.i = i + 1
26
it.checkBucket = checkBucket
27
return
28
}
29
b = b.overflow(t)
30
i = 0
31
goto next
32
}
Copied!
在上小节中,咱们已经选定了起始桶的位置。接下来就是通过 mapiternext 进行具体的循环遍历动作。该方法主要涉及如下:
  • 从已选定的桶中开始进行遍历,寻找桶中的下一个元素进行处理
  • 如果桶已经遍历完,则对溢出桶 overflow buckets 进行遍历处理
通过对本方法的阅读,可得知其对 buckets 的遍历规则以及对于扩容的一些处理(这不是本文重点。因此没有具体展开)

总结

在本文开始,咱们先提出核心讨论点:“为什么 Go map 遍历输出是不固定顺序?”。而通过这一番分析,原因也很简单明了。就是 for range map 在开始处理循环逻辑的时候,就做了随机播种...
你想问为什么要这么做?当然是官方有意为之,因为 Go 在早期(1.0)的时候,虽是稳定迭代的,但从结果来讲,其实是无法保证每个 Go 版本迭代遍历规则都是一样的。而这将会导致可移植性问题。因此,改之。也请不要依赖...

参考