go map數據結構和源碼詳解

来源:https://www.cnblogs.com/JoZSM/archive/2019/11/02/11784037.html
-Advertisement-
Play Games

[TOC] 1. 前言 本文以go1.12.5版本分析，map相關的源碼在runtime包的map開頭的幾個文件中，主要為map.go。 go的map底層實現方式是hash表（C++的map是紅黑樹實現，而C++ 11新增的unordered_map則與go的map類似，都是hash實現）。go m ...


目錄

1. 前言

本文以go1.12.5版本分析，map相關的源碼在runtime包的map開頭的幾個文件中，主要為map.go。
go的map底層實現方式是hash表（C++的map是紅黑樹實現，而C++ 11新增的unordered_map則與go的map類似，都是hash實現）。go map的數據被置入一個由桶組成的有序數組中，每個桶最多可以存放8個key/value對。key的hash值(32位)的低階位用於在該數組中定位到桶，而高8位則用於在桶中區分key/value對。
go map的hash表中的基本單位是桶，每個桶最多存8個鍵值對，超了，則會鏈接到額外的溢出桶。所以go map是基本數據結構是hash數組+桶內的key-value數組+溢出的桶鏈表
當hash表超過閾值需要擴容增長時，會分配一個新的數組，新數組的大小一般是舊數組的2倍。這裡從舊數組將數據遷移到新數組，不會一次全量拷貝，go會在每次讀寫Map時以桶為單位做動態搬遷疏散。

2. go map的數據結構

我們先瞭解基本的數據結構，後面再看源碼就簡單多了。

2.1 核心結體體

map主要由兩個核心的結構，即基礎結構和桶實現：

  • hmap：map的基礎結構
  • bmap：嚴格來說hmap.buckets指向桶組成的數組，每個桶的頭部是bmap，之後是8個key，再是8個value，最後是1個溢出指針。溢出指針指向額外的桶鏈表，用於存儲溢出的數據
const ( // 關鍵的變數
    bucketCntBits = 3
    bucketCnt     = 1 << bucketCntBits  // 一個桶最多存儲8個key-value對
    loadFactorNum = 13 // 擴散因數：loadFactorNum / loadFactorDen = 6.5。
    loadFactorDen = 2  // 即元素數量 >= (hash桶數量(2^hmp.B) * 6.5 / 8) 時，觸發擴容
)
// map的基礎數據結構
type hmap struct {
    count     int    // map存儲的元素對計數，len()函數返回此值，所以map的len()時間複雜度是O(1)
    flags     uint8  // 記錄幾個特殊的位標記，如當前是否有別的線程正在寫map、當前是否為相同大小的增長（擴容/縮容？）
    B         uint8  // hash桶buckets的數量為2^B個
    noverflow uint16 // 溢出的桶的數量的近似值
    hash0     uint32 // hash種子

    buckets    unsafe.Pointer // 指向2^B個桶組成的數組的指針，數據存在這裡
    oldbuckets unsafe.Pointer // 指向擴容前的舊buckets數組，只在map增長時有效
    nevacuate  uintptr        // 計數器，標示擴容後搬遷的進度

    extra *mapextra // 保存溢出桶的鏈表和未使用的溢出桶數組的首地址
}

// 桶的實現結構
type bmap struct {
    // tophash存儲桶內每個key的hash值的高位元組
    // tophash[0] < minTopHash表示桶的疏散狀態
    // 當前版本bucketCnt的值是8，一個桶最多存儲8個key-value對
    tophash [bucketCnt]uint8
    // 特別註意：
    // 實際分配記憶體時會申請一個更大的記憶體空間A，A的前8位元組為bmap
    // 後面依次跟8個key、8個value、1個溢出指針
    // map的桶結構實際指的是記憶體空間A
}

// map.go里很多函數的第1個入參是這個結構，從成員來看很明顯，此結構標示了鍵值對和桶的大小等必要信息
// 有了這個結構的信息，map.go的代碼就可以與鍵值對的具體數據類型解耦
// 所以map.go用記憶體偏移量和unsafe.Pointer指針來直接對記憶體進行存取，而無需關心key或value的具體類型
type maptype struct {
    typ        _type
    key        *_type
    elem       *_type
    bucket     *_type // internal type representing a hash bucket
    keysize    uint8  // size of key slot
    valuesize  uint8  // size of value slot
    bucketsize uint16 // size of bucket
    flags      uint32
}

