摘要：有人說(shuō)因?yàn)槭枪５乃跃褪菬o(wú)亂序等等說(shuō)法。沒(méi)錯(cuò)，它是一個(gè)生成隨機(jī)數(shù)的方法。更具體的話就是根據(jù)隨機(jī)數(shù)，選擇一個(gè)桶位置作為起始點(diǎn)進(jìn)行遍歷迭代因此每次重新，你見(jiàn)到的結(jié)果都是不一樣的。

有的小伙伴沒(méi)留意過(guò) Go map 輸出順序，以為它是穩(wěn)定的有序的；有的小伙伴知道是無(wú)序的，但卻不知道為什么？有的卻理解錯(cuò)誤？今天我們將通過(guò)本文，揭開(kāi) for range map 的 “神秘” 面紗，看看它內(nèi)部實(shí)現(xiàn)到底是怎么樣的，輸出順序到底是怎么樣？

原文地址：為什么遍歷 Go map 是無(wú)序的？

func main() {
    m := make(map[int32]string)
    m[0] = "EDDYCJY1"
    m[1] = "EDDYCJY2"
    m[2] = "EDDYCJY3"
    m[3] = "EDDYCJY4"
    m[4] = "EDDYCJY5"

    for k, v := range m {
        log.Printf("k: %v, v: %v", k, v)
    }
}

假設(shè)運(yùn)行這段代碼，輸出結(jié)果是按順序？還是無(wú)序輸出呢？

2019/04/03 23:27:29 k: 3, v: EDDYCJY4
2019/04/03 23:27:29 k: 4, v: EDDYCJY5
2019/04/03 23:27:29 k: 0, v: EDDYCJY1
2019/04/03 23:27:29 k: 1, v: EDDYCJY2
2019/04/03 23:27:29 k: 2, v: EDDYCJY3

從輸出結(jié)果上來(lái)講，是非固定順序輸出的，也就是每次都不一樣（標(biāo)題也講了）。但這是為什么呢？

首先建議你先自己想想原因。其次我在面試時(shí)聽(tīng)過(guò)一些說(shuō)法。有人說(shuō)因?yàn)槭枪５乃跃褪菬o(wú)（亂）序等等說(shuō)法。當(dāng)時(shí)我是有點(diǎn) ？？？

這也是這篇文章出現(xiàn)的原因，希望大家可以一起研討一下，理清這個(gè)問(wèn)題 ：）

    ...
    0x009b 00155 (main.go:11)    LEAQ    type.map[int32]string(SB), AX
    0x00a2 00162 (main.go:11)    PCDATA    $2, $0
    0x00a2 00162 (main.go:11)    MOVQ    AX, (SP)
    0x00a6 00166 (main.go:11)    PCDATA    $2, $2
    0x00a6 00166 (main.go:11)    LEAQ    ""..autotmp_3+24(SP), AX
    0x00ab 00171 (main.go:11)    PCDATA    $2, $0
    0x00ab 00171 (main.go:11)    MOVQ    AX, 8(SP)
    0x00b0 00176 (main.go:11)    PCDATA    $2, $2
    0x00b0 00176 (main.go:11)    LEAQ    ""..autotmp_2+72(SP), AX
    0x00b5 00181 (main.go:11)    PCDATA    $2, $0
    0x00b5 00181 (main.go:11)    MOVQ    AX, 16(SP)
    0x00ba 00186 (main.go:11)    CALL    runtime.mapiterinit(SB)
    0x00bf 00191 (main.go:11)    JMP    207
    0x00c1 00193 (main.go:11)    PCDATA    $2, $2
    0x00c1 00193 (main.go:11)    LEAQ    ""..autotmp_2+72(SP), AX
    0x00c6 00198 (main.go:11)    PCDATA    $2, $0
    0x00c6 00198 (main.go:11)    MOVQ    AX, (SP)
    0x00ca 00202 (main.go:11)    CALL    runtime.mapiternext(SB)
    0x00cf 00207 (main.go:11)    CMPQ    ""..autotmp_2+72(SP), $0
    0x00d5 00213 (main.go:11)    JNE    193
    ...

我們大致看一下整體過(guò)程，重點(diǎn)處理 Go map 循環(huán)迭代的是兩個(gè) runtime 方法，如下：

runtime.mapiterinit

runtime.mapiternext

但你可能會(huì)想，明明用的是 for range 進(jìn)行循環(huán)迭代，怎么出現(xiàn)了這兩個(gè)函數(shù)，怎么回事？

