[[426001]]

本文轉(zhuǎn)載自微信公眾號(hào)「腦子進(jìn)煎魚了」，作者陳煎魚 。轉(zhuǎn)載本文請(qǐng)聯(lián)系腦子進(jìn)煎魚了公眾號(hào)。

大家好，我是煎魚。

在上篇 《一文啃透 Go map：初始化和訪問》中，我們?cè)跀?shù)據(jù)結(jié)構(gòu)小節(jié)里講解了大量基礎(chǔ)字段，可能你會(huì)疑惑需要 #&(!……#(!￥!來干嘛?

今天我們一起簡(jiǎn)單了解一下基礎(chǔ)概念，再開始研討 map 的重點(diǎn)內(nèi)容。我相信這樣你能更好的讀懂這篇文章。

哈希函數(shù)

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

在哈希表中，其生成的散列值常用于尋找其鍵映射到哪一個(gè)桶上。

一個(gè)好的哈希函數(shù)，應(yīng)當(dāng)盡量少的出現(xiàn)哈希沖突，以此保證操作哈希表的時(shí)間復(fù)雜度(但是哈希沖突在目前來講，是無法避免的。我們需要 “解決” 它)。

鏈地址法

在哈希操作中，相當(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)超過 8 個(gè)時(shí)，將會(huì)使用溢出桶進(jìn)行存儲(chǔ)或進(jìn)行擴(kuò)容。

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

前言

基本概要復(fù)習(xí)的差不多后，接下來我們將一同研討 Go map 的另外三個(gè)核心行為：

• 賦值。
• 擴(kuò)容。
• 遷移。

正式開始我們的研討之旅吧 ：)

賦值

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

函數(shù)原型

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

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

源碼

第一階段：校驗(yàn)和初始化

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 方法計(jì)算得出 hash 值。
• 設(shè)置 flags 標(biāo)志位，表示有一個(gè) goroutine 正在寫入數(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í)沒有初始 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(高八位)是否一致。
• 若不一致，判斷是否為空槽。若是空槽(有兩種情況，第一種是沒有插入過。第二種是插入后被刪除)，則把該位置標(biāo)識(shí)為可插入 tophash 位置。注意，這里就是第一個(gè)可以插入數(shù)據(jù)的地方。
• 若 key 與當(dāng)前 k 不匹配則跳過。但若是匹配(也就是原本已經(jīng)存在)，則進(jìn)行更新。最后跳出并返回 value 的內(nèi)存地址。
• 判斷是否迭代完畢，若是則結(jié)束迭代 buckets 并更新當(dāng)前桶位置。
• 若滿足三個(gè)條件：觸發(fā)最大 LoadFactor 、存在過多溢出桶 overflow buckets、沒有正在進(jìn)行擴(kuò)容。就會(huì)進(jìn)行擴(kuò)容動(dòng)作(以確保后續(xù)的動(dòng)作)。

總的來講，這一塊邏輯做了兩件大事：

• 第一是尋找空位，將位置其記錄在案，用于后續(xù)的插入動(dòng)作。
• 第二是判斷 Key 是否已經(jīng)存在哈希表中，存在則進(jìn)行更新。

若是第二種場(chǎng)景，更新完畢后就會(huì)進(jìn)行收尾動(dòng)作，第一種將繼續(xù)執(zhí)行下述的代碼。

第三階段：申請(qǐng)新的插入位和插入新值

   ... 
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++ 
 
one: 
... 
return val 

經(jīng)過前面迭代尋找動(dòng)作，若沒有找到可插入的位置，意味著當(dāng)前的所有桶都滿了，將重新分配一個(gè)新溢出桶用于插入動(dòng)作。

最后再在上一步申請(qǐng)的新插入位置，存儲(chǔ)鍵值對(duì)，返回該值的內(nèi)存地址。

第四階段：寫入

但是這里又疑惑了，最后為什么是返回內(nèi)存地址?

這是因?yàn)殡[藏的最后一步寫入動(dòng)作(將值拷貝到指定內(nèi)存區(qū)域)是通過底層匯編配合來完成的，在 runtime 中只完成了絕大部分的動(dòng)作。

寫入 map 的示例代碼：

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)生。

小結(jié)

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

• 不同類型對(duì)應(yīng)哈希函數(shù)不一樣。
• 高八位用于定位 bucket。
• 低八位用于定位 key，快速試錯(cuò)后再進(jìn)行完整對(duì)比。
• buckets/overflow buckets 遍歷。
• 可插入位的處理。
• 最終寫入動(dòng)作與底層匯編的交互。

擴(kuò)容

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

