摘要：我相信這樣你能更好的讀懂這篇文章原文地址深入理解賦值和擴(kuò)容遷移哈希函數(shù)哈希函數(shù)，又稱散列算法散列函數(shù)。而一個(gè)好的哈希函數(shù)，應(yīng)當(dāng)盡量少的出現(xiàn)哈希沖突，以此保證操作哈希表的時(shí)間復(fù)雜度但是哈希沖突在目前來(lái)講，是無(wú)法避免的。

在 上一章節(jié) 中，數(shù)據(jù)結(jié)構(gòu)小節(jié)里講解了大量基礎(chǔ)字段，可能你會(huì)疑惑需要 #&（！……#（！￥！ 來(lái)干嘛？接下來(lái)我們一起簡(jiǎn)單了解一下基礎(chǔ)概念。再開(kāi)始研討今天文章的重點(diǎn)內(nèi)容。我相信這樣你能更好的讀懂這篇文章

原文地址：深入理解 Go map：賦值和擴(kuò)容遷移

哈希函數(shù)，又稱散列算法、散列函數(shù)。主要作用是通過(guò)特定算法將數(shù)據(jù)根據(jù)一定規(guī)則組合重新生成得到一個(gè)散列值

而在哈希表中，其生成的散列值常用于尋找其鍵映射到哪一個(gè)桶上。而一個(gè)好的哈希函數(shù)，應(yīng)當(dāng)盡量少的出現(xiàn)哈希沖突，以此保證操作哈希表的時(shí)間復(fù)雜度（但是哈希沖突在目前來(lái)講，是無(wú)法避免的。我們需要 “解決” 它）

在哈希操作中，相當(dāng)核心的一個(gè)處理動(dòng)作就是 “哈希沖突” 的解決。而在 Go map 中采用的就是 "鏈地址法 " 去解決哈希沖突，又稱 "拉鏈法"。其主要做法是數(shù)組 + 鏈表的數(shù)據(jù)結(jié)構(gòu)，其溢出節(jié)點(diǎn)的存儲(chǔ)內(nèi)存都是動(dòng)態(tài)申請(qǐng)的，因此相對(duì)更靈活。而每一個(gè)元素都是一個(gè)鏈表。如下圖：

type hmap struct {
    ...
    buckets    unsafe.Pointer
    ...
    extra *mapextra
}

type mapextra struct {
    overflow    *[]*bmap
    oldoverflow *[]*bmap
    nextOverflow *bmap
}

在上章節(jié)中，我們介紹了 Go map 中的桶和溢出桶的概念，在其桶中只能存儲(chǔ) 8 個(gè)鍵值對(duì)元素。當(dāng)超過(guò) 8 個(gè)時(shí)，將會(huì)使用溢出桶進(jìn)行存儲(chǔ)或進(jìn)行擴(kuò)容

你可能會(huì)有疑問(wèn)，hint 大于 8 又會(huì)怎么樣？答案很明顯，性能問(wèn)題，其時(shí)間復(fù)雜度改變（也就是執(zhí)行效率出現(xiàn)問(wèn)題）

概要復(fù)習(xí)的差不多后，接下來(lái)我們將一同研討 Go map 的另外三個(gè)核心行為：賦值、擴(kuò)容、遷移。正式開(kāi)始我們的研討之旅吧 ：）

m := make(map[int32]string)
m[0] = "EDDYCJY"

在 map 的賦值動(dòng)作中，依舊是針對(duì) 32/64 位、string、pointer 類型有不同的轉(zhuǎn)換處理，總的函數(shù)原型如下：

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess1_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
func mapaccess2_fast32(t *maptype, h *hmap, key uint32) (unsafe.Pointer, bool)
func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer
func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer

func mapaccess1_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
func mapaccess2_fast64(t *maptype, h *hmap, key uint64) (unsafe.Pointer, bool)
func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer
func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess1_faststr(t *maptype, h *hmap, ky string) unsafe.Pointer
func mapaccess2_faststr(t *maptype, h *hmap, ky string) (unsafe.Pointer, bool)
func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer
...