C++使用模板可以根據不同的類型生成map的代碼。
golang則通過上述maptype結構體傳遞鍵值對的類型大小等信息，從而map.go直接用指針操作對應大小的記憶體來實現全局一份map代碼同時適用於不同類型的鍵值對。這點上可以認為相比C++用模板實現map的方式，go map的目標文件的代碼量會更小。

2.2 數據結構圖

map底層創建時，會初始化一個hmap結構體，同時分配一個足夠大的記憶體空間A。其中A的前段用於hash數組，A的後段預留給溢出的桶。於是hmap.buckets指向hash數組，即A的首地址；hmap.extra.nextOverflow初始時指向記憶體A中的後段，即hash數組結尾的下一個桶，也即第1個預留的溢出桶。所以當hash衝突需要使用到新的溢出桶時，會優先使用上述預留的溢出桶，hmap.extra.nextOverflow依次往後偏移直到用完所有的溢出桶，才有可能會申請新的溢出桶空間。

上圖中，當需要分配一個溢出桶時，會優先從預留的溢出桶數組裡取一個出來鏈接到鏈表後面，這時不需要再次申請記憶體。但當預留的桶被用完了，則需要申請新的記憶體給溢出桶。

3. go map的常用操作

3.1 創建

使用make(map[k]v, hint)創建map時會調用makemap()函數，代碼邏輯比較簡單。
值得註意的是，makemap()創建的hash數組，數組的前面是hash表的空間，當hint >= 4時後面會追加2^(hint-4)個桶，之後再記憶體頁幀對齊又追加了若幹個桶（參見2.2章節結構圖的hash數組部分）
所以創建map時一次記憶體分配既分配了用戶預期大小的hash數組，又追加了一定量的預留的溢出桶，還做了記憶體對齊，一舉多得。

// make(map[k]v, hint), hint即預分配大小
// 不傳hint時，如用new創建個預設容量為0的map時，makemap只初始化hmap結構，不分配hash數組
func makemap(t *maptype, hint int, h *hmap) *hmap {
    // 省略部分代碼
    // 隨機hash種子
    h.hash0 = fastrand()

    // 2^h.B 為大於hint*6.5(擴容因數)的最小的2的冪
    B := uint8(0)
    // overLoadFactor(hint, B)只有一行代碼：return hint > bucketCnt && uintptr(hint) > loadFactorNum*(bucketShift(B)/loadFactorDen)
    // 即B的大小應滿足 hint <= (2^B) * 6.5
    // 一個桶能存8對key-value，所以這就表示B的初始值是保證這個map不需要擴容即可存下hint個元素對的最小的B值
    for overLoadFactor(hint, B) {
        B++
    }
    h.B = B

    // 這裡分配hash數組
    if h.B != 0 {
        var nextOverflow *bmap
        h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
        // makeBucketArray()會在hash數組後面預分配一些溢出桶，
        // h.extra.nextOverflow用來保存上述溢出桶的首地址
        if nextOverflow != nil {
            h.extra = new(mapextra)
            h.extra.nextOverflow = nextOverflow
        }
    }

    return h
}

// 分配hash數組
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
    base := bucketShift(b) // base代表用戶預期的桶的數量，即hash數組的真實大小
    nbuckets := base // nbuckets表示實際分配的桶的數量，>= base，這就可能會追加一些溢出桶作為溢出的預留
    if b >= 4 {
        // 這裡追加一定數量的桶，並做記憶體對齊
        nbuckets += bucketShift(b - 4)
        sz := t.bucket.size * nbuckets
        up := roundupsize(sz)
        if up != sz {
            nbuckets = up / t.bucket.size
        }
    }

    // 後面的代碼就是申請記憶體空間了，此處省略
    // 這裡大家可以思考下這個數組空間要怎麼分配，其實就是n*sizeof(桶)，所以：
        // 每個桶前面是8位元組的tophash數組，然後是8個key，再是8個value，最後放一個溢出指針
        // sizeof(桶) = 8 + 8*sizeof(key) + 8*sizeof(value) + 8
    
    return buckets, nextOverflow
}

