[[396167]]

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

大家好，我是煎魚。

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

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

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

奇怪的輸出結(jié)果

今天通過本文，我們將揭開 for range map 輸出的 “神秘” 面紗，看看它內(nèi)部實現(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è)運行這段代碼，輸出的結(jié)果是怎么樣?是有序，還是無序輸出呢?

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

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

首先建議你先自己想想原因。其次我在面試時聽過一些說法。有人說因為是哈希的所以就是無(亂)序等等說法。當時我是有點 ???

這也是這篇文章出現(xià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 
... 

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

• runtime.mapiterinit
• runtime.mapiternext

但你可能會想，明明用的是 for range 進行循環(huán)迭代，怎么出現(xiàn)了這兩個函數(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 
} 

實際上編譯器對于 slice 和 map 的循環(huán)迭代有不同的實現(xiàn)方式，并不是 for 一扔就完事了，還做了一些附加動作進行處理。而上述代碼就是 for range map 在編譯器展開后的偽實現(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) 
} 

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

為什么

咱們關(guān)注到源碼中 fastrand 的部分，這個方法名，是不是迷之眼熟。沒錯，它是一個生成隨機數(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 

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

因此每次重新 for range map，你見到的結(jié)果都是不一樣的。那是因為它的起始位置根本就不固定!

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 進行具體的循環(huán)遍歷動作。該方法主要涉及如下：

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

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

總結(jié)

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

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

你想問為什么要這么做?

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

因此，改之。也請不要依賴...

參考

• Go maps in action