接下來(lái)我們將分成幾個(gè)部分去看看底層在賦值的時(shí)候，都做了些什么處理？

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    if h == nil {
        panic(plainError("assignment to entry in nil map"))
    }
    ...
    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }
    alg := t.key.alg
    hash := alg.hash(key, uintptr(h.hash0))

    h.flags |= hashWriting

    if h.buckets == nil {
        h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
    }
    ...    
}

判斷 hmap 是否已經(jīng)初始化（是否為 nil）

判斷是否并發(fā)讀寫(xiě) map，若是則拋出異常

根據(jù) key 的不同類型調(diào)用不同的 hash 方法計(jì)算得出 hash 值

設(shè)置 flags 標(biāo)志位，表示有一個(gè) goroutine 正在寫(xiě)入數(shù)據(jù)。因?yàn)?alg.hash 有可能出現(xiàn) panic 導(dǎo)致異常

判斷 buckets 是否為 nil，若是則調(diào)用 newobject 根據(jù)當(dāng)前 bucket 大小進(jìn)行分配（例如：上章節(jié)提到的 makemap_small 方法，就在初始化時(shí)沒(méi)有初始 buckets，那么它在第一次賦值時(shí)就會(huì)對(duì) buckets 分配）

...
again:
    bucket := hash & bucketMask(h.B)
    if h.growing() {
        growWork(t, h, bucket)
    }
    b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
    top := tophash(hash)

    var inserti *uint8
    var insertk unsafe.Pointer
    var val unsafe.Pointer
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if b.tophash[i] == empty && inserti == nil {
                    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))
                }
                continue
            }
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey {
                k = *((*unsafe.Pointer)(k))
            }
            if !alg.equal(key, k) {
                continue
            }
            // already have a mapping for key. Update it.
            if t.needkeyupdate {
                typedmemmove(t.key, k, key)
            }
            val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize))
            goto done
        }
        ovf := b.overflow(t)
        if ovf == nil {
            break
        }
        b = ovf
    }

    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
    }
    ...

根據(jù)低八位計(jì)算得到 bucket 的內(nèi)存地址，并判斷是否正在擴(kuò)容，若正在擴(kuò)容中則先遷移再接著處理

計(jì)算并得到 bucket 的 bmap 指針地址，計(jì)算 key hash 高八位用于查找 Key

迭代 buckets 中的每一個(gè) bucket（共 8 個(gè)），對(duì)比 bucket.tophash 與 top（高八位）是否一致

若不一致，判斷是否為空槽。若是空槽（有兩種情況，第一種是沒(méi)有插入過(guò)。第二種是插入后被刪除），則把該位置標(biāo)識(shí)為可插入 tophash 位置。注意，這里就是第一個(gè)可以插入數(shù)據(jù)的地方

若 key 與當(dāng)前 k 不匹配則跳過(guò)。但若是匹配（也就是原本已經(jīng)存在），則進(jìn)行更新。最后跳出并返回 value 的內(nèi)存地址

判斷是否迭代完畢，若是則結(jié)束迭代 buckets 并更新當(dāng)前桶位置

若滿足三個(gè)條件：觸發(fā)最大 LoadFactor 、存在過(guò)多溢出桶 overflow buckets、沒(méi)有正在進(jìn)行擴(kuò)容。就會(huì)進(jìn)行擴(kuò)容動(dòng)作（以確保后續(xù)的動(dòng)作）

總的來(lái)講，這一塊邏輯做了兩件大事，第一是尋找空位，將位置其記錄在案，用于后續(xù)的插入動(dòng)作。第二是判斷 Key 是否已經(jīng)存在哈希表中，存在則進(jìn)行更新。而若是第二種場(chǎng)景，更新完畢后就會(huì)進(jìn)行收尾動(dòng)作，第一種將繼續(xù)執(zhí)行下述的代碼

    ...
    if inserti == nil {
        newb := h.newoverflow(t, b)
        inserti = &newb.tophash[0]
        insertk = add(unsafe.Pointer(newb), dataOffset)
        val = add(insertk, bucketCnt*uintptr(t.keysize))
    }

    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)
    *inserti = top
    h.count++