3.2 插入或更新

go map的插入操作，調用mapassign()函數。
同學們或許在某些資料上瞭解過：

  • go map需要初始化才能使用，對空map插入會panic。hmap指針傳遞的方式，決定了map在使用前必須初始化
  • go map不支持併發讀寫，會panic。如果一定要併發，請用sync.Map或自己解決衝突

上述兩個限制，在mapassign()函數開頭能找到答案：

  1. 參數合法性檢測，計算hash值
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // 不熟悉指針操作的同學，用指針傳參往往會踩空指針的坑
    // 這裡大家可以思考下，為什麼h要非空判斷？
    // 如果一定要在這裡支持空map並檢測到map為空時自動初始化，應該怎麼寫？
    // 提示：指針的指針
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    // 在這裡做併發判斷，檢測到併發寫時，拋異常
    // 註意：go map的併發檢測是偽檢測，並不保證所有的併發都會被檢測出來。而且這玩意是在運行期檢測。
    // 所以對map有併發要求時，應使用sync.map來代替普通map，通過加鎖來阻斷併發衝突
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    hash := alg.hash(key, uintptr(h.hash0)) // 這裡得到uint32的hash值
    h.flags ^= hashWriting // 置Writing標誌，key寫入buckets後才會清除標誌
    if h.buckets == nil { // map不能為空，但hash數組可以初始是空的，這裡會初始化
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }
    
    ...
}
  1. 定位key在hash表中的位置
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
again:
    bucket := hash & bucketMask(h.B) // 這裡用hash值的低階位定位hash數組的下標偏移量
    if h.growing() {
        growWork(t, h, bucket) // 這裡是map的擴容縮容操作，我們在第4章單獨講
    }
    // 通過下標bucket，偏移定位到具體的桶
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
    top := tophash(hash) // 這裡取高8位用於在桶內定位鍵值對
    
    ...
}
  1. 進一步定位key可以插入的桶及桶中的位置
  • 兩輪迴圈，外層迴圈遍歷hash桶及其指向的溢出鏈表，內層迴圈則在桶內遍歷（一個桶最多8個key-value對）
  • 有可能正好鏈表上的桶都滿了，這時inserti為nil，第4步會鏈接一個新的溢出桶進來
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...

    var inserti *uint8          // tophash插入位置
    var insertk unsafe.Pointer  // key插入位置
    var val unsafe.Pointer      // value插入位置
bucketloop:
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if isEmpty(b.tophash[i]) && inserti == nil {
                    // 找到個空位，先記錄下tophash、key、value的插入位置
                    // 但要遍歷完才能確定要不要插入到這個位置，因為後面有可能有重覆的元素
                    inserti = &b.tophash[i]
                    insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
                    val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
                }
                if b.tophash[i] == emptyRest {
                    break bucketloop // 遍歷完整個溢出鏈表，退出迴圈
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            if !alg.equal(key, k) {
                continue
            }
            // 走到這裡說明map里找到一個重覆的key，更新key-value，跳到第5步
            if t.needkeyupdate() {
                typedmemmove(t.key, k, key)
            }
            val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            goto done // 更新Key後跳到第5步
        }
        ovf := b.overflow(t)
        if ovf == nil {
            break // 遍歷完整個溢出鏈表，沒找到能插入的空位，結束迴圈，下一步再追加一個溢出桶進來
        }
        b = ovf // 繼續遍歷下一個溢出桶
    }

    ...
}
  1. 插入key
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    // 這裡判斷要不要擴容，我們第4章再講
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }

    if inserti == nil { // inserti == nil說明上1步沒找到空位，整個鏈表是滿的，這裡添加一個新的溢出桶上去
        newb := h.newoverflow(t, b) // 分配新溢出桶，優先用3.1章節預留的溢出桶，用完了則分配一個新桶記憶體
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        val = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    // 當key或value的類型大小超過一定值時，桶只存儲key或value的指針。這裡分配空間並取指針
    if t.indirectkey() {
        kmem := newobject(t.key)
        *(*unsafe.Pointer)(insertk) = kmem
        insertk = kmem
    }
    if t.indirectvalue() {
        vmem := newobject(t.elem)
        *(*unsafe.Pointer)(val) = vmem
    }
    typedmemmove(t.key, insertk, key) // 在桶中對應位置插入key
    *inserti = top // 插入tophash，hash值高8位
    h.count++ // 插入了新的鍵值對，h.count數量+1

    ...
}
  1. 結束插入
 func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
 done:
    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting // 釋放hashWriting標誌位
    if t.indirectvalue() {
        val = *((*unsafe.Pointer)(val))
    }
    return val // 返回value可插入位置的指針，註意，value還沒插入
}
  • 只插入了tophash和key，就結束了嗎？value還沒插入呢
  • 是的，mapassign()只插入tophash和key，並返回val指針，編譯器會在調用mapassign()後用彙編往val插入value
  • google大佬這麼騷氣的操作，是為了減少value值傳遞的次數嗎？

