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

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

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

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

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

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

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

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

在上章節(jié)中，我們介紹了 Go map 中的桶和溢出桶的概念，在其桶中只能存儲 8 個鍵值對元素。當超過 8 個時，將會使用溢出桶進行存儲或進行擴容

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

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

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

在 map 的賦值動作中，依舊是針對 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
...

接下來我們將分成幾個部分去看看底層在賦值的時候，都做了些什么處理？

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ā)讀寫 map，若是則拋出異常

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

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

判斷 buckets 是否為 nil，若是則調(diào)用 newobject 根據(jù)當前 bucket 大小進行分配（例如：上章節(jié)提到的 makemap_small 方法，就在初始化時沒有初始 buckets，那么它在第一次賦值時就會對 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ù)低八位計算得到 bucket 的內(nèi)存地址，并判斷是否正在擴容，若正在擴容中則先遷移再接著處理

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

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

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

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

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

若滿足三個條件：觸發(fā)最大 LoadFactor 、存在過多溢出桶 overflow buckets、沒有正在進行擴容。就會進行擴容動作（以確保后續(xù)的動作）

總的來講，這一塊邏輯做了兩件大事，第一是尋找空位，將位置其記錄在案，用于后續(xù)的插入動作。第二是判斷 Key 是否已經(jī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)過前面迭代尋找動作，若沒有找到可插入的位置，意味著當前的所有桶都滿了，將重新分配一個新溢出桶用于插入動作。最后再在上一步申請的新插入位置，存儲鍵值對，返回該值的內(nèi)存地址

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

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

對應(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)

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

通過前面幾個階段的分析，我們可梳理出一些要點。例如：

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

高八位用于定位 bucket

低八位用于定位 key，快速試錯后再進行完整對比

buckets/overflow buckets 遍歷

可插入位的處理

最終寫入動作與底層匯編的交互

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

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

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

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

溢出桶 overflow buckets 過多

那么什么情況下會對這兩個 “值” 有影響呢？如下：

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

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

loadFactor：負載因子

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

bytes/entry：每個鍵值對所的字節(jié)數(shù)開銷

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

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

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

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é)有講到擴容的依據(jù)有兩種，在 hashGrow 開頭就進行了劃分。如下：

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

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

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

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

主要是針對擴容的相關(guān)數(shù)據(jù)前置處理，涉及 buckets/oldbuckets、overflow/oldoverflow 之類與存儲相關(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)是擴容的時候就馬上申請并初始化內(nèi)存了嗎？假設(shè)涉及大量的內(nèi)存分配，那挺耗費性能的...

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

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

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

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

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

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

evacuate(t, h, h.nevacuate): 如果當前正在進行擴容，則再進行多一次遷移

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

為什么是增量擴容？

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

而增量擴容，就可以解決這個問題。它通過每一次的 map 操作行為去分攤總的一次性動作。因此有了 buckets/oldbuckets 的設(shè)計，它是逐步完成的，并且會在擴容完畢后才進行清空

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

根據(jù)需擴容的原因不同（overLoadFactor/tooManyOverflowBuckets），分為兩類容量規(guī)則方向，為等量擴容（不改變原有大小）或雙倍擴容

新申請的擴容空間（newbuckets/newoverflow）都是預(yù)分配，等真正使用的時候才會初始化

擴容完畢后（預(yù)分配），不會馬上就進行遷移。而是采取增量擴容的方式，當有訪問到具體 bukcet 時，才會逐漸的進行遷移（將 oldbucket 遷移到 bucket）

這時候又想到，既然遷移是逐步進行的。那如果在途中又要擴容了，怎么辦？

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 語句，結(jié)合上下文可得若正在進行擴容，就會不斷地進行遷移。待遷移完畢后才會開始進行下一次的擴容動作

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

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

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

b: 當前目標桶

i: 當前目標桶存儲的鍵值對數(shù)量

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

v: 指向當前 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)
    }
}

計算并得到 oldbucket 的 bmap 指針地址

計算 hmap 在增長之前的桶數(shù)量

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

當分流完畢后，需要遷移的數(shù)據(jù)都會通過 typedmemmove 函數(shù)遷移到指定的目標桶上

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

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

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

在本章節(jié)我們主要研討了 Go map 的幾個核心動作，分別是：“賦值、擴容、遷移” 。而通過本次的閱讀，我們能夠更進一步的認識到一些要點，例如：

賦值的時候會觸發(fā)擴容嗎？

負載因子是什么？過高會帶來什么問題？它的變動會對哈希表操作帶來什么影響嗎？

溢出桶越多會帶來什么問題？

是否要擴容的基準條件是什么？

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

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

擴容是一次性擴容還是增量擴容？

正在擴容的時候又要擴容怎么辦？

擴容時的遷移分流動作是怎么樣的？

在擴容動作中，底層匯編承擔了什么角色？做了什么事？

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

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

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