golang

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

golang中map每次迭代的时候,key值的顺序都会发生变化,这有点想不通,如果map已经固定了,buckets不再变化,按直觉来想是不会变化的。

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

没有整明白的话,就去看下源码,首先用go tool compile -S 看下编译出来的goasm码,对应符号可以看到源码的行数。

0x0189 00393 (main.go:13) LEAQ ""..autotmp_9+272(SP), DI 
0x0191 00401 (main.go:13) XORPS X0, X0 
0x0194 00404 (main.go:13) PCDATA $0, $-2 
0x0194 00404 (main.go:13) LEAQ -32(DI), DI 
0x0198 00408 (main.go:13) NOP 
0x01a0 00416 (main.go:13) DUFFZERO $273
0x01b3 00435 (main.go:13) PCDATA $0, $-1 
0x01b3 00435 (main.go:13) LEAQ type.map[int]int(SB), AX 
0x01ba 00442 (main.go:13) MOVQ AX, (SP) 
0x01be 00446 (main.go:13) LEAQ ""..autotmp_12+224(SP), AX 
0x01c6 00454 (main.go:13) MOVQ AX, 8(SP) 
0x01cb 00459 (main.go:13) LEAQ ""..autotmp_9+272(SP), AX 
0x01d3 00467 (main.go:13) MOVQ AX, 16(SP) 
0x01d8 00472 (main.go:13) PCDATA $1, $2 
0x01d8 00472 (main.go:13) CALL runtime.mapiterinit(SB) 
0x01dd 00477 (main.go:13) JMP 606 
0x01df 00479 (main.go:13) MOVQ (AX), AX 
 ...

看到了迭代的时候调用了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个元素,再运行呢,看看下图。

可以看到是很难预测下一个数值的,因为此时已经有了2个bucket,所以顺序相对于一个bucket就会打的更乱。

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

Leave a Reply

Your email address will not be published.

6 + 18 =