3.3 刪除

  1. 刪除與插入類似，前面的步驟都是參數和狀態判斷、定位key-value位置，然後clear對應的記憶體。不展開說。以下是幾個關鍵點：
  • 刪除過程中也會置hashWriting標誌
  • 當key/value過大時，hash表裡存儲的是指針，這時候用軟刪除，置指針為nil，數據交給gc去刪。當然，這是map的內部處理，外層是無感知的，拿到的都是值拷貝
  • 無論Key/value是值類型還是指針類型，刪除操作都隻影響hash表，外層已經拿到的數據不受影響。尤其是指針類型，外層的指針還能繼續使用
  1. 由於定位key位置的方式是查找tophash，所以刪除操作對tophash的處理是關鍵：
  • map首先將對應位置的tophash[i]置為emptyOne，表示該位置已被刪除
  • 如果tophash[i]不是整個鏈表的最後一個，則只置emptyOne標誌，該位置被刪除但未釋放，後續插入操作不能使用此位置
  • 如果tophash[i]是鏈表最後一個有效節點了，則把鏈表最後面的所有標誌為emptyOne的位置，都置為emptyRest。置為emptyRest的位置可以在後續的插入操作中被使用。
  • 這種刪除方式，以少量空間來避免桶鏈表和桶內的數據移動。事實上，go 數據一旦被插入到桶的確切位置，map是不會再移動該數據在桶中的位置了。
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    ...

            b.tophash[i] = emptyOne // 先標記刪除
            // 如果b.tophash[i]不是最後一個元素，則暫時先占著坑。emptyOne標記的位置暫時不能被插入新元素(見3.2章節插入函數)
            if i == bucketCnt-1 {
                if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
                    goto notLast
                }
            } else {
                if b.tophash[i+1] != emptyRest {
                    goto notLast
                }
            }
            for { // 如果b.tophash[i]是最後一個元素，則把末尾的emptyOne全部清除置為emptyRest
                b.tophash[i] = emptyRest
                if i == 0 {
                    if b == bOrig {
                        break // beginning of initial bucket, we're done.
                    }
                    // Find previous bucket, continue at its last entry.
                    c := b
                    for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
                    }
                    i = bucketCnt - 1
                } else {
                    i--
                }
                if b.tophash[i] != emptyOne {
                    break
                }
            }

    ...
}

3.4 查找

查找操作由mapaccess開頭的一組函數實現。前面的章節在插入和刪除之前都得先定位查找到元素，邏輯是類似的，也比較簡單，就不細說了：

  • mapaccess1()：通過Key查找，返回value指針，用於val := map[key]。未找到時返回value類型的0值。
  • mapaccess2()：通過key查找，返回value指針，以及bool類型的是否查找成功的標誌，用於val, ok := map[key]。未找到時返回value類型的0值。
  • mapaccessK()：通過key查找，返回key和value指針，用於迭代器(range)。未找到時返回空指針
  • mapaccess1_fat()，對mapaccess1()的封裝，區別是mapaccess1_fat()多了個zero參數，未找到時返回zero
  • mapaccess2_fat()，也是對mapaccess1()的封裝。相比mapaccess1_fat()，本函數增加一個是否查找成功的標誌

