欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Golang map實現(xiàn)原理深入分析

 更新時間:2023年01月29日 15:56:12   作者:阿拉斯加大閘蟹  
map是一種無序的基于key-value的數(shù)據(jù)結(jié)構(gòu),Go語言中的map是引用類型,必須初始化才能使用,下面這篇文章主要給大家介紹了關(guān)于golang中map使用的幾點注意事項,需要的朋友可以參考下

簡介

本文主要通過探究在golang 中map的數(shù)據(jù)結(jié)構(gòu)及源碼實現(xiàn)來學(xué)習(xí)和了解map的特性,共包含map的模型探究、存取、擴容等內(nèi)容。歡迎大家共同討論。

Map 的底層內(nèi)存模型

在 goland 的源碼中表示 map 的底層 struct 是 hmap,其是 hashmap 的縮寫

type hmap struct {
   // map中存入元素的個數(shù), golang中調(diào)用len(map)的時候直接返回該字段
   count     int
   // 狀態(tài)標(biāo)記位,通過與定義的枚舉值進(jìn)行&操作可以判斷當(dāng)前是否處于這種狀態(tài)
   flags     uint8
   B         uint8  // 2^B 表示bucket的數(shù)量, B 表示取hash后多少位來做bucket的分組
   noverflow uint16 // overflow bucket 的數(shù)量的近似數(shù)
   hash0     uint32 // hash seed (hash 種子) 一般是一個素數(shù)
   buckets    unsafe.Pointer // 共有2^B個 bucket ,但是如果沒有元素存入,這個字段可能為nil
   oldbuckets unsafe.Pointer // 在擴容期間,將舊的bucket數(shù)組放在這里, 新buckets會是這個的兩倍大
   nevacuate  uintptr        // 表示已經(jīng)完成擴容遷移的bucket的指針, 地址小于當(dāng)前指針的bucket已經(jīng)遷移完成
   extra *mapextra // optional fields
}

B 是 buckets 數(shù)組的長度的對數(shù), 即 bucket 數(shù)組的長度是 2^B。bucket 的本質(zhì)上是一個指針,指向了一片內(nèi)存空間,其指向的 struct 如下所示:

// A bucket for a Go map.
type bmap struct {
   tophash [bucketCnt]uint8
}

但這只是表面(src/runtime/hashmap.go)的結(jié)構(gòu),編譯期間會給它加料,動態(tài)地創(chuàng)建一個新的結(jié)構(gòu):

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr        // 內(nèi)存對齊使用,可能不需要
    overflow uintptr        // 當(dāng)bucket 的8個key 存滿了之后
}

bmap 就是我們常說的“桶”的底層數(shù)據(jù)結(jié)構(gòu), 一個桶中可以存放最多 8 個 key/value, map 使用 hash 函數(shù) 得到 hash 值決定分配到哪個桶, 然后又會根據(jù) hash 值的高 8 位來尋找放在桶的哪個位置 具體的 map 的組成結(jié)構(gòu)如下圖所示:

Map 的存與取

在 map 中存與取本質(zhì)上都是在進(jìn)行一個工作, 那就是:

查詢當(dāng)前 k/v 應(yīng)該存儲的位置。

賦值/取值, 所以我們理解了 map 中 key 的定位我們就理解了存取。

底層代碼

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // map 為空,或者元素數(shù)為 0,直接返回未找到
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0]), false
    }
    // 不支持并發(fā)讀寫
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }
    // 根據(jù)hash 函數(shù)算出hash值,注意key的類型不同可能使用的hash函數(shù)也不同
    hash := t.hasher(key, uintptr(h.hash0))
    // 如果 B = 5,那么結(jié)果用二進(jìn)制表示就是 11111 , 返回的是B位全1的值
    m := bucketMask(h.B)
    // 根據(jù)hash的后B位,定位在bucket數(shù)組中的位置
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))
    // 當(dāng) h.oldbuckets 非空時,說明 map 發(fā)生了擴容
    // 這時候,新的 buckets 里可能還沒有老的內(nèi)容
    // 所以一定要在老的里面找,否則有可能發(fā)生“消失”的詭異現(xiàn)象
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            // 說明之前只有一半的 bucket,需要除 2
            m >>= 1
        }
        oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
        if !evacuated(oldb) {
            b = oldb
        }
    }
    // tophash 取其高 8bit 的值
    top := tophash(hash)
    // 一個 bucket 在存儲滿 8 個元素后,就再也放不下了,這時候會創(chuàng)建新的 bucket,掛在原來的 bucket 的 overflow 指針成員上
    // 遍歷當(dāng)前bucket的所有鏈?zhǔn)絙ucket
    for ; b != nil; b = b.overflow(t) {
        // 在bucket的8個位置上查詢
        for i := uintptr(0); i < bucketCnt; i++ {
            // 如果找到了相等的 tophash,那說明就是這個 bucket 了
            if b.tophash[i] != top {
                continue
            }
            // 根據(jù)內(nèi)存結(jié)構(gòu)定位key的位置
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey {
                k = *((*unsafe.Pointer)(k))
            }
            // 校驗找到的key是否匹配
            if t.key.equal(key, k) {
                // 定位v的位置
                v := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                if t.indirectvalue {
                    v = *((*unsafe.Pointer)(v))
                }
                return v, true
            }
        }
    }
    // 所有 bucket 都沒有找到,返回零值和 false
    return unsafe.Pointer(&zeroVal[0]), false
}

