golang map 操作，是map 實(shí)現(xiàn)中較復(fù)雜的邏輯。因?yàn)楫?dāng)賦值時(shí)，為了減少hash 沖突鏈的長(zhǎng)度過(guò)長(zhǎng)問(wèn)題，會(huì)做map 的擴(kuò)容以及數(shù)據(jù)的遷移。而map 的擴(kuò)容以及數(shù)據(jù)的遷移也是關(guān)注的重點(diǎn)。
數(shù)據(jù)結(jié)構(gòu)
首先，我們需要重新學(xué)習(xí)下map實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
type hmap struct { count int flags uint8 B uint8 noverflow uint16 hash0 uint32 buckets unsafe.Pointer oldbuckets unsafe.Pointer nevacuate uintptr extra *mapextra}type mapextra struct { overflow *[]*bmap oldoverflow *[]*bmap nextOverflow *bmap} |
hmap 是 map 實(shí)現(xiàn)的結(jié)構(gòu)體。大部分字段在 第一節(jié)中已經(jīng)學(xué)習(xí)過(guò)了。剩余的就是nevacuate 和extra 了。
首先需要了解搬遷的概念：當(dāng)hash 中數(shù)據(jù)鏈太長(zhǎng)，或者空的bucket 太多時(shí)，會(huì)操作數(shù)據(jù)搬遷，將數(shù)據(jù)挪到一個(gè)新的bucket 上，就的bucket數(shù)組成為了oldbuckets。bucket的搬遷不是一次就搬完的，是訪(fǎng)問(wèn)到對(duì)應(yīng)的bucket時(shí)才可能會(huì)觸發(fā)搬遷操作。（這一點(diǎn)是不是和redis 的擴(kuò)容比較類(lèi)似，將擴(kuò)容放在多個(gè)訪(fǎng)問(wèn)上，減少了單次訪(fǎng)問(wèn)的延遲壓力）
- nevactuate 標(biāo)識(shí)的是搬遷的位置(也可以考慮為搬遷的進(jìn)度）。標(biāo)識(shí)目前 oldbuckets 中 （一個(gè) array）bucket 搬遷到哪里了。
- extra 是一個(gè)map 的結(jié)構(gòu)體，nextOverflow 標(biāo)識(shí)的是申請(qǐng)的空的bucket，用于之后解決沖突時(shí)使用；overflow 和 oldoverflow 標(biāo)識(shí)溢出的鏈表中正在使用的bucket 數(shù)據(jù)。old 和非old 的區(qū)別是，old 是為搬遷的數(shù)據(jù)。
理解了大概的數(shù)據(jù)結(jié)構(gòu)，我們可以學(xué)習(xí)map的 賦值操作了。
map 賦值操作
map 的賦值操作寫(xiě)法如下：
|
1
|
data := mapExample["hello"] |
賦值的實(shí)現(xiàn)，golang 為了對(duì)不同類(lèi)型k做了優(yōu)化，下面時(shí)一些實(shí)現(xiàn)方法：
|
1
2
3
4
5
6
|
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {}func mapassign_fast32(t *maptype, h *hmap, key uint32) unsafe.Pointer {}func mapassign_fast32ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {}func mapassign_fast64(t *maptype, h *hmap, key uint64) unsafe.Pointer {}func mapassign_fast64ptr(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer{}func mapassign_faststr(t *maptype, h *hmap, s string) unsafe.Pointer {} |
內(nèi)容大同小異，我們主要學(xué)習(xí)mapassign 的實(shí)現(xiàn)。
mapassign 方法的實(shí)現(xiàn)是查找一個(gè)空的bucket，把key賦值到bucket上，然后把val的地址返回,然后直接通過(guò)匯編做內(nèi)存拷貝。
那我們一步步看是如何找空閑bucket的：
① 在查找key之前，會(huì)做異常檢測(cè)，校驗(yàn)map是否未初始化，或正在并發(fā)寫(xiě)操作，如果存在，則拋出異常：（這就是為什么map 并發(fā)寫(xiě)回panic的原因）
|
1
2
3
4
5
6
7
8
|
if h == nil { panic(plainError("assignment to entry in nil map"))}// 竟態(tài)檢查 和 內(nèi)存掃描if h.flags&hashWriting != 0 { throw("concurrent map writes")} |
② 需要計(jì)算key 對(duì)應(yīng)的hash 值，如果buckets 為空（初始化的時(shí)候小于一定長(zhǎng)度的map 不會(huì)初始化數(shù)據(jù)）還需要初始化一個(gè)bucket
|
1
2
3
4
5
6
7
8
9
|
alg := t.key.alghash := alg.hash(key, uintptr(h.hash0))// 為什么需要在hash 后設(shè)置flags，因?yàn)?alg.hash可能會(huì)panich.flags ^= hashWritingif h.buckets == nil { h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)} |
③ 通過(guò)hash 值，獲取對(duì)應(yīng)的bucket。如果map 還在遷移數(shù)據(jù)，還需要在oldbuckets中找對(duì)應(yīng)的bucket，并搬遷到新的bucket。
|
1
2
3
4
5
6
7
8
9
10
11
|
// 通過(guò)hash 計(jì)算bucket的位置偏移bucket := hash & bucketMask(h.B)// 此處是搬遷邏輯，我們后續(xù)詳解if h.growing() { growWork(t, h, bucket)}// 計(jì)算對(duì)應(yīng)的bucket 位置，和top hash 值b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))top := tophash(hash) |
④ 拿到bucket之后，還需要按照鏈表方式一個(gè)一個(gè)查，找到對(duì)應(yīng)的key， 可能是已經(jīng)存在的key，也可能需要新增。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
for { for i := uintptr(0); i < bucketCnt; i++ { // 若 tophash 就不相等，那就取tophash 中的下一個(gè) if b.tophash[i] != top { // 若是個(gè)空位置，把kv的指針拿到。 if isEmpty(b.tophash[i]) && 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)) } // 若后續(xù)無(wú)數(shù)據(jù)，那就不用再找坑了 if b.tophash[i] == emptyRest { break bucketloop } continue } // 若tophash匹配時(shí) k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize)) if t.indirectkey() { k = *((*unsafe.Pointer)(k)) } // 比較k不等，還需要繼續(xù)找 if !alg.equal(key, k) { continue } // 如果key 也相等，說(shuō)明之前有數(shù)據(jù)，直接更新k，并拿到v的地址就可以了 if t.needkeyupdate() { typedmemmove(t.key, k, key) } val = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.valuesize)) goto done } // 取下一個(gè)overflow （鏈表指針） ovf := b.overflow(t) if ovf == nil { break } b = ovf} |
總結(jié)下這段程序，主要有幾個(gè)部分：
a. map hash 不匹配的情況，會(huì)看是否是空kv 。如果調(diào)用了delete，會(huì)出現(xiàn)空kv的情況，那先把地址留下，如果后面也沒(méi)找到對(duì)應(yīng)的k（也就是說(shuō)之前map 里面沒(méi)有對(duì)應(yīng)的Key），那就直接用空kv的位置即可。
b. 如果 map hash 是匹配的，需要判定key 的字面值是否匹配。如果不匹配，還需要查找。如果匹配了，那直接把key 更新（因?yàn)榭赡苡幸茫瑅的地址返回即可。
c. 如果上面都沒(méi)有，那就看下一個(gè)bucket
⑤ 插入數(shù)據(jù)前，會(huì)先檢查數(shù)據(jù)太多了，需要擴(kuò)容，如果需要擴(kuò)容，那就從第③開(kāi)始拿到新的bucket，并查找對(duì)應(yīng)的位置。
|
1
2
3
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} |
⑥ 如果剛才看沒(méi)有有空的位置，那就需要在鏈表后追加一個(gè)bucket，拿到kv。
|
1
2
3
4
5
6
7
|
if inserti == nil { // all current buckets are full, allocate a new one. newb := h.newoverflow(t, b) inserti = &newb.tophash[0] insertk = add(unsafe.Pointer(newb), dataOffset) val = add(insertk, bucketCnt*uintptr(t.keysize))} |
⑦ 最后更新tophash 和 key 的字面值, 并解除hashWriting 約束
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
// 如果非指針數(shù)據(jù)（也就是直接賦值的數(shù)據(jù)），還需要申請(qǐng)內(nèi)存和拷貝if t.indirectkey() { kmem := newobject(t.key) *(*unsafe.Pointer)(insertk) = kmem insertk = kmem}if t.indirectvalue() { vmem := newobject(t.elem) *(*unsafe.Pointer)(val) = vmem}// 更新tophash, ktypedmemmove(t.key, insertk, key)*inserti = topdone:if h.flags&hashWriting == 0 { throw("concurrent map writes") } h.flags &^= hashWriting if t.indirectvalue() { val = *((*unsafe.Pointer)(val)) } return val |
到這里，map的賦值基本就介紹完了。下面學(xué)習(xí)下步驟⑤中的map的擴(kuò)容。
Map 的擴(kuò)容
有兩種情況下，需要做擴(kuò)容。一種是存的kv數(shù)據(jù)太多了，已經(jīng)超過(guò)了當(dāng)前map的負(fù)載。還有一種是overflow的bucket過(guò)多了。這個(gè)閾值是一個(gè)定值，經(jīng)驗(yàn)得出的結(jié)論，所以我們這里不考究。
當(dāng)滿(mǎn)足條件后，將開(kāi)始擴(kuò)容。如果滿(mǎn)足條件二，擴(kuò)容后的buckets 的數(shù)量和原來(lái)是一樣的，說(shuō)明可能是空kv占據(jù)的坑太多了，通過(guò)map擴(kuò)容做內(nèi)存整理。如果是因?yàn)閗v 量多導(dǎo)致map負(fù)載過(guò)高，那就擴(kuò)一倍的量。
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
func hashGrow(t *maptype, h *hmap) { bigger := uint8(1) // 如果是第二種情況，擴(kuò)容大小為0 if !overLoadFactor(h.count+1, h.B) { bigger = 0 h.flags |= sameSizeGrow } oldbuckets := h.buckets // 申請(qǐng)一個(gè)大數(shù)組，作為新的buckets newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil) flags := h.flags &^ (iterator | oldIterator) if h.flags&iterator != 0 { flags |= oldIterator } // 然后重新賦值map的結(jié)構(gòu)體，oldbuckets 被填充。之后將做搬遷操作 h.B += bigger h.flags = flags h.oldbuckets = oldbuckets h.buckets = newbuckets h.nevacuate = 0 h.noverflow = 0 // extra 結(jié)構(gòu)體做賦值 if h.extra != nil && h.extra.overflow != nil { // Promote current overflow buckets to the old generation. 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 }} |
總結(jié)下map的擴(kuò)容操作。首先拿到擴(kuò)容的大小，然后申請(qǐng)大數(shù)組，然后做些初始化的操作，把老的buckets，以及overflow做切換即可。
map 數(shù)據(jù)的遷移
擴(kuò)容完成后，需要做數(shù)據(jù)的遷移。數(shù)據(jù)的遷移不是一次完成的，是使用時(shí)才會(huì)做對(duì)應(yīng)bucket的遷移。也就是逐步做到的數(shù)據(jù)遷移。下面我們來(lái)學(xué)習(xí)。
在數(shù)據(jù)賦值的第③步，會(huì)看需要操作的bucket是不是在舊的buckets里面，如果在就搬遷。下面是搬遷的具體操作：
|
1
2
3
4
5
6
7
8
9
|
func growWork(t *maptype, h *hmap, bucket uintptr) { // 首先把需要操作的bucket 搬遷 evacuate(t, h, bucket&h.oldbucketmask()) // 再順帶搬遷一個(gè)bucket if h.growing() { evacuate(t, h, h.nevacuate) }} |
nevacuate 標(biāo)識(shí)的是當(dāng)前的進(jìn)度，如果都搬遷完，應(yīng)該和2^B的長(zhǎng)度是一樣的（這里說(shuō)的B是oldbuckets 里面的B，畢竟新的buckets長(zhǎng)度可能是2^(B+1))。
在evacuate 方法實(shí)現(xiàn)是把這個(gè)位置對(duì)應(yīng)的bucket，以及其沖突鏈上的數(shù)據(jù)都轉(zhuǎn)移到新的buckets上。
① 先要判斷當(dāng)前bucket是不是已經(jīng)轉(zhuǎn)移。 (oldbucket 標(biāo)識(shí)需要搬遷的bucket 對(duì)應(yīng)的位置)
|
1
2
3
4
5
|
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))// 判斷if !evacuated(b) { // 做轉(zhuǎn)移操作} |
轉(zhuǎn)移的判斷直接通過(guò)tophash 就可以，判斷tophash中第一個(gè)hash值即可 （tophash的作用可以參考第三講）
|
1
2
3
4
5
|
func evacuated(b *bmap) bool { h := b.tophash[0] // 這個(gè)區(qū)間的flag 均是已被轉(zhuǎn)移 return h > emptyOne && h < minTopHash} |
② 如果沒(méi)有被轉(zhuǎn)移，那就要遷移數(shù)據(jù)了。數(shù)據(jù)遷移時(shí)，可能是遷移到大小相同的buckets上，也可能遷移到2倍大的buckets上。這里xy 都是標(biāo)記目標(biāo)遷移位置的標(biāo)記：x 標(biāo)識(shí)的是遷移到相同的位置，y 標(biāo)識(shí)的是遷移到2倍大的位置上。我們先看下目標(biāo)位置的確定：
|
1
2
3
4
5
6
7
8
9
10
11
12
|
var xy [2]evacDstx := &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() { // 如果是2倍的大小，就得算一次 y 的值 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))} |
③ 確定bucket位置后，需要按照kv 一條一條做遷移。（目的就是清除空閑的kv）
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
// 遍歷每個(gè)bucketfor ; b != nil; b = b.overflow(t) { k := add(unsafe.Pointer(b), dataOffset) v := add(k, bucketCnt*uintptr(t.keysize)) // 遍歷bucket 里面的每個(gè)kv for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) { top := b.tophash[i] // 空的不做遷移 if isEmpty(top) { b.tophash[i] = evacuatedEmpty continue } if top < minTopHash { throw("bad map state") } k2 := k if t.indirectkey() { k2 = *((*unsafe.Pointer)(k2)) } var useY uint8 if !h.sameSizeGrow() { // 2倍擴(kuò)容的需要重新計(jì)算hash， hash := t.key.alg.hash(k2, uintptr(h.hash0)) if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.alg.equal(k2, k2) { useY = top & 1 top = tophash(hash) } else { if hash&newbit != 0 { useY = 1 } } } // 這些是固定值的校驗(yàn)，可以忽略 if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY { throw("bad evacuatedN") } // 設(shè)置oldbucket 的tophash 為已搬遷 b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY dst := &xy[useY] // evacuation destination if dst.i == bucketCnt { // 如果dst是bucket 里面的最后一個(gè)kv，則需要添加一個(gè)overflow dst.b = h.newoverflow(t, dst.b) dst.i = 0 dst.k = add(unsafe.Pointer(dst.b), dataOffset) dst.v = add(dst.k, bucketCnt*uintptr(t.keysize)) } // 填充tophash值， kv 數(shù)據(jù) dst.b.tophash[dst.i&(bucketCnt-1)] = top if t.indirectkey() { *(*unsafe.Pointer)(dst.k) = k2 } else { typedmemmove(t.key, dst.k, k) } if t.indirectvalue() { *(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v) } else { typedmemmove(t.elem, dst.v, v) } // 更新目標(biāo)的bucket dst.i++ dst.k = add(dst.k, uintptr(t.keysize)) dst.v = add(dst.v, uintptr(t.valuesize)) }} |
對(duì)于key 非間接使用的數(shù)據(jù)（即非指針數(shù)據(jù)），做內(nèi)存回收
|
1
2
3
4
5
6
7
8
|
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 // ptr 是kv的位置， 前面的topmap 保留，做遷移前的校驗(yàn)使用 memclrHasPointers(ptr, n)} |
④ 如果當(dāng)前搬遷的bucket 和 總體搬遷的bucket的位置是一樣的，我們需要更新總體進(jìn)度的標(biāo)記 nevacuate
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
// newbit 是oldbuckets 的長(zhǎng)度，也是nevacuate 的重點(diǎn)func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) { // 首先更新標(biāo)記 h.nevacuate++ // 最多查看2^10 個(gè)bucket stop := h.nevacuate + 1024 if stop > newbit { stop = newbit } // 如果沒(méi)有搬遷就停止了，等下次搬遷 for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) { h.nevacuate++ } // 如果都已經(jīng)搬遷完了，oldbukets 完全搬遷成功，清空oldbuckets if h.nevacuate == newbit { h.oldbuckets = nil if h.extra != nil { h.extra.oldoverflow = nil } h.flags &^= sameSizeGrow }} |
總結(jié)
- Map 的賦值難點(diǎn)在于數(shù)據(jù)的擴(kuò)容和數(shù)據(jù)的搬遷操作。
- bucket 搬遷是逐步進(jìn)行的，每進(jìn)行一次賦值，會(huì)做至少一次搬遷工作。
- 擴(kuò)容不是一定會(huì)新增空間，也有可能是只是做了內(nèi)存整理。
- tophash 的標(biāo)志即可以判斷是否為空，還會(huì)判斷是否搬遷，以及搬遷的位置為X or Y。
- delete map 中的key，有可能出現(xiàn)很多空的kv，會(huì)導(dǎo)致搬遷操作。如果可以避免，盡量避免。
到此這篇關(guān)于Golang Map實(shí)現(xiàn)賦值和擴(kuò)容的示例代碼的文章就介紹到這了,更多相關(guān)Golang Map 賦值和擴(kuò)容內(nèi)容請(qǐng)搜索服務(wù)器之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持服務(wù)器之家！
原文鏈接：https://www.cnblogs.com/-lee/p/12807063.html