3.5 range迭代

map的迭代是通過hiter結構和對應的兩個輔助函數實現的。hiter結構由編譯器在調用輔助函數之前創建並傳入，每次迭代結果也由hiter結構傳回。下方的it即是hiter結構體的指針變數。

3.5.1 初始化迭代器mapiterinit()

mapiterinit()函數主要是決定我們從哪個位置開始迭代，為什麼是從哪個位置，而不是直接從hash數組頭部開始呢？《go程式設計語言》好像提到過，hash表中數據每次插入的位置是變化的（其實是因為實現的原因，一方面hash種子是隨機的，這導致相同的數據在不同的map變數內的hash值不同；另一方面即使同一個map變數內，數據刪除再添加的位置也有可能變化，因為在同一個桶及溢出鏈表中數據的位置不分先後），所以為了防止用戶錯誤的依賴於每次迭代的順序，map作者乾脆讓相同的map每次迭代的順序也是隨機的。
迭代順序隨機的實現方式也簡單，直接從隨機的一個位置開始就行了：

  • it.startBucket：這個是hash數組的偏移量，表示遍歷從這個桶開始
  • it.offset：這個是桶內的偏移量，表示每個桶的遍歷都從這個偏移量開始

於是，map的遍歷過程如下：

  • 從hash數組中第it.startBucket個桶開始，先遍歷hash桶，然後是這個桶的溢出鏈表。
  • 之後hash數組偏移量+1，繼續前一步動作。
  • 遍歷每一個桶，無論是hash桶還是溢出桶，都從it.offset偏移量開始。（如果只是隨機一個開始的桶，range結果還是有序的；但每個桶都加it.offset偏移，這個輸出結果就有點撲朔迷離，大家可以親手試下，對同一個map多次range）
  • 當迭代器經過一輪迴圈回到it.startBucket的位置，結束遍歷。
func mapiterinit(t *maptype, h *hmap, it *hiter) {
    ...
    
    // 隨機一個偏移量來開始
    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))
    
    ...
    
    mapiternext(it) // 初始化迭代器的同時也返回第1對key/value
}

3.5.2 迭代過程mapiternext()

上一節迭代迴圈的過程很清晰了，這裡我們說明幾個重要的參數：

  • it.startBucket：開始的桶
  • it.offset：每個桶開始的偏移量
  • it.bptr：當前遍歷的桶
  • it.i：it.bptr已經遍歷的鍵值對數量，i初始為0，當i=8時表示這個桶遍歷完了，將it.bptr移向下一個桶
  • it.key：每次迭代的結果
  • it.value：每次迭代的結果

此外，迭代還需要關註擴容縮容的情況：

  • 如果是在迭代開始後才growing，這種情況當前的邏輯沒處理，迭代有可能異常。呃，go map不支持併發。
  • 如果是先growing，再開始迭代，這是有可能的。這種情況下，會先到舊hash表中檢查key對應的桶有沒有被疏散，未疏散則遍歷舊桶，已疏散則遍歷新hash表裡對應的桶。

4. go map的擴容縮容

4.1 擴容縮容的基本原理

go map的擴容縮容都是grow相關的函數，這裡擴容是真的，縮容是偽縮容，後面我會解釋。我們先看下觸發條件：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    ...
    
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again // Growing the table invalidates everything, so try again
    }
    
    ...
}

// overLoadFactor()返回true則觸發擴容，即map的count大於hash桶數量(2^B)*6.5
func overLoadFactor(count int, B uint8) bool {
    return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// tooManyOverflowBuckets()，顧名思義，溢出桶太多了觸發縮容
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
    if B > 15 {
        B = 15
    }
    return noverflow >= uint16(1)<<(B&15)
}

map只在插入元素即mapassign()函數中對是否擴容縮容進行觸發，條件即是上面這段代碼：

  • 條件1：當前不處在growing狀態
  • 條件2-1：觸發擴容：map的數據量count大於hash桶數量(2^B)*6.5。註意這裡的(2^B)只是hash數組大小，不包括溢出的桶
  • 條件2-2：觸發縮容：溢出的桶數量noverflow>=32768(1<<15)或者>=hash數組大小。