done:
    ...
    return val

經(jīng)過(guò)前面迭代尋找動(dòng)作，若沒(méi)有找到可插入的位置，意味著當(dāng)前的所有桶都滿了，將重新分配一個(gè)新溢出桶用于插入動(dòng)作。最后再在上一步申請(qǐng)的新插入位置，存儲(chǔ)鍵值對(duì)，返回該值的內(nèi)存地址

但是這里又疑惑了？最后為什么是返回內(nèi)存地址。這是因?yàn)殡[藏的最后一步寫(xiě)入動(dòng)作（將值拷貝到指定內(nèi)存區(qū)域）是通過(guò)底層匯編配合來(lái)完成的，在 runtime 中只完成了絕大部分的動(dòng)作

func main() {
    m := make(map[int32]int32)
    m[0] = 6666666
}

對(duì)應(yīng)的匯編部分：

...
0x0099 00153 (test.go:6)    CALL    runtime.mapassign_fast32(SB)
0x009e 00158 (test.go:6)    PCDATA    $2, $2
0x009e 00158 (test.go:6)    MOVQ    24(SP), AX
0x00a3 00163 (test.go:6)    PCDATA    $2, $0
0x00a3 00163 (test.go:6)    MOVL    $6666666, (AX)

這里分為了幾個(gè)部位，主要是調(diào)用 mapassign 函數(shù)和拿到值存放的內(nèi)存地址，再將 6666666 這個(gè)值存放進(jìn)該內(nèi)存地址中。另外我們看到 PCDATA 指令，主要是包含一些垃圾回收的信息，由編譯器產(chǎn)生

通過(guò)前面幾個(gè)階段的分析，我們可梳理出一些要點(diǎn)。例如：

不同類型對(duì)應(yīng)哈希函數(shù)不一樣

高八位用于定位 bucket

低八位用于定位 key，快速試錯(cuò)后再進(jìn)行完整對(duì)比

buckets/overflow buckets 遍歷

可插入位的處理

最終寫(xiě)入動(dòng)作與底層匯編的交互

在所有動(dòng)作中，擴(kuò)容規(guī)則是大家較關(guān)注的點(diǎn)，也是賦值里非常重要的一環(huán)。因此咱們將這節(jié)拉出來(lái)，對(duì)這塊細(xì)節(jié)進(jìn)行研討

if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    goto again
}

在特定條件的情況下且當(dāng)前沒(méi)有正在進(jìn)行擴(kuò)容動(dòng)作（以判斷 hmap.oldbuckets != nil 為基準(zhǔn)）。哈希表在賦值、刪除的動(dòng)作下會(huì)觸發(fā)擴(kuò)容行為，條件如下：

觸發(fā) load factor 的最大值，負(fù)載因子已達(dá)到當(dāng)前界限

溢出桶 overflow buckets 過(guò)多

那么什么情況下會(huì)對(duì)這兩個(gè) “值” 有影響呢？如下：

負(fù)載因子 load factor，用途是評(píng)估哈希表當(dāng)前的時(shí)間復(fù)雜度，其與哈希表當(dāng)前包含的鍵值對(duì)數(shù)、桶數(shù)量等相關(guān)。如果負(fù)載因子越大，則說(shuō)明空間使用率越高，但產(chǎn)生哈希沖突的可能性更高。而負(fù)載因子越小，說(shuō)明空間使用率低，產(chǎn)生哈希沖突的可能性更低

溢出桶 overflow buckets 的判定與 buckets 總數(shù)和 overflow buckets 總數(shù)相關(guān)聯(lián)

loadFactor：負(fù)載因子

%overflow：溢出率，具有溢出桶 overflow buckets 的桶的百分比

bytes/entry：每個(gè)鍵值對(duì)所的字節(jié)數(shù)開(kāi)銷

hitprobe：查找存在的 key 時(shí)，平均需要檢索的條目數(shù)量

missprobe：查找不存在的 key 時(shí)，平均需要檢索的條目數(shù)量

