国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

為什么遍歷 Go map 是無序的?

Hanks10100 / 1295人閱讀

摘要:有人說因為是哈希的所以就是無亂序等等說法。沒錯,它是一個生成隨機數的方法。更具體的話就是根據隨機數,選擇一個桶位置作為起始點進行遍歷迭代因此每次重新,你見到的結果都是不一樣的。

有的小伙伴沒留意過 Go map 輸出順序,以為它是穩定的有序的;有的小伙伴知道是無序的,但卻不知道為什么?有的卻理解錯誤?今天我們將通過本文,揭開 for range map 的 “神秘” 面紗,看看它內部實現到底是怎么樣的,輸出順序到底是怎么樣?

原文地址:為什么遍歷 Go 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)
    }
}

假設運行這段代碼,輸出結果是按順序?還是無序輸出呢?

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

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

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

這也是這篇文章出現的原因,希望大家可以一起研討一下,理清這個問題 :)

看一下匯編
    ...
    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_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 的循環迭代有不同的實現方式,并不是 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 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

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

因此每次重新 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 版本迭代遍歷規則都是一樣的。而這將會導致可移植性問題。因此,改之。也請不要依賴...

參考

Go maps in action

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/31182.html

相關文章

  • golang學習筆記(一)——golang基礎和相關數據結構

    摘要:小白前端一枚,最近在研究,記錄自己學習過程中的一些筆記,以及自己的理解。此外,結構體也支持嵌套。在函數聲明時,在函數名前放上一個變量,這個變量稱為方法的接收器,一般是結構體類型的。 小白前端一枚,最近在研究golang,記錄自己學習過程中的一些筆記,以及自己的理解。 go中包的依賴管理 go中的切片 byte 和 string go中的Map go中的struct結構體 go中的方...

    lyning 評論0 收藏0
  • 你確定不來了解下 Redis 跳躍表原理嗎

    摘要:前言本章將介紹中和的基本使用和內部原理因為這兩種數據結構有很多相似的地方所以把他們放到一章中介紹并且重點介紹內部一個很重要的數據結構跳躍表基本介紹先來看看中集合很像中鍵值對無序唯一不為空值重復無序是中最特別的基礎數據結構其他幾個都能和大致對 前言 本章將介紹 Redis中 set 和 zset的基本使用和內部原理.因為這兩種數據結構有很多相似的地方所以把他們放到一章中介紹.并且重點介紹...

    BigTomato 評論0 收藏0
  • 通過面試題,讓我們來了解Collection

    摘要:說一說迭代器通過集合對象獲取其對應的對象判斷是否存在下一個元素取出該元素并將迭代器對象指向下一個元素取出元素的方式迭代器。對于使用容器者而言,具體的實現不重要,只要通過容器獲取到該實現的迭代器的對象即可,也就是方法。 前言 歡迎關注微信公眾號:Coder編程獲取最新原創技術文章和相關免費學習資料,隨時隨地學習技術知識!** 本章主要介紹Collection集合相關知識,結合面試中會提到...

    HelKyle 評論0 收藏0

發表評論

0條評論

最新活動
閱讀需要支付1元查看
<