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

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

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

簡(jiǎn)介

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

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

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

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

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

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

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

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

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

Map 的存與取

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

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

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

底層代碼

func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
    // map 為空,或者元素?cái)?shù)為 0,直接返回未找到
    if h == nil || h.count == 0 {
        return unsafe.Pointer(&zeroVal[0]), false
    }
    // 不支持并發(fā)讀寫(xiě)
    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 非空時(shí),說(shuō)明 map 發(fā)生了擴(kuò)容
    // 這時(shí)候,新的 buckets 里可能還沒(méi)有老的內(nèi)容
    // 所以一定要在老的里面找,否則有可能發(fā)生“消失”的詭異現(xiàn)象
    if c := h.oldbuckets; c != nil {
        if !h.sameSizeGrow() {
            // 說(shuō)明之前只有一半的 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)
    // 一個(gè) bucket 在存儲(chǔ)滿 8 個(gè)元素后,就再也放不下了,這時(shí)候會(huì)創(chuàng)建新的 bucket,掛在原來(lái)的 bucket 的 overflow 指針成員上
    // 遍歷當(dāng)前bucket的所有鏈?zhǔn)絙ucket
    for ; b != nil; b = b.overflow(t) {
        // 在bucket的8個(gè)位置上查詢
        for i := uintptr(0); i < bucketCnt; i++ {
            // 如果找到了相等的 tophash,那說(shuō)明就是這個(gè) 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))
            }
            // 校驗(yàn)找到的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 都沒(méi)有找到,返回零值和 false
    return unsafe.Pointer(&zeroVal[0]), false
}

尋址過(guò)程

Map 的擴(kuò)容

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

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

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

第一種情況

第二種情況

Map的有序性

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

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

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

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

不難看出,即使不對(duì) map 進(jìn)行擴(kuò)容,在多次遍歷時(shí)也是無(wú)序的,這是因?yàn)?golang 官方在設(shè)計(jì)時(shí)故意加上隨機(jī)的元素,將遍歷 map 的順序隨機(jī)化,用來(lái)防止使用者用來(lái)順序遍歷。

而這是有風(fēng)險(xiǎn)的代碼,在 GO 的嚴(yán)格語(yǔ)法規(guī)則下,是堅(jiān)決不提倡的。所以我們?cè)谑褂?map 時(shí)一定要記得其是無(wú)序的,不要依賴其順序。

Map 的并發(fā)

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

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

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

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

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

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

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

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

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

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

相關(guān)文章

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

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

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

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

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

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

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

    golang使用DockerFile正確用法指南

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

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

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

    Golang WebView跨平臺(tái)的桌面應(yīng)用庫(kù)的使用

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

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

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

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

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

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

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

    深入理解Go語(yǔ)言中的閉包

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

最新評(píng)論