map遍历的时候每次顺序都是固定的吗？为什么？

题目来源：字节跳动

答案1：

  1. package main
  3. import "fmt"
  5. func main() {
  6.     fooMap := make(map[string]string)
  7.     fooMap["foo1Key"] = "foo1Value"
  8.     fooMap["foo2Key"] = "foo2Value"
  9.     fooMap["foo3Key"] = "foo3Value"
  10.     fooMap["foo4Key"] = "foo4Value"
  11.     fooMap["foo5Key"] = "foo5Value"
  12.     fooMap["foo6Key"] = "foo6Value"
  14.     for k, v := range fooMap {
  15.         fmt.Printf("k: %s ,v: %s \n", k, v)
  16.     }
  17.     //k: foo1Key ,v: foo1Value
  18.     //k: foo2Key ,v: foo2Value
  19.     //k: foo3Key ,v: foo3Value
  20.     //k: foo4Key ,v: foo4Value
  21.     //k: foo5Key ,v: foo5Value
  22.     //k: foo6Key ,v: foo6Value
  24.     //k: foo5Key ,v: foo5Value
  25.     //k: foo6Key ,v: foo6Value
  26.     //k: foo1Key ,v: foo1Value
  27.     //k: foo2Key ,v: foo2Value
  28.     //k: foo3Key ,v: foo3Value
  29.     //k: foo4Key ,v: foo4Value
  31. }

结论：map遍历的时候每次的顺序是不一样的。

  1. go tool compile -S main.go 
  2. ...初始化map...
  3. 0x0253 00595 (main.go:14)       LEAQ    type.map[string]string(SB), AX
  4.         0x025a 00602 (main.go:14)       LEAQ    ""..autotmp_13+104(SP), BX
  5.         0x025f 00607 (main.go:14)       LEAQ    ""..autotmp_10+152(SP), CX
  6.         0x0267 00615 (main.go:14)       PCDATA  $1, $2
  7.         0x0267 00615 (main.go:14)       CALL    runtime.mapiterinit(SB)
  8.         0x026c 00620 (main.go:14)       JMP     786
  9.         0x0271 00625 (main.go:14)       MOVQ    ""..autotmp_10+160(SP), DX
  10.         0x0279 00633 (main.go:14)       MOVQ    (DX), SI
  11.         0x027c 00636 (main.go:14)       MOVQ    SI, "".v.ptr+64(SP)
  12.         0x0281 00641 (main.go:14)       MOVQ    (CX), AX
  13.         0x0284 00644 (main.go:14)       MOVQ    8(DX), DX
  14. ...

在初始化完成之后，调用了runtime.mapiterinit方法，在go1.18\src\runtime\map.go中找到此方法的实现，看一下源码的实现。

  1. // mapiterinit initializes the hiter struct used for ranging over maps.
  2. // The hiter struct pointed to by 'it' is allocated on the stack
  3. // by the compilers order pass or on the heap by reflect_mapiterinit.
  4. // Both need to have zeroed hiter since the struct contains pointers.
  5. func mapiterinit(t *maptype, h *hmap, it *hiter) {
  6.     if raceenabled && h != nil {
  7.         callerpc := getcallerpc()
  8.         racereadpc(unsafe.Pointer(h), callerpc, abi.FuncPCABIInternal(mapiterinit))
  9.     }
  11.     it.t = t
  12.     if h == nil || h.count == 0 {
  13.         return
  14.     }
  16.     if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {
  17.         throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go
  18.     }
  19.     it.h = h
  21.     // grab snapshot of bucket state
  22.     it.B = h.B
  23.     it.buckets = h.buckets
  24.     if t.bucket.ptrdata == 0 {
  25.         // Allocate the current slice and remember pointers to both current and old.
  26.         // This preserves all relevant overflow buckets alive even if
  27.         // the table grows and/or overflow buckets are added to the table
  28.         // while we are iterating.
  29.         h.createOverflow()
  30.         it.overflow = h.extra.overflow
  31.         it.oldoverflow = h.extra.oldoverflow
  32.     }
  34.     // decide where to start
  35.     r := uintptr(fastrand())
  36.     if h.B > 31-bucketCntBits {
  37.         r += uintptr(fastrand()) << 31
  38.     }
  39.     it.startBucket = r & bucketMask(h.B)
  40.     it.offset = uint8(r >> h.B & (bucketCnt - 1))
  42.     // iterator state
  43.     it.bucket = it.startBucket
  45.     // Remember we have an iterator.
  46.     // Can run concurrently with another mapiterinit().
  47.     if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
  48.         atomic.Or8(&h.flags, iterator|oldIterator)
  49.     }
  51.     mapiternext(it)
  52. }

通过对 mapiterinit 方法阅读，可得知其主要用途是在 map 进行遍历迭代时进行初始化动作。共有三个形参，用于读取当前哈希表的类型信息、当前哈希表的存储信息和当前遍历迭代的数据。

咱们关注到源码中 fastrand 的部分，这个方法名，是不是迷之眼熟。没错，它是一个生成随机数的方法。再看看上下文

  1. // decide where to start
  2.     r := uintptr(fastrand())
  3.     if h.B > 31-bucketCntBits {
  4.         r += uintptr(fastrand()) << 31
  5.     }
  6.     it.startBucket = r & bucketMask(h.B)
  7.     it.offset = uint8(r >> h.B & (bucketCnt - 1))

在这段代码中，它生成了随机数。用于决定从哪里开始循环迭代。更具体的话就是根据随机数，选择一个桶位置作为起始点进行遍历迭代

因此每次重新 for range map，你见到的结果都是不一样的。那是因为它的起始位置根本就不固定！