這一組數(shù)據(jù)能夠體現(xiàn)出不同的負(fù)載因子會(huì)給哈希表的動(dòng)作帶來(lái)怎么樣的影響。而在上一章節(jié)我們有提到默認(rèn)的負(fù)載因子是 6.5 (loadFactorNum/loadFactorDen)，可以看出來(lái)是經(jīng)過(guò)測(cè)試后取出的一個(gè)比較合理的因子。能夠較好的影響哈希表的擴(kuò)容動(dòng)作的時(shí)機(jī)

func hashGrow(t *maptype, h *hmap) {
    bigger := uint8(1)
    if !overLoadFactor(h.count+1, h.B) {
        bigger = 0
        h.flags |= sameSizeGrow
    }
    oldbuckets := h.buckets
    newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
    ...
    h.oldbuckets = oldbuckets
    h.buckets = newbuckets
    h.nevacuate = 0
    h.noverflow = 0

    if h.extra != nil && h.extra.overflow != nil {
        if h.extra.oldoverflow != nil {
            throw("oldoverflow is not nil")
        }
        h.extra.oldoverflow = h.extra.overflow
        h.extra.overflow = nil
    }
    if nextOverflow != nil {
        if h.extra == nil {
            h.extra = new(mapextra)
        }
        h.extra.nextOverflow = nextOverflow
    }

    // the actual copying of the hash table data is done incrementally
    // by growWork() and evacuate().
}

在上小節(jié)有講到擴(kuò)容的依據(jù)有兩種，在 hashGrow 開(kāi)頭就進(jìn)行了劃分。如下：

if !overLoadFactor(h.count+1, h.B) {
    bigger = 0
    h.flags |= sameSizeGrow
}

若不是負(fù)載因子 load factor 超過(guò)當(dāng)前界限，也就是屬于溢出桶 overflow buckets 過(guò)多的情況。因此本次擴(kuò)容規(guī)則將是 sameSizeGrow，即是不改變大小的擴(kuò)容動(dòng)作。那要是前者的情況呢？

bigger := uint8(1)
...
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

結(jié)合代碼分析可得出，若是負(fù)載因子 load factor 達(dá)到當(dāng)前界限，將會(huì)動(dòng)態(tài)擴(kuò)容當(dāng)前大小的兩倍作為其新容量大小

主要是針對(duì)擴(kuò)容的相關(guān)數(shù)據(jù)前置處理，涉及 buckets/oldbuckets、overflow/oldoverflow 之類與存儲(chǔ)相關(guān)的字段

...
oldbuckets := h.buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

flags := h.flags &^ (iterator | oldIterator)
if h.flags&iterator != 0 {
    flags |= oldIterator
}

h.B += bigger
...
h.noverflow = 0

if h.extra != nil && h.extra.overflow != nil {
    ...
    h.extra.oldoverflow = h.extra.overflow
    h.extra.overflow = nil
}
if nextOverflow != nil {
    ...
    h.extra.nextOverflow = nextOverflow
}

這里注意到這段代碼： newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)。第一反應(yīng)是擴(kuò)容的時(shí)候就馬上申請(qǐng)并初始化內(nèi)存了嗎？假設(shè)涉及大量的內(nèi)存分配，那挺耗費(fèi)性能的...

然而并不，內(nèi)部只會(huì)先進(jìn)行預(yù)分配，當(dāng)使用的時(shí)候才會(huì)真正的去初始化

在源碼中，發(fā)現(xiàn)第三階段的流轉(zhuǎn)并沒(méi)有顯式展示。這是因?yàn)榱鬓D(zhuǎn)由底層去做控制了。但通過(guò)分析代碼和注釋，可得知由第三階段涉及 growWork 和 evacuate 方法。如下：

func growWork(t *maptype, h *hmap, bucket uintptr) {
    evacuate(t, h, bucket&h.oldbucketmask())

    if h.growing() {
        evacuate(t, h, h.nevacuate)
    }
}

