簡(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)文章希望大家以后多多支持腳本之家！

最新評(píng)論