尋址過程

Map 的擴容

在 golang 中 map 和 slice 一樣都是在初始化時首先申請較小的內(nèi)存空間,在 map 的不斷存入的過程中,動態(tài)的進(jìn)行擴容。擴容共有兩種,增量擴容與等量擴容(重新排列并分配內(nèi)存)。下面我們來了解一下擴容的觸發(fā)方式:

負(fù)載因子超過閾值,源碼里定義的閾值是 6.5。(觸發(fā)增量擴容)

overflow 的 bucket 數(shù)量過多:當(dāng) B 小于 15,也就是 bucket 總數(shù) 2^B 小于 2^15 時,如果 overflow 的 bucket 數(shù)量超過 2^B;當(dāng) B >= 15,也就是 bucket 總數(shù) 2^B 大于等于 2^15,如果 overflow 的 bucket 數(shù)量超過 2^15。(觸發(fā)等量擴容)

第一種情況

第二種情況

Map的有序性

先說結(jié)論,在 golang 中 map 是無序的,準(zhǔn)確的說是無法嚴(yán)格保證順序的, 從上面的源碼中我們可以知道,golang 中 map 在擴容后,可能會將部分 key 移至新內(nèi)存,由于在擴容搬移數(shù)據(jù)過程中,并未記錄原數(shù)據(jù)位置, 并且在 golang 的數(shù)據(jù)結(jié)構(gòu)中也并未保存數(shù)據(jù)的順序,所以那么這一部分在擴容后實際上就已經(jīng)是無序的了。

遍歷的過程,其實就是按順序遍歷內(nèi)存地址,同時按順序遍歷內(nèi)存地址中的 key。但這時已經(jīng)是無序的了。但是如果我就一個 map,我保證不會對 map 進(jìn)行修改刪除等操作,那么按理說沒有擴容就不會發(fā)生改變。但也是因為這樣,GO 才在源碼中 但是有一個有趣的現(xiàn)象,就算不對 map 進(jìn)行插入刪除等操作致使其擴容,其在遍歷過程中仍是無序的。

objMap := make(map[string]int)
for i := 0; i < 5; i++ {
   objMap[strconv.Itoa(i)] = i
}
for i := 0 ; i < 5; i ++ {
   var valStr1, valStr2 string
   for k, v := range objMap {
      fmt.Println(k)
      fmt.Println(v)
      valStr1 += k
   }
   for k, v := range objMap {
      fmt.Println(k)
      fmt.Println(v)
      valStr2 += k
   }
   fmt.Println(valStr1 == valStr2)
   if valStr1 != valStr2 {
      fmt.Println("not equal")
   }
}
fmt.Println("end")

以上的運行結(jié)果是

不難看出,即使不對 map 進(jìn)行擴容,在多次遍歷時也是無序的,這是因為 golang 官方在設(shè)計時故意加上隨機的元素,將遍歷 map 的順序隨機化,用來防止使用者用來順序遍歷。

而這是有風(fēng)險的代碼,在 GO 的嚴(yán)格語法規(guī)則下,是堅決不提倡的。所以我們在使用 map 時一定要記得其是無序的,不要依賴其順序。

Map 的并發(fā)

首先我們大家都知道,在 golang 中 map 并不是一個并發(fā)安全的數(shù)據(jù)結(jié)構(gòu),當(dāng)幾個 goruotine 同時對一個 map 進(jìn)行讀寫操作時,就會出現(xiàn)并發(fā)寫問題:fatal error: concurrent map writes。但是為什么 map 是不支持并發(fā)安全的呢, 主要是因為成本與效益。

官方答復(fù)原因如下:

  • 典型使用場景:map 的典型使用場景是不需要從多個 goroutine 中進(jìn)行安全訪問。
  • 非典型場景(需要原子操作):map 可能是一些更大的數(shù)據(jù)結(jié)構(gòu)或已經(jīng)同步的計算的一部分。

性能場景考慮:若是只是為少數(shù)程序增加安全性,導(dǎo)致 map 所有的操作都要處理 mutex,將會降低大多數(shù)程序的性能。同時 golang 提供了并發(fā)安全的 sync map。

// 不支持并發(fā)讀寫
    if h.flags&hashWriting != 0 {
        throw("concurrent map read and map write")
    }

但是我們又有疑問了,為什么 golang map 并發(fā)沖突了不拋一個 error 出來,或者 panic 掉,而是要讓程序 panic,選擇讓程序 crash 崩潰掉。這里是 golang 官方出于權(quán)衡風(fēng)險和 map 使用復(fù)雜度場景考慮的,首先 map 在官方中就明確表示不支持并發(fā)讀寫, 所以并發(fā)對 map 進(jìn)行讀寫操作本身就是不正確的。

