大家好，我是煎鱼。

最近又有同学问我这个日经话题，想转他文章时，后果发现我的公众号居然没有发过，因而明天我再唠叨两句，好让大家避开这个 “坑”。

有的小伙伴没注意过 Go map 输入、遍历程序，认为它是稳固的有序的，会在业务程序中间接依赖这个后果集程序，后果栽了个大跟头，吃了线上 BUG。

有的小伙伴晓得是无序的，但却不晓得为什么,有的却了解谬误？

明天通过本文，咱们将揭开 for range map 输入的 “神秘” 面纱，看看它外部实现到底是怎么样的，程序到底是怎么样？

开始吸鱼之路。

前言

例子如下：

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

假如运行这段代码，输入的后果是怎么样？是有序，还是无序输入呢？

k: 3, v: EDDYCJY4k: 4, v: EDDYCJY5k: 0, v: EDDYCJY1k: 1, v: EDDYCJY2k: 2, v: EDDYCJY3

从输入后果上来讲，是非固定程序输入的，也就是每次都不一样。但这是为什么呢？

首先倡议你先本人想想起因。其次我在面试时听过一些说法。有人说因为是哈希的所以就是无（乱）序等等说法。过后我是有点 ？？？

这也是这篇文章呈现的起因，心愿大家能够一起研究一下，理清这个问题 ：）

看一下汇编

    ...    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 循环迭代的是两个 runtime 办法，如下：

  • runtime.mapiterinit
  • runtime.mapiternext

但你可能会想，明明用的是 for range 进行循环迭代，怎么呈现了这两个函数，怎么回事？

看一下转换后

var hiter map_iteration_structfor 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 的循环迭代有不同的实现形式，并不是 for 一扔就完事了，还做了一些附加动作进行解决。而上述代码就是 for range map 在编译器开展后的伪实现

看一下源码

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 进行遍历迭代时进行初始化动作。共有三个形参，用于读取以后哈希表的类型信息、以后哈希表的存储信息和以后遍历迭代的数据

为什么

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

...// decide where to startr := 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 stateit.bucket = it.startBucket

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

因而每次从新 for range map，你见到的后果都是不一样的。那是因为它的起始地位基本就不固定！

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}

在上大节中，咱们曾经选定了起始桶的地位。接下来就是通过 mapiternext 进行具体的循环遍历动作。该办法次要波及如下：

  • 从已选定的桶中开始进行遍历，寻找桶中的下一个元素进行解决
  • 如果桶曾经遍历完，则对溢出桶 overflow buckets 进行遍历解决

通过对本办法的浏览，可得悉其对 buckets 的遍历规定以及对于扩容的一些解决（这不是本文重点。因而没有具体开展）

总结

在本文开始，咱们先提出外围探讨点：“为什么 Go map 遍历输入是不固定程序？”。

通过这一番剖析，起因也很简单明了。就是 for range map 在开始解决循环逻辑的时候，就做了随机收获...

你想问为什么要这么做？

当然是官网无意为之，因为 Go 在晚期（1.0）的时候，虽是稳固迭代的，但从后果来讲，其实是无奈保障每个 Go 版本迭代遍历规定都是一样的。而这将会导致可移植性问题。

因而，改之。也请不要依赖...

若有任何疑难欢送评论区反馈和交换，最好的关系是相互成就，各位的点赞就是煎鱼创作的最大能源，感激反对。

文章继续更新，能够微信搜【脑子进煎鱼了】浏览，回复【000】有我筹备的一线大厂面试算法题解和材料。

本文 GitHub github.com/eddycjy/blog 已收录，欢送 Star 催更。

参考

  • Go maps in action