var hiter map_iteration_struct
for mapiterinit(type, range, &hiter); hiter.key != nil; mapiternext(&hiter) {
    index_temp = *hiter.key
    value_temp = *hiter.val
    index = index_temp
    value = value_temp
    original body
}

實(shí)際上編譯器對(duì)于 slice 和 map 的循環(huán)迭代有不同的實(shí)現(xiàn)方式，并不是 for 一扔就完事了，還做了一些附加動(dòng)作進(jìn)行處理。而上述代碼就是 for range map 在編譯器展開(kāi)后的偽實(shí)現(xiàn)

func mapiterinit(t *maptype, h *hmap, it *hiter) {
    ...
    it.t = t
    it.h = h
    it.B = h.B
    it.buckets = h.buckets
    if t.bucket.kind&kindNoPointers != 0 {
        h.createOverflow()
        it.overflow = h.extra.overflow
        it.oldoverflow = h.extra.oldoverflow
    }

    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))
    it.bucket = it.startBucket
    ...

    mapiternext(it)
}

通過(guò)對(duì) mapiterinit 方法閱讀，可得知其主要用途是在 map 進(jìn)行遍歷迭代時(shí)進(jìn)行初始化動(dòng)作。共有三個(gè)形參，用于讀取當(dāng)前哈希表的類(lèi)型信息、當(dāng)前哈希表的存儲(chǔ)信息和當(dāng)前遍歷迭代的數(shù)據(jù)

咱們關(guān)注到源碼中 fastrand 的部分，這個(gè)方法名，是不是迷之眼熟。沒(méi)錯(cuò)，它是一個(gè)生成隨機(jī)數(shù)的方法。再看看上下文：

...
// 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

在這段代碼中，它生成了隨機(jī)數(shù)。用于決定從哪里開(kāi)始循環(huán)迭代。更具體的話就是根據(jù)隨機(jī)數(shù)，選擇一個(gè)桶位置作為起始點(diǎn)進(jìn)行遍歷迭代

因此每次重新 for range map，你見(jiàn)到的結(jié)果都是不一樣的。那是因?yàn)樗钠鹗嘉恢酶揪筒还潭ǎ?/p> runtime.mapiternext

func mapiternext(it *hiter) {
    ...
    for ; i < bucketCnt; i++ {
        ...
        k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
        v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.valuesize))
        ...
        if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
            !(t.reflexivekey || alg.equal(k, k)) {
            ...
            it.key = k
            it.value = v
        } else {
            rk, rv := mapaccessK(t, h, k)
            if rk == nil {
                continue // key has been deleted
            }
            it.key = rk
            it.value = rv
        }
        it.bucket = bucket
        if it.bptr != b { 
            it.bptr = b
        }
        it.i = i + 1
        it.checkBucket = checkBucket
        return
    }
    b = b.overflow(t)
    i = 0
    goto next
}

在上小節(jié)中，咱們已經(jīng)選定了起始桶的位置。接下來(lái)就是通過(guò) mapiternext 進(jìn)行具體的循環(huán)遍歷動(dòng)作。該方法主要涉及如下：

從已選定的桶中開(kāi)始進(jìn)行遍歷，尋找桶中的下一個(gè)元素進(jìn)行處理

如果桶已經(jīng)遍歷完，則對(duì)溢出桶 overflow buckets 進(jìn)行遍歷處理

通過(guò)對(duì)本方法的閱讀，可得知其對(duì) buckets 的遍歷規(guī)則以及對(duì)于擴(kuò)容的一些處理（這不是本文重點(diǎn)。因此沒(méi)有具體展開(kāi)）

在本文開(kāi)始，咱們先提出核心討論點(diǎn)：“為什么 Go map 遍歷輸出是不固定順序？”。而通過(guò)這一番分析，原因也很簡(jiǎn)單明了。就是 for range map 在開(kāi)始處理循環(huán)邏輯的時(shí)候，就做了隨機(jī)播種...

你想問(wèn)為什么要這么做？當(dāng)然是官方有意為之，因?yàn)?Go 在早期（1.0）的時(shí)候，雖是穩(wěn)定迭代的，但從結(jié)果來(lái)講，其實(shí)是無(wú)法保證每個(gè) Go 版本迭代遍歷規(guī)則都是一樣的。而這將會(huì)導(dǎo)致可移植性問(wèn)題。因此，改之。也請(qǐng)不要依賴(lài)...

Go maps in action