場景假設(shè)一:如果 map 選擇在寫入或者讀取時增加 error 返回值,會導(dǎo)致程序在使用 map 時就無法像現(xiàn)在一樣,需要額外的捕獲并判斷 err。

場景假設(shè)二:如果 map 選擇 panic(可被 recover),此時如果出現(xiàn)并發(fā)寫入數(shù)據(jù)的場景,就會導(dǎo)致走進(jìn) recover 中,如果沒有對這種場景進(jìn)行特殊處理,就會導(dǎo)致 map 中存在臟數(shù)據(jù),此時程序在使用 map 時就會引發(fā)不可預(yù)知的錯誤,此時排查起來也是很難找到問題的根因的。

所以 golang 在考慮了這些場景后,選擇明確的拋出 crash 崩潰異常,使得風(fēng)險被提前暴露??梢悦鞔_的定位到問題點。綜上所述我們在使用 map 時,已經(jīng)要嚴(yán)格保障其是在單線程內(nèi)使用的,如果有多線程場景,建議使用 sync map

到此這篇關(guān)于Golang map實現(xiàn)原理深入分析的文章就介紹到這了,更多相關(guān)Golang map內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!

相關(guān)文章

  • Go 實現(xiàn)百萬WebSocket連接的方法示例

    Go 實現(xiàn)百萬WebSocket連接的方法示例

    這篇文章主要介紹了Go 實現(xiàn)百萬WebSocket連接的方法示例,文中通過示例代碼介紹的非常詳細(xì),對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-08-08
  • 談?wù)凣o語言的反射三定律

    談?wù)凣o語言的反射三定律

    本文中,我們將解釋Go語言中反射的運作機制。每個編程語言的反射模型不大相同,很多語言索性就不支持反射(C、C++)。由于本文是介紹Go語言的,所以當(dāng)我們談到“反射”時,默認(rèn)為是Go語言中的反射。
    2016-08-08
  • Golang中的包及包管理工具go?mod詳解

    Golang中的包及包管理工具go?mod詳解

    這篇文章主要介紹了Golang中的包及包管理工具go?mod,本文給大家介紹的非常詳細(xì),對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值,需要的朋友可以參考下
    2022-07-07
  • golang使用DockerFile正確用法指南

    golang使用DockerFile正確用法指南

    docker在開發(fā)和運維中使用的場景越來越多,作為開發(fā)人員非常有必要了解一些docker的基本知識,而離我們工作中最近的也就是對應(yīng)用的docker部署編排了,這篇文章主要給大家介紹了關(guān)于golang使用DockerFile的正確用法指南,需要的朋友可以參考下
    2024-03-03
  • go語言切片slice使用細(xì)節(jié)和注意事項整理大全

    go語言切片slice使用細(xì)節(jié)和注意事項整理大全

    這篇文章主要給大家介紹了關(guān)于go語言切片slice使用細(xì)節(jié)和注意事項整理的相關(guān)資料,需要的朋友可以參考下
    2024-05-05
  • Golang WebView跨平臺的桌面應(yīng)用庫的使用

    Golang WebView跨平臺的桌面應(yīng)用庫的使用

    Golang WebView是一個強大的桌面應(yīng)用庫,本文介紹了Golang WebView的特點和使用方法,并列舉示例詳細(xì)的介紹了其在實際項目中的應(yīng)用,具有一定的參考價值,感興趣的可以了解一下
    2024-03-03
  • Go工具鏈之go tool cover使用方法和示例詳解

    Go工具鏈之go tool cover使用方法和示例詳解

    go tool cover是Go工具鏈中的一個命令,作用是分析測試用例的代碼覆蓋率,本文將對go tool cover 作用,使用方法和使用場景作一個簡單的介紹,感興趣的同學(xué)可以參考閱讀一下
    2023-07-07
  • 定位并修復(fù) Go 中的內(nèi)存泄露問題

    定位并修復(fù) Go 中的內(nèi)存泄露問題

    Go 是一門帶 GC 的語言,這篇文章回顧了我如何發(fā)現(xiàn)內(nèi)存泄漏、如何修復(fù)它,以及我如何修復(fù) Google 示例 Go 代碼中的類似問題,以及我們?nèi)绾胃倪M(jìn)我們的庫以防止將來發(fā)生這種情況,感興趣的朋友一起看看吧
    2021-10-10
  • golang通過遞歸遍歷生成樹狀結(jié)構(gòu)的操作

    golang通過遞歸遍歷生成樹狀結(jié)構(gòu)的操作

    這篇文章主要介紹了golang通過遞歸遍歷生成樹狀結(jié)構(gòu)的操作,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2021-04-04
  • 深入理解Go語言中的閉包

    深入理解Go語言中的閉包

    Go函數(shù)是可以閉包的。閉包是一個函數(shù)值,他來自函數(shù)體外部的變量引用。 下面這篇文章通過一個demo來進(jìn)行深入的介紹了Go語言中閉包的相關(guān)資料,文中介紹的非常詳細(xì),需要的朋友可以參考下。
    2017-03-03

最新評論