什么時(shí)候擴(kuò)容

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

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

條件如下：

• 觸發(fā) load factor 的最大值，負(fù)載因子已達(dá)到當(dāng)前界限。
• 溢出桶 overflow buckets 過多。

什么時(shí)候受影響

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

負(fù)載因子 load factor，用途是評(píng)估哈希表當(dāng)前的時(shí)間復(fù)雜度，其與哈希表當(dāng)前包含的鍵值對(duì)數(shù)、桶數(shù)量等相關(guān)。

• 負(fù)載因子越大，則說明空間使用率越高，但產(chǎn)生哈希沖突的可能性更高。
• 負(fù)載因子越小，說明空間使用率低，產(chǎn)生哈希沖突的可能性更低。

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

因子關(guān)系

loadFactor	%overflow	bytes/entry	hitprobe	missprobe
4.00	2.13	20.77	3.00	4.00
4.50	4.05	17.30	3.25	4.50
5.00	6.85	14.77	3.50	5.00
5.50	10.55	12.94	3.75	5.50
6.00	15.27	11.67	4.00	6.00
6.50	20.90	10.79	4.25	6.50
7.00	27.14	10.15	4.50	7.00

• loadFactor：負(fù)載因子
• %overflow：溢出率，具有溢出桶 overflow buckets 的桶的百分比
• bytes/entry：每個(gè)鍵值對(duì)所的字節(jié)數(shù)開銷
• hitprobe：查找存在的 key 時(shí)，平均需要檢索的條目數(shù)量
• missprobe：查找不存在的 key 時(shí)，平均需要檢索的條目數(shù)量

這一組數(shù)據(jù)能夠體現(xiàn)出不同的負(fù)載因子會(huì)給哈希表的動(dòng)作帶來怎么樣的影響。

在上一章節(jié)中，有提到默認(rèn)的負(fù)載因子是 6.5 (loadFactorNum/loadFactorDen)，可以看出來是經(jīng)過測(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(). 
} 

第一階段：確定擴(kuò)容容量規(guī)則

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

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

若不是負(fù)載因子 load factor 超過當(dāng)前界限，也就是屬于溢出桶 overflow buckets 過多的情況。

因此本次擴(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ì)真正的去初始化

第三階段：擴(kuò)容

在源碼中，發(fā)現(xiàn)第三階段的流轉(zhuǎn)并沒有顯式展示。這是因?yàn)榱鬓D(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) 
 } 
} 

在該方法中，主要是兩個(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ò)容的話，那問題就來了。假設(shè)當(dāng)前 hmap 的容量比較大，直接全量擴(kuò)容的話，就會(huì)導(dǎo)致擴(kuò)容要花費(fèi)大量的時(shí)間和內(nèi)存，導(dǎo)致系統(tǒng)卡頓，最直觀的表現(xiàn)就是慢。

顯然，不能這么做。

而增量擴(kuò)容，就可以解決這個(gè)問題。它通過每一次的 map 操作行為去分?jǐn)偪偟囊淮涡詣?dòng)作。

因此有了 buckets/oldbuckets 的設(shè)計(jì)，它是逐步完成的，并且會(huì)在擴(kuò)容完畢后才進(jìn)行清空。

小結(jié)

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

• 根據(jù)需擴(kuò)容的原因不同(overLoadFactor/tooManyOverflowBuckets)，分為兩類容量規(guī)則方向，為等量擴(kuò)容(不改變?cè)写笮?或雙倍擴(kuò)容
• 新申請(qǐng)的擴(kuò)容空間(newbuckets/newoverflow)都是預(yù)分配，等真正使用的時(shí)候才會(huì)初始化。
• 擴(kuò)容完畢后(預(yù)分配)，不會(huì)馬上就進(jìn)行遷移。而是采取增量擴(kuò)容的方式，當(dāng)有訪問到具體 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 語句，結(jié)合上下文可得若正在進(jìn)行擴(kuò)容，就會(huì)不斷地進(jìn)行遷移，待遷移完畢后才會(huì)開始進(jìn)行下一次的擴(kuò)容動(dòng)作。

遷移

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

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ù)的操作。若沒有正在進(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ì)通過 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)行清空。

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

總結(jié)

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

• 賦值的時(shí)候會(huì)觸發(fā)擴(kuò)容嗎?
• 負(fù)載因子是什么?過高會(huì)帶來什么問題?它的變動(dòng)會(huì)對(duì)哈希表操作帶來什么影響嗎?
• 溢出桶越多會(huì)帶來什么問題?
• 是否要擴(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)沒有空槽了，但是又有新值要插入，底層會(huì)怎么處理

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