仔細觀察觸發的代碼，擴容和縮容是同一個函數，這是怎麼做到的呢？在hashGrow()開始，會先判斷是否滿足擴容條件，如果滿足就表明這次是擴容，不滿足就一定是縮容條件觸發了。擴容和縮容剩下的邏輯，主要區別就在於容量變化，就是hmap.B參數，擴容時B+1則hash表容量擴大1倍，縮容時hash表容量不變。

  • h.oldbuckets：指向舊的hash數組，即當前的h.buckets
  • h.buckets：指向新創建的hash數組

到這裡觸發的主要工作已經完成，接下來就是怎麼把元素搬遷到新hash表裡了。如果現在就一次全量搬遷過去，顯然接下來會有比較長的一段時間map被占用（不支持併發）。所以搬遷的工作是非同步增量搬遷的。
在插入和刪除的函數內都有下麵一段代碼用於在每次插入和刪除操作時，執行一次搬遷工作：

    if h.growing() { // 當前處於搬遷狀態
        growWork(t, h, bucket) // 調用搬遷函數
    }
    
func growWork(t *maptype, h *hmap, bucket uintptr) {
    // 將當前需要處理的桶搬遷
    evacuate(t, h, bucket&h.oldbucketmask())

    if h.growing() { // 再多搬遷一個桶
        evacuate(t, h, h.nevacuate)
    }
}
  • 每執行一次插入或刪除，都會調用growWork搬遷0~2個hash桶（有可能這次需要搬遷的2個桶在此之前都被搬過了）
  • 搬遷是以hash桶為單位的，包含對應的hash桶和這個桶的溢出鏈表
  • 被delete掉的元素(emptyone標誌)會被捨棄（這是縮容的關鍵）

4.2 為什麼叫“偽縮容”？如何實現“真縮容”？

現在可以解釋為什麼我把map的縮容叫做偽縮容了：因為縮容僅僅針對溢出桶太多的情況，觸發縮容時hash數組的大小不變，即hash數組所占用的空間只增不減。也就是說，如果我們把一個已經增長到很大的map的元素挨個全部刪除掉，hash表所占用的記憶體空間也不會被釋放。

所以如果要實現“真縮容”，需自己實現縮容搬遷，即創建一個較小的map，將需要縮容的map的元素挨個搬遷過來：

// go map縮容代碼示例
myMap := make(map[int]int, 1000000)

// 假設這裡我們對bigMap做了很多次插入，之後又做了很多次刪除，此時bigMap的元素數量遠小於hash表大小
// 接下來我們開始縮容
smallMap := make(map[int]int, len(myMap))
for k, v := range myMap {
    smallMap[k] = v
}
myMap = smallMap // 縮容完成，原來的map被我們丟棄，交給gc去清理

5 Q&A關鍵知識點

5.1 基本原理

  • 底層是hash實現，數據結構為hash數組 + 桶 + 溢出的桶鏈表，每個桶存儲最多8個key-value對
  • 查找和插入的原理：key的hash值（低階位）與桶數量相與，得到key所在的hash桶，再用key的高8位與桶中的tophash[i]對比，相同則進一步對比key值，key值相等則找到
  • go map不支持併發。插入、刪除、搬遷等操作會置writing標誌，檢測到併發直接panic
  • 每次擴容hash表增大1倍，hash表只增不減
  • 支持有限縮容，delete操作只置刪除標誌位，釋放溢出桶的空間依靠觸發縮容來實現。
  • map在使用前必須初始化，否則panic：已初始化的map是make(map[key]value)或make(map[key]value, hint)這兩種形式。而new或var xxx map[key]value這兩種形式是未初始化的，直接使用會panic。

5.2 時間複雜度和空間複雜度分析

時間複雜度，go map是hash實現，我們先不管具體原理，江湖套路hash實現的就叫它O(1)的時間複雜度：

  • 正常情況，且不考慮擴容狀態，複雜度O(1)：通過hash值定位桶是O(1)，一個桶最多8個元素，合理的hash演算法應該能把元素相對均勻散列，所以溢出鏈表（如果有）也不會太長，所以雖然在桶和溢出鏈表上定位key是遍歷，考慮到數量小也可以認為是O(1)
  • 正常情況，處於擴容狀態時，複雜度也是O(1)：相比於上一種狀態，擴容會增加搬遷最多2個桶和溢出鏈表的時間消耗，當溢出鏈表不太長時，複雜度也可以認為是O(1)
  • 極端情況，散列極不均勻，大部分數據被集中在一條散列鏈表上，複雜度退化為O(n)。

