概要
在 上一章節(jié) 中炊邦，數(shù)據(jù)結(jié)構(gòu)小節(jié)里講解了大量基礎(chǔ)字段，可能你會(huì)疑惑需要 #&（祭玉！……#（！￥春畔！ 來(lái)干嘛攘宙？接下來(lái)我們一起簡(jiǎn)單了解一下基礎(chǔ)概念。再開(kāi)始研討今天文章的重點(diǎn)內(nèi)容拐迁。我相信這樣你能更好的讀懂這篇文章
哈希函數(shù)
哈希函數(shù)蹭劈，又稱(chēng)散列算法、散列函數(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 中采用的就是 "鏈地址法 " 去解決哈希沖突伏蚊，又稱(chēng) "拉鏈法"立轧。其主要做法是數(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"
函數(shù)原型
在 map 的賦值動(dòng)作中篙顺，依舊是針對(duì) 32/64 位偶芍、string、pointer 類(lèi)型有不同的轉(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í)候匪蟀，都做了些什么處理？
源碼
第一階段：校驗(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ā)讀寫(xiě) map宰僧，若是則拋出異常
- 根據(jù) key 的不同類(lèi)型調(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í)行下述的代碼
第三階段：申請(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++
done:
...
return val
經(jīng)過(guò)前面迭代尋找動(dòng)作，若沒(méi)有找到可插入的位置遮婶，意味著當(dāng)前的所有桶都滿了蝗碎，將重新分配一個(gè)新溢出桶用于插入動(dòng)作。最后再在上一步申請(qǐng)的新插入位置旗扑，存儲(chǔ)鍵值對(duì)蹦骑，返回該值的內(nèi)存地址
第四階段：寫(xiě)入
但是這里又疑惑了？最后為什么是返回內(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)生
小結(jié)
通過(guò)前面幾個(gè)階段的分析登疗，我們可梳理出一些要點(diǎn)。例如：
- 不同類(lèi)型對(duì)應(yīng)哈希函數(shù)不一樣
- 高八位用于定位 bucket
- 低八位用于定位 key篡悟，快速試錯(cuò)后再進(jìn)行完整對(duì)比
- buckets/overflow buckets 遍歷
- 可插入位的處理
- 最終寫(xiě)入動(dòng)作與底層匯編的交互
擴(kuò)容
在所有動(dòng)作中谜叹，擴(kuò)容規(guī)則是大家較關(guān)注的點(diǎn)，也是賦值里非常重要的一環(huán)搬葬。因此咱們將這節(jié)拉出來(lái)荷腊，對(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)前沒(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ò)多
什么時(shí)候受影響
那么什么情況下會(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)
因子關(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ù)開(kāi)銷(xiāo)
- 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().
}
第一階段：確定擴(kuò)容容量規(guī)則
在上小節(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 之類(lèi)與存儲(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)并沒(méi)有顯式展示蜡塌。這是因?yàn)榱鬓D(zhuǎn)由底層去做控制了。但通過(guò)分析代碼和注釋?zhuān)傻弥傻谌A段涉及 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)行清空
小結(jié)
通過(guò)前面三個(gè)階段的分析乓序，可以得知擴(kuò)容的大致過(guò)程寺酪。我們階段性總結(jié)一下。主要如下：
- 根據(jù)需擴(kuò)容的原因不同（overLoadFactor/tooManyOverflowBuckets）替劈，分為兩類(lèi)容量規(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)作悍募，又稱(chē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 不為指針類(lèi)型背桐。則取消鏈接溢出桶优烧、清除鍵值
- 在最后
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é)
在本章節(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)作的 ：）
