golang map 操作，是map 實現(xiàn)中較復(fù)雜的邏輯。因為當(dāng)賦值時，為了減少hash 沖突鏈的長度過長問題，會做map 的擴容以及數(shù)據(jù)的遷移。而map 的擴容以及數(shù)據(jù)的遷移也是關(guān)注的重點。
數(shù)據(jù)結(jié)構(gòu)
首先，我們需要重新學(xué)習(xí)下map實現(xiàn)的數(shù)據(jù)結(jié)構(gòu)：
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 實現(xiàn)的結(jié)構(gòu)體。大部分字段在 第一節(jié)中已經(jīng)學(xué)習(xí)過了。剩余的就是nevacuate 和extra 了。
首先需要了解搬遷的概念：當(dāng)hash 中數(shù)據(jù)鏈太長，或者空的bucket 太多時，會操作數(shù)據(jù)搬遷，將數(shù)據(jù)挪到一個新的bucket 上，就的bucket數(shù)組成為了oldbuckets。bucket的搬遷不是一次就搬完的，是訪問到對應(yīng)的bucket時才可能會觸發(fā)搬遷操作。（這一點是不是和redis 的擴容比較類似，將擴容放在多個訪問上，減少了單次訪問的延遲壓力）
- nevactuate 標(biāo)識的是搬遷的位置(也可以考慮為搬遷的進(jìn)度）。標(biāo)識目前 oldbuckets 中 （一個 array）bucket 搬遷到哪里了。
- extra 是一個map 的結(jié)構(gòu)體，nextOverflow 標(biāo)識的是申請的空的bucket，用于之后解決沖突時使用；overflow 和 oldoverflow 標(biāo)識溢出的鏈表中正在使用的bucket 數(shù)據(jù)。old 和非old 的區(qū)別是，old 是為搬遷的數(shù)據(jù)。
理解了大概的數(shù)據(jù)結(jié)構(gòu)，我們可以學(xué)習(xí)map的 賦值操作了。
map 賦值操作
map 的賦值操作寫法如下：
data := mapExample["hello"]
賦值的實現(xiàn)，golang 為了對不同類型k做了優(yōu)化，下面時一些實現(xiàn)方法：
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 的實現(xiàn)。
mapassign 方法的實現(xiàn)是查找一個空的bucket，把key賦值到bucket上，然后把val的地址返回,然后直接通過匯編做內(nèi)存拷貝。
那我們一步步看是如何找空閑bucket的：
① 在查找key之前，會做異常檢測，校驗map是否未初始化，或正在并發(fā)寫操作，如果存在，則拋出異常：（這就是為什么map 并發(fā)寫回panic的原因）
if h == nil {
panic(plainError("assignment to entry in nil map"))
}
// 竟態(tài)檢查 和 內(nèi)存掃描
if h.flagshashWriting != 0 {
throw("concurrent map writes")
}
② 需要計算key 對應(yīng)的hash 值，如果buckets 為空（初始化的時候小于一定長度的map 不會初始化數(shù)據(jù)）還需要初始化一個bucket
alg := t.key.alg
hash := alg.hash(key, uintptr(h.hash0))
// 為什么需要在hash 后設(shè)置flags，因為 alg.hash可能會panic
h.flags ^= hashWriting
if h.buckets == nil {
h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
}
③ 通過hash 值，獲取對應(yīng)的bucket。如果map 還在遷移數(shù)據(jù)，還需要在oldbuckets中找對應(yīng)的bucket，并搬遷到新的bucket。
// 通過hash 計算bucket的位置偏移
bucket := hash bucketMask(h.B)
// 此處是搬遷邏輯，我們后續(xù)詳解
if h.growing() {
growWork(t, h, bucket)
}
// 計算對應(yīng)的bucket 位置，和top hash 值
b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + bucket*uintptr(t.bucketsize)))
top := tophash(hash)
④ 拿到bucket之后，還需要按照鏈表方式一個一個查，找到對應(yīng)的key， 可能是已經(jīng)存在的key，也可能需要新增。
for {
for i := uintptr(0); i bucketCnt; i++ {
// 若 tophash 就不相等，那就取tophash 中的下一個
if b.tophash[i] != top {
// 若是個空位置，把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ù)無數(shù)據(jù)，那就不用再找坑了
if b.tophash[i] == emptyRest {
break bucketloop
}
continue
}
// 若tophash匹配時
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 也相等，說明之前有數(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
}
// 取下一個overflow （鏈表指針）
ovf := b.overflow(t)
if ovf == nil {
break
}
b = ovf
}
總結(jié)下這段程序，主要有幾個部分：
a. map hash 不匹配的情況，會看是否是空kv 。如果調(diào)用了delete，會出現(xiàn)空kv的情況，那先把地址留下，如果后面也沒找到對應(yīng)的k（也就是說之前map 里面沒有對應(yīng)的Key），那就直接用空kv的位置即可。
b. 如果 map hash 是匹配的，需要判定key 的字面值是否匹配。如果不匹配，還需要查找。如果匹配了，那直接把key 更新（因為可能有引用），v的地址返回即可。
c. 如果上面都沒有，那就看下一個bucket
⑤ 插入數(shù)據(jù)前，會先檢查數(shù)據(jù)太多了，需要擴容，如果需要擴容，那就從第③開始拿到新的bucket，并查找對應(yīng)的位置。
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
}
⑥ 如果剛才看沒有有空的位置，那就需要在鏈表后追加一個bucket，拿到kv。
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 約束
// 如果非指針數(shù)據(jù)（也就是直接賦值的數(shù)據(jù)），還需要申請內(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, k
typedmemmove(t.key, insertk, key)
*inserti = top
done:
if h.flagshashWriting == 0 {
throw("concurrent map writes")
}
h.flags ^= hashWriting
if t.indirectvalue() {
val = *((*unsafe.Pointer)(val))
}
return val
到這里，map的賦值基本就介紹完了。下面學(xué)習(xí)下步驟⑤中的map的擴容。
Map 的擴容
有兩種情況下，需要做擴容。一種是存的kv數(shù)據(jù)太多了，已經(jīng)超過了當(dāng)前map的負(fù)載。還有一種是overflow的bucket過多了。這個閾值是一個定值，經(jīng)驗得出的結(jié)論，所以我們這里不考究。
當(dāng)滿足條件后，將開始擴容。如果滿足條件二，擴容后的buckets 的數(shù)量和原來是一樣的，說明可能是空kv占據(jù)的坑太多了，通過map擴容做內(nèi)存整理。如果是因為kv 量多導(dǎo)致map負(fù)載過高，那就擴一倍的量。
func hashGrow(t *maptype, h *hmap) {
bigger := uint8(1)
// 如果是第二種情況，擴容大小為0
if !overLoadFactor(h.count+1, h.B) {
bigger = 0
h.flags |= sameSizeGrow
}
oldbuckets := h.buckets
// 申請一個大數(shù)組，作為新的buckets
newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
flags := h.flags ^ (iterator | oldIterator)
if h.flagsiterator != 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的擴容操作。首先拿到擴容的大小，然后申請大數(shù)組，然后做些初始化的操作，把老的buckets，以及overflow做切換即可。
map 數(shù)據(jù)的遷移
擴容完成后，需要做數(shù)據(jù)的遷移。數(shù)據(jù)的遷移不是一次完成的，是使用時才會做對應(yīng)bucket的遷移。也就是逐步做到的數(shù)據(jù)遷移。下面我們來學(xué)習(xí)。
在數(shù)據(jù)賦值的第③步，會看需要操作的bucket是不是在舊的buckets里面，如果在就搬遷。下面是搬遷的具體操作：
func growWork(t *maptype, h *hmap, bucket uintptr) {
// 首先把需要操作的bucket 搬遷
evacuate(t, h, bucketh.oldbucketmask())
// 再順帶搬遷一個bucket
if h.growing() {
evacuate(t, h, h.nevacuate)
}
}
nevacuate 標(biāo)識的是當(dāng)前的進(jìn)度，如果都搬遷完，應(yīng)該和2^B的長度是一樣的（這里說的B是oldbuckets 里面的B，畢竟新的buckets長度可能是2^(B+1))。
在evacuate 方法實現(xiàn)是把這個位置對應(yīng)的bucket，以及其沖突鏈上的數(shù)據(jù)都轉(zhuǎn)移到新的buckets上。
① 先要判斷當(dāng)前bucket是不是已經(jīng)轉(zhuǎn)移。 (oldbucket 標(biāo)識需要搬遷的bucket 對應(yīng)的位置)
b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
// 判斷
if !evacuated(b) {
// 做轉(zhuǎn)移操作
}
轉(zhuǎn)移的判斷直接通過tophash 就可以，判斷tophash中第一個hash值即可 （tophash的作用可以參考第三講）
func evacuated(b *bmap) bool {
h := b.tophash[0]
// 這個區(qū)間的flag 均是已被轉(zhuǎn)移
return h > emptyOne h minTopHash
}
② 如果沒有被轉(zhuǎn)移，那就要遷移數(shù)據(jù)了。數(shù)據(jù)遷移時，可能是遷移到大小相同的buckets上，也可能遷移到2倍大的buckets上。這里xy 都是標(biāo)記目標(biāo)遷移位置的標(biāo)記：x 標(biāo)識的是遷移到相同的位置，y 標(biāo)識的是遷移到2倍大的位置上。我們先看下目標(biāo)位置的確定：
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() {
// 如果是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）
// 遍歷每個bucket
for ; b != nil; b = b.overflow(t) {
k := add(unsafe.Pointer(b), dataOffset)
v := add(k, bucketCnt*uintptr(t.keysize))
// 遍歷bucket 里面的每個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倍擴容的需要重新計算hash，
hash := t.key.alg.hash(k2, uintptr(h.hash0))
if h.flagsiterator != 0 !t.reflexivekey() !t.key.alg.equal(k2, k2) {
useY = top 1
top = tophash(hash)
} else {
if hashnewbit != 0 {
useY = 1
}
}
}
// 這些是固定值的校驗，可以忽略
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 里面的最后一個kv，則需要添加一個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))
}
}
對于key 非間接使用的數(shù)據(jù)（即非指針數(shù)據(jù)），做內(nèi)存回收
if h.flagsoldIterator == 0 t.bucket.kindkindNoPointers == 0 {
b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
ptr := add(b, dataOffset)
n := uintptr(t.bucketsize) - dataOffset
// ptr 是kv的位置， 前面的topmap 保留，做遷移前的校驗使用
memclrHasPointers(ptr, n)
}
④ 如果當(dāng)前搬遷的bucket 和 總體搬遷的bucket的位置是一樣的，我們需要更新總體進(jìn)度的標(biāo)記 nevacuate
// newbit 是oldbuckets 的長度，也是nevacuate 的重點
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
// 首先更新標(biāo)記
h.nevacuate++
// 最多查看2^10 個bucket
stop := h.nevacuate + 1024
if stop > newbit {
stop = newbit
}
// 如果沒有搬遷就停止了，等下次搬遷
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 的賦值難點在于數(shù)據(jù)的擴容和數(shù)據(jù)的搬遷操作。
- bucket 搬遷是逐步進(jìn)行的，每進(jìn)行一次賦值，會做至少一次搬遷工作。
- 擴容不是一定會新增空間，也有可能是只是做了內(nèi)存整理。
- tophash 的標(biāo)志即可以判斷是否為空，還會判斷是否搬遷，以及搬遷的位置為X or Y。
- delete map 中的key，有可能出現(xiàn)很多空的kv，會導(dǎo)致搬遷操作。如果可以避免，盡量避免。
到此這篇關(guān)于Golang Map實現(xiàn)賦值和擴容的示例代碼的文章就介紹到這了,更多相關(guān)Golang Map 賦值和擴容內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
您可能感興趣的文章:- Golang 語言map底層實現(xiàn)原理解析
- golang映射Map的方法步驟
- Golang 使用map需要注意的幾個點
- golang中使用sync.Map的方法
- golang中range在slice和map遍歷中的注意事項
- golang 并發(fā)安全Map以及分段鎖的實現(xiàn)方法
- Golang自定義結(jié)構(gòu)體轉(zhuǎn)map的操作
