[[396167]]

本文轉(zhuǎn)載自微信公眾號(hào)「腦子進(jìn)煎魚了」，作者陳煎魚。轉(zhuǎn)載本文請(qǐng)聯(lián)系腦子進(jìn)煎魚了公眾號(hào)。

大家好，我是煎魚。

最近又有同學(xué)問我這個(gè)日經(jīng)話題，想轉(zhuǎn)他文章時(shí)，結(jié)果發(fā)現(xiàn)我的公眾號(hào)竟然沒有發(fā)過，因此今天我再嘮叨兩句，好讓大家避開這個(gè) “坑”。

有的小伙伴沒留意過 Go map 輸出、遍歷順序，以為它是穩(wěn)定的有序的，會(huì)在業(yè)務(wù)程序中直接依賴這個(gè)結(jié)果集順序，結(jié)果栽了個(gè)大跟頭，吃了線上 BUG。

有的小伙伴知道是無序的，但卻不知道為什么,有的卻理解錯(cuò)誤?

奇怪的輸出結(jié)果

今天通過本文，我們將揭開 for range map 輸出的 “神秘” 面紗，看看它內(nèi)部實(shí)現(xiàn)到底是怎么樣的，順序到底是怎么樣?

開始吸魚之路。

前言

例子如下：

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é)果是怎么樣?是有序，還是無序輸出呢?

k: 3, v: EDDYCJY4 
k: 4, v: EDDYCJY5 
k: 0, v: EDDYCJY1 
k: 1, v: EDDYCJY2 
k: 2, v: EDDYCJY3 

從輸出結(jié)果上來講，是非固定順序輸出的，也就是每次都不一樣。但這是為什么呢?

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

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

看一下匯編

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

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

• runtime.mapiterinit
• runtime.mapiternext

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

看一下轉(zhuǎn)換后

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 在編譯器展開后的偽實(shí)現(xiàn)

看一下源碼

runtime.mapiterinit

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) 
} 

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

為什么

咱們關(guān)注到源碼中 fastrand 的部分，這個(gè)方法名，是不是迷之眼熟。沒錯(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ù)。用于決定從哪里開始循環(huán)迭代。更具體的話就是根據(jù)隨機(jī)數(shù)，選擇一個(gè)桶位置作為起始點(diǎn)進(jìn)行遍歷迭代

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

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)選定了起始桶的位置。接下來就是通過 mapiternext 進(jìn)行具體的循環(huán)遍歷動(dòng)作。該方法主要涉及如下：

1. 從已選定的桶中開始進(jìn)行遍歷，尋找桶中的下一個(gè)元素進(jìn)行處理
2. 如果桶已經(jīng)遍歷完，則對(duì)溢出桶 overflow buckets 進(jìn)行遍歷處理

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

總結(jié)

在本文開始，咱們先提出核心討論點(diǎn)：“為什么 Go map 遍歷輸出是不固定順序?”。

經(jīng)過這一番分析，原因也很簡(jiǎn)單明了。就是 for range map 在開始處理循環(huán)邏輯的時(shí)候，就做了隨機(jī)播種...

你想問為什么要這么做?

當(dāng)然是官方有意為之，因?yàn)?Go 在早期(1.0)的時(shí)候，雖是穩(wěn)定迭代的，但從結(jié)果來講，其實(shí)是無法保證每個(gè) Go 版本迭代遍歷規(guī)則都是一樣的。而這將會(huì)導(dǎo)致可移植性問題。

因此，改之。也請(qǐng)不要依賴...

參考

• Go maps in action