在該方法中，主要是兩個(gè) evacuate 函數(shù)的調(diào)用。他們?cè)谡{(diào)用上又分別有什么區(qū)別呢？如下：

evacuate(t, h, bucket&h.oldbucketmask()): 將 oldbucket 中的元素遷移 rehash 到擴(kuò)容后的新 bucket

evacuate(t, h, h.nevacuate): 如果當(dāng)前正在進(jìn)行擴(kuò)容，則再進(jìn)行多一次遷移

另外，在執(zhí)行擴(kuò)容動(dòng)作的時(shí)候，可以發(fā)現(xiàn)都是以 bucket/oldbucket 為單位的，而不是傳統(tǒng)的 buckets/oldbuckets。再結(jié)合代碼分析，可得知在 Go map 中擴(kuò)容是采取增量擴(kuò)容的方式，并非一步到位

為什么是增量擴(kuò)容？

如果是全量擴(kuò)容的話，那問(wèn)題就來(lái)了。假設(shè)當(dāng)前 hmap 的容量比較大，直接全量擴(kuò)容的話，就會(huì)導(dǎo)致擴(kuò)容要花費(fèi)大量的時(shí)間和內(nèi)存，導(dǎo)致系統(tǒng)卡頓，最直觀的表現(xiàn)就是慢。顯然，不能這么做

而增量擴(kuò)容，就可以解決這個(gè)問(wèn)題。它通過(guò)每一次的 map 操作行為去分?jǐn)偪偟囊淮涡詣?dòng)作。因此有了 buckets/oldbuckets 的設(shè)計(jì)，它是逐步完成的，并且會(huì)在擴(kuò)容完畢后才進(jìn)行清空

通過(guò)前面三個(gè)階段的分析，可以得知擴(kuò)容的大致過(guò)程。我們階段性總結(jié)一下。主要如下：

根據(jù)需擴(kuò)容的原因不同（overLoadFactor/tooManyOverflowBuckets），分為兩類容量規(guī)則方向，為等量擴(kuò)容（不改變?cè)写笮。┗螂p倍擴(kuò)容

新申請(qǐng)的擴(kuò)容空間（newbuckets/newoverflow）都是預(yù)分配，等真正使用的時(shí)候才會(huì)初始化

擴(kuò)容完畢后（預(yù)分配），不會(huì)馬上就進(jìn)行遷移。而是采取增量擴(kuò)容的方式，當(dāng)有訪問(wèn)到具體 bukcet 時(shí)，才會(huì)逐漸的進(jìn)行遷移（將 oldbucket 遷移到 bucket）

這時(shí)候又想到，既然遷移是逐步進(jìn)行的。那如果在途中又要擴(kuò)容了，怎么辦？

again:
    bucket := hash & bucketMask(h.B)
    ...
    if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
        hashGrow(t, h)
        goto again 
    }

在這里注意到 goto again 語(yǔ)句，結(jié)合上下文可得若正在進(jìn)行擴(kuò)容，就會(huì)不斷地進(jìn)行遷移。待遷移完畢后才會(huì)開(kāi)始進(jìn)行下一次的擴(kuò)容動(dòng)作

在擴(kuò)容的完整閉環(huán)中，包含著遷移的動(dòng)作，又稱 “搬遷”。因此我們繼續(xù)深入研究 evacuate 函數(shù)。接下來(lái)一起打開(kāi)遷移世界的大門(mén)。如下：

type evacDst struct {
    b *bmap          
    i int            
    k unsafe.Pointer 
    v unsafe.Pointer 
}

evacDst 是遷移中的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，其包含如下字段：

b: 當(dāng)前目標(biāo)桶

i: 當(dāng)前目標(biāo)桶存儲(chǔ)的鍵值對(duì)數(shù)量

k: 指向當(dāng)前 key 的內(nèi)存地址

