Golang中map迭代顺序为何总是变化

Golangmap每次迭代的时候,key值的顺序都会发生变化,Golang到底是如何设置的呢?先编写下列代码进行运行测试:

func main() {
    var m = make(map[int]int)
    m[1] = 1
    m[2] = 2
    m[3] = 3
    m[4] = 4
    m[5] = 5
    // m[6] = 6
    // m[7] = 7
    // m[8] = 8
    // m[9] = 9

    fmt.Println("first:")
    for k := range m {
        fmt.Println(k)
    }

    fmt.Println("second:")

    for k := range m {
        fmt.Println(k)
    }
}

运行上面代码,发现确实出现了两次不同顺序。

$ go run main.go
first:
1
2
3
4
5
second:
4
5
1
2
3

选择去追下具体实现的源码来查找问题所在,map迭代调用了runtime.mapiterinit函数,而这个函数也在src/runtime/map.go中可以找到,缩略下其他代码,可以看到每次迭代的起始都是用了一个随机数。这个随机数不仅参与了buckets的随机,而且参与了buckets内的起始随机。

func mapiterinit(t *maptype, h *hmap, it *hiter) {
    ......
    // decide where to start
    r := uintptr(fastrand())
    if h.B > 31-bucketCntBits {
        r += uintptr(fastrand()) << 31
    }
    it.startBucket = r & bucketMask(h.B)
    it.offset = uint8(r >> h.B & (bucketCnt - 1))

    // iterator state
    it.bucket = it.startBucket
    ......
}

如果map是8个以内,也就是只有一个bucket的话,还是可以预测下一个顺序的值是什么,例如上面的运行,只要得到首个,就可以猜出来后面的顺序,但如果把map增加到9个元素,再运行呢,看看下图。

$ go run main.go
first:
3
4
5
1
2
8
9
6
7
second:
2
3
4
5
1
7
8
9
6

可以看到是很难预测下一个数值的,因为此时已经有了2个bucket,根据上述源码的实现,顺序相对于一个bucket就会变得不可预测。

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注

6 + 18 =