go採用的hash演算法應是很成熟的演算法，極端情況暫不考慮。所以綜合情況下go map的時間複雜度應為O(1)

空間複雜度分析：
首先我們不考慮因刪除大量元素導致的空間浪費情況（這種情況現在go是留給程式員自己解決），只考慮一個持續增長狀態的map的一個空間使用率：
由於溢出桶數量超過hash桶數量時會觸發縮容，所以最壞的情況是數據被集中在一條鏈上，hash表基本是空的，這時空間浪費O(n)。
最好的情況下，數據均勻散列在hash表上，沒有元素溢出，這時最好的空間複雜度就是擴散因數決定了，當前go的擴散因數由全局變數決定，即loadFactorNum/loadFactorDen = 6.5。即平均每個hash桶被分配到6.5個元素以上時，開始擴容。所以最小的空間浪費是(8-6.5)/8 = 0.1875，即O(0.1875n)

結論：go map的空間複雜度（指除去正常存儲元素所需空間之外的空間浪費）是O(0.1875n) ~ O(n)之間。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • SpringBoot打可執行war包
    1. 主程式類： 2. pom.xml： 3. 使用maven打包(clean package)，此war包可以用於傳統的部署方式（外部tomcat），也可以直接使用java jar 的方式運行。 ...
  • GIT版本管理工具教程
    [toc] GIT版本管理工具教程 一 Git初始化 1. 下載安裝， 下載地址： https://git scm.com/downloads 每個系統的都有（linux、mac、windows等），看官網的安裝教程，很詳細，此處我以windows來練習 2. 首先創建一個文件夾，這個文件夾就是我們 ...
  • 使用Urllib下載圖片
    urllib下載圖片 urllib3下載圖片 Urllib下載圖片 1 from urllib import request 2 import re 3 import os 4 5 # 妹子圖首頁 下載首頁的幾張 6 url = 'https://www.mzitu.com' 7 # Request ...
  • python訪問Apollo獲取配置
    操作系統 ： CentOS7.3.1611_x64 Python 版本 : 3.6.8 Apollo源碼地址： https://github.com/ctripcorp/apollo 訪問Apollo使用這個庫： https://github.com/filamoon/pyapollo 不要使用py ...
  • PHP開發提高效率技巧
    PHP技術交流QQ群（各個大佬線上解答技術問題）： 953618831 0、用單引號代替雙引號來包含字元串，這樣做會更快一些。因為PHP會在雙引號包圍的字元串中搜尋變數，單引號則不會，註意：只有echo能這麼做，它是一種可以把多個字元串當作參數的“函數”（譯註：PHP手冊中說echo是語言結構，不是 ...
  • 為什麼 main 方法是 public static void ？
    Main方法是我們學習Java編程語言時知道的第一個方法，你是否曾經想過為什麼main方法是public、static、void的。當然，很多人首先學的是C和C++，但是在Java中main方法與前者有些細微的不同，它不會返回任何值，為什麼main方式是public、static、void，這篇文章 ...
  • Windowns系統下搭建python環境
    本文介紹下在windows系統下安裝python和python環境搭建。 安裝PYTHON 首先，我們去python的官方網站下載python安裝包。官網地址：https://www.python.org/downloads/跳轉到官網後，我們點擊下載按鈕，如圖： 在網頁下方還可下載python的歷 ...
  • python初學者的行業分類器三部曲之一【實現程式】
    python初學者，想要做一個簡單但是實用的小程式，實現目標如下： 可以手動選擇本地excel文件，然後點擊確認後，生成一個“將不同行業放在不同sheet”的新工作簿。 從而免去每個月都需要在各個excel表格中反覆匹配行業、反覆篩選、反覆複製粘貼到不同工作表的過程 實現我“做一個輕鬆快樂、無憂無慮 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類