v: 指向當(dāng)前 value 的內(nèi)存地址

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
    b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
    newbit := h.noldbuckets()
    if !evacuated(b) {
        var xy [2]evacDst
        x := &xy[0]
        x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
        x.k = add(unsafe.Pointer(x.b), dataOffset)
        x.v = add(x.k, bucketCnt*uintptr(t.keysize))

        if !h.sameSizeGrow() {
            y := &xy[1]
            y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
            y.k = add(unsafe.Pointer(y.b), dataOffset)
            y.v = add(y.k, bucketCnt*uintptr(t.keysize))
        }

        for ; b != nil; b = b.overflow(t) {
            ...
        }

        if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
            b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
            ptr := add(b, dataOffset)
            n := uintptr(t.bucketsize) - dataOffset
            memclrHasPointers(ptr, n)
        }
    }

    if oldbucket == h.nevacuate {
        advanceEvacuationMark(h, t, newbit)
    }
}

計(jì)算并得到 oldbucket 的 bmap 指針地址

計(jì)算 hmap 在增長(zhǎng)之前的桶數(shù)量

判斷當(dāng)前的遷移（搬遷）狀態(tài)，以便流轉(zhuǎn)后續(xù)的操作。若沒(méi)有正在進(jìn)行遷移 !evacuated(b) ，則根據(jù)擴(kuò)容的規(guī)則的不同，當(dāng)規(guī)則為等量擴(kuò)容 sameSizeGrow 時(shí)，只使用一個(gè) evacDst 桶用于分流。而為雙倍擴(kuò)容時(shí)，就會(huì)使用兩個(gè) evacDst 進(jìn)行分流操作

當(dāng)分流完畢后，需要遷移的數(shù)據(jù)都會(huì)通過(guò) typedmemmove 函數(shù)遷移到指定的目標(biāo)桶上

若當(dāng)前不存在 flags 使用標(biāo)志、使用 oldbucket 迭代器、bucket 不為指針類型。則取消鏈接溢出桶、清除鍵值

在最后 advanceEvacuationMark 函數(shù)中會(huì)對(duì)遷移進(jìn)度 hmap.nevacuate 進(jìn)行累積計(jì)數(shù)，并調(diào)用 bucketEvacuated 對(duì)舊桶 oldbuckets 進(jìn)行不斷的遷移。直至全部遷移完畢。那么也就表示擴(kuò)容完畢了，會(huì)對(duì) hmap.oldbuckets 和 h.extra.oldoverflow 進(jìn)行清空

總的來(lái)講，就是計(jì)算得到所需數(shù)據(jù)的位置。再根據(jù)當(dāng)前的遷移狀態(tài)、擴(kuò)容規(guī)則進(jìn)行數(shù)據(jù)分流遷移。結(jié)束后進(jìn)行清理，促進(jìn) GC 的回收

在本章節(jié)我們主要研討了 Go map 的幾個(gè)核心動(dòng)作，分別是：“賦值、擴(kuò)容、遷移” 。而通過(guò)本次的閱讀，我們能夠更進(jìn)一步的認(rèn)識(shí)到一些要點(diǎn)，例如：

賦值的時(shí)候會(huì)觸發(fā)擴(kuò)容嗎？

負(fù)載因子是什么？過(guò)高會(huì)帶來(lái)什么問(wèn)題？它的變動(dòng)會(huì)對(duì)哈希表操作帶來(lái)什么影響嗎？

溢出桶越多會(huì)帶來(lái)什么問(wèn)題？

是否要擴(kuò)容的基準(zhǔn)條件是什么？

擴(kuò)容的容量規(guī)則是怎么樣的？

擴(kuò)容的步驟是怎么樣的？涉及到了哪些數(shù)據(jù)結(jié)構(gòu)？

擴(kuò)容是一次性擴(kuò)容還是增量擴(kuò)容？

正在擴(kuò)容的時(shí)候又要擴(kuò)容怎么辦？

擴(kuò)容時(shí)的遷移分流動(dòng)作是怎么樣的？

在擴(kuò)容動(dòng)作中，底層匯編承擔(dān)了什么角色？做了什么事？

在 buckets/overflow buckets 中尋找時(shí)，是如何 “快速” 定位值的？低八位、高八位的用途？

空槽有可能出現(xiàn)在任意位置嗎？假設(shè)已經(jīng)沒(méi)有空槽了，但是又有新值要插入，底層會(huì)怎么處理

最后希望你通過(guò)本文的閱讀，能更清楚地了解到 Go map 是怎么樣運(yùn)作的 ：）