欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

Go數(shù)據(jù)結(jié)構(gòu)之映射map方式

 更新時間:2025年06月11日 09:00:13   作者:大P哥阿豪  
這篇文章主要介紹了Go數(shù)據(jù)結(jié)構(gòu)之映射map方式,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教

Map作為Go原生支持的另一個主要的數(shù)據(jù)結(jié)構(gòu),其使用頻繁程度與切片有過之而無不及。用一句話描述map:存儲鍵-值對映射關(guān)系的無序數(shù)據(jù)結(jié)構(gòu),保證鍵的唯一性但不保證并發(fā)操作安全。

本文將介紹map的基本使用以及go 1.16版本其底層實現(xiàn)。

1 map的使用

1.1 map基本使用

聲明/初始化,一般有如下三種方式,

  • 使用var聲明一個map變量,需要指定鍵值對分別的類型,這種方式僅僅只是聲明,返回的是一個nil map,既沒有分配內(nèi)存,無法對其進行寫入操作。如果要對其進行寫入操作,則還需要為其分配內(nèi)存。
  • 比較常用的是直接使用make初始化,在初始化map類型時,可以傳一個容量(通常是不傳這個參數(shù),因為map底層有自動擴容機制,且無法準(zhǔn)確預(yù)估m(xù)ap所需的容量)。
  • 第三種方式就是直接在定義的同時,對map進行寫入操作,這種方式適用于確定部分需要寫入map的場景
// 聲明一個map變量,鍵是string類型,值是int類型
// 但此時m還是一個nil map,無法對其進行寫入
var m map[string]int 
m["1"] = 1 // 報錯,nil map無法寫入

m = make(map[string]int) // 使用make為map分配內(nèi)存,此時可以正常寫入


// 可以將聲明和分配內(nèi)存合二為一,直接使用make函數(shù)為map分配內(nèi)存
// make函數(shù)第一個參數(shù)是map的類型,第二個參數(shù)可選,表示map的容量大小
m1 := make(map[string]int)

// 第三種方式就是在定義的時候,連帶著給map進行賦值
m2 := map[string]int{
    "1": 1,
    "2": 2,
}

賦值,其實就比較簡單,直接將鍵放入中括號,對應(yīng)的值放在等號右邊即可,如果鍵之間存在,則實現(xiàn)更新;不存在,則實現(xiàn)插入。這里需要特別注意的是

  • 對于nil map無法進行賦值操作,如果對nil map進行賦值,則會panic。
  • map中的value是不可尋址的,無法直接通過map值進行更新操作,但有兩種例外,1)value為int類型,編譯器會通過語法糖進行直接更新;2)value為指針類型時,也能直接通過map值進行更新操作。
m := make(map[string]int)
m["1"] = 1

type Person struct {
	name string
	age  int
}

m1 := map[string]Person{}
m1["Tom"].age++ // 錯誤,因為map的值是無法尋址的,這種情況需要接受舊值,將修改完后的值重新賦值

m2 := map[string]*Person{}
m2["Tom"].age++ // 正確,這種情況下沒有改變map中的value,而是通過指針找到對應(yīng)存儲的值進行修改
  • 查找,map對于查詢的處理原則就是,如果key不存在,則返回value對應(yīng)的零值(nil map也能進行查找,只是對于所有的查詢都返回value類型零值)。如果需要判斷key是否存在,則推薦使用v, ok := m["1"]的寫法,ok為true表示key存在于map中。
var m map[string]int
fmt.Println(m["1"]) // nil map可以進行查找,返回的是value的默認(rèn)零值

// 如果需要判斷key是否存在于map中,則可以使用如下寫法
if _, ok := m["1"]; ok {
    fmt.Println("key存在")
} else {
    fmt.Println("key不存在")
}
  • 刪除,主要通過調(diào)用delete函數(shù)實現(xiàn)map中鍵值對的刪除操作,對于nil map也能執(zhí)行刪除操作,如果待刪除的key不存在,則不做任何處理。
var m map[string]int
delete(m ,"1")
  • 遍歷,只能通過for range進行map的遍歷操作,而且遍歷是無序的,每次遍歷結(jié)果都不一樣,這樣做:一是為了讓使用者不依賴于map的遍歷順序,二也是與map的底層實現(xiàn)有很大關(guān)系。實際開發(fā)過程中,如果要確定的遍歷順序,往往需要借助切片保存順序,然后通過遍歷切片去map中取值。
m := map[string]int{
    "1": 1,
    "2": 2,
}

// 無序遍歷,每次遍歷的順序都不一樣
for k, v := range m {
    fmt.Println(k, v)
}

1.2 map注意事項

map是一種引用傳遞類型,其作為函數(shù)參數(shù)進行傳遞時,函數(shù)內(nèi)部修改會直接影響調(diào)用者。

map遍歷是無序的,即每次遍歷的結(jié)果都不一樣,可能是Go的設(shè)計者不想使用者依賴與map的遍歷順序性,個人認(rèn)為這個也是與其底層實現(xiàn)有關(guān),如果要保證有序,則需要維護額外的數(shù)據(jù)結(jié)構(gòu),與Go極簡的設(shè)計原則不符。

map的key必須是支持==、!=運算的數(shù)據(jù)類型(map的key可以為float類型、chan類型自定義結(jié)構(gòu)體,但不能是func、map、slice,value則可以為任意數(shù)據(jù)類型)。

因內(nèi)存訪問安全和哈希算法等緣故,字典被設(shè)置成“not addressable”,故不能直接修改value的值(實際上就是不允許直接修改map中的值)。如果需要對value進行修改,一般將需要將整個value返回,修改后再重新賦值,或直接將value設(shè)置成指針類型(指針能修改的原因是,通過指針修改原結(jié)構(gòu)體中的數(shù)據(jù),但沒有修改map中保存的數(shù)據(jù))。但是,如果map的value為int,那么可以直接修改value,例如:

m := map[string]int{"test":1}

m["test"]++  // 實際上是語法糖
/* 
temp := m["test"]
temp += 1
m["test"] = temp
*/

map并不是多線程讀寫安全的,在多線程開發(fā)中使用map需要特別小心,解決此問題一般可以使用sync.RWMutex進行保護或直接使用sync.Map。

訪問不存在的主鍵,返回對應(yīng)key的零值,并不會panic。刪除不存在的鍵值,也不會引發(fā)錯誤。

可對nil的字典進行讀、刪除操作,但是寫會引發(fā)panic!即,從nil的字典中,讀出來的都是value的默認(rèn)值;對nil字典進行刪除操作,實際不會產(chǎn)生任何效果。

2 map的底層數(shù)據(jù)結(jié)構(gòu)

在Go 1.16版本中,使用了hash table來實現(xiàn)map(Go 1.24版本已經(jīng)使用Swiss table作為map的底層實現(xiàn),后續(xù)有空研究下),其底層實現(xiàn)主要借助hmap、bmap,下面詳細介紹下這兩個數(shù)據(jù)。

2.1 bmap

bmap是Go map中bucket的抽象,為提高存儲效率,每一個 bmap 都能存儲 8 個鍵值對。

當(dāng)哈希表中存儲的數(shù)據(jù)過多,單個桶已經(jīng)裝滿時就會使用 extra.nextOverflow 中桶存儲溢出的數(shù)據(jù)。上述兩種不同的桶在內(nèi)存中是連續(xù)存儲的,我們在這里將它們分別稱為正常桶和溢出桶。

bucket的結(jié)構(gòu)體 bmap 在 Go 語言源代碼中的定義只包含一個簡單的 tophash 字段,tophash 存儲了鍵的哈希的高 8 位,通過比較不同鍵的哈希的高 8 位可以減少訪問鍵值對次數(shù)以提高性能。在運行期間,bmap 結(jié)構(gòu)體其實不止包含 tophash 字段,因為哈希表中可能存儲不同類型的鍵值對,而且 Go 語言也不支持泛型,所以鍵值對占據(jù)的內(nèi)存空間大小只能在編譯時進行推導(dǎo)。runtime.bmap 中的其他字段在運行時也都是通過計算內(nèi)存地址的方式訪問的,所以它的定義中就不包含這些字段,不過我們能根據(jù)編譯期間的 cmd/compile/internal/gc.bmap 函數(shù)重建它的結(jié)構(gòu):

type bmap struct {
    tophash [bucketCnt]uint8
}

// 利用../go/src/cmd/compile/internal/gc/reflect.go文件中的bmap函數(shù)反推
type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    overflow uintptr
}

桶和溢出桶

  • 桶(bucket): 每個桶包含固定數(shù)量的鍵值對,Go 中每個桶默認(rèn)可以存儲 8 對鍵值對。
  • 溢出桶(overflow bucket): 當(dāng)一個桶已滿但仍需插入新的鍵值對時,會創(chuàng)建一個新的桶作為當(dāng)前桶的溢出桶。

溢出桶的作用

解決哈希沖突:

  • 在理想情況下,每個鍵會被分配到不同的桶中。然而,在實際應(yīng)用中,由于哈希函數(shù)的特性,多個鍵可能會被分配到同一個桶中(即哈希沖突)。
  • 當(dāng)一個桶已滿且仍然需要存儲新的鍵值對時,Go 會創(chuàng)建一個新的桶作為當(dāng)前桶的溢出桶,并將新鍵值對存儲在這個溢出桶中。

管理存儲空間:

  • 溢出桶允許動態(tài)擴展 map 的存儲容量。通過使用鏈表結(jié)構(gòu)(由多個溢出桶組成),可以有效地管理超過初始桶容量的數(shù)據(jù)。
  • 這種機制避免了頻繁地重新分配和復(fù)制整個哈希表,從而提高了性能。

高效查找:

  • 即使存在多個溢出桶,Go 的 map 實現(xiàn)仍然能夠高效地進行鍵值對的查找。通過遍歷主桶及其關(guān)聯(lián)的溢出桶,可以快速找到所需的鍵值對。
  • 溢出桶的設(shè)計確保了查找操作在平均情況下仍然是 O(1) 時間復(fù)雜度。

2.2 hmap

hmap是Go實現(xiàn)map的底層數(shù)據(jù)結(jié)構(gòu),主要用于管理bucket的擴容、元素的查找/刪除等,其具體結(jié)構(gòu)如下:

 type hmap struct {
   count       int        // 元素個數(shù),調(diào)用 len(map) 時,直接返回此值
   flags       uint8      // 標(biāo)記,對應(yīng) const 中 '// flags' 下的幾個狀態(tài)
   B           uint8      // buckets 的對數(shù) log_2
   noverflow   uint16     // overflow 的 bucket 近似數(shù)
   hash0       uint32     // 計算 key 的哈希的時候會傳入哈希函數(shù)
   buckets     unsafe.Pointer    // 指向 buckets 數(shù)組,大小為 2^B。如果元素個數(shù)為0,就為 nil
                                 // 擴容的時候,buckets 長度會是 oldbuckets 的兩倍
   oldbuckets unsafe.Pointer     // 指向擴容前的數(shù)組(漸進式擴容)
   nevacuate  uintptr            // 指示擴容進度,小于此地址的 buckets 遷移完成
   extra      *mapextra          //保存溢出桶的信息
}


type mapextra struct {
   // 如果 key 和 value 都不包含指針,并且可以被 inline(<=128 字節(jié))
   // 使用 extra 來存儲 overflow bucket,這樣可以避免 GC 掃描整個 map
   // 然而 bmap.overflow 也是個指針。這時候我們只能把這些 overflow 的指針
   // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
   overflow    *[]*bmap // overflow 包含的是 hmap.buckets 的 overflow 的 bucket
   oldoverflow *[]*bmap // oldoverflow 包含擴容時的 hmap.oldbuckets 的 overflow 的 bucket

   nextOverflow *bmap // 指向空閑的 overflow bucket 的指針
}

3 map實現(xiàn)源碼

3.1 map的初始化

使用make函數(shù)創(chuàng)建map:

make(map[k]v, hint)

在 hint <= 8(鍵值對的個數(shù)) 時,會調(diào)用 makemap_small 來進行初始化,如果 hint > 8,則調(diào)用 makemap。在預(yù)估待插入的元素個數(shù)小于8或者需要的bucket為0時,Go編譯器會采用延遲分配策略,只有在真正往map中寫入數(shù)據(jù)時, 才會分配bucket。

makemap函數(shù)主要流程如下:

  • 內(nèi)存安全檢查:通過計算預(yù)估內(nèi)存 = 元素數(shù)量(hint) × 單個桶大小(t.bucket.size),防止內(nèi)存溢出攻擊和無效分配,若檢測失敗,將 hint 重置為 0(后續(xù)按最小分配處理)
  • 初始化 hmap 結(jié)構(gòu)體:若傳入 h 為 nil,新建 hmap 結(jié)構(gòu)(map 的底層表示);隨后h.hash0 = fastrand():生成隨機哈希種子,用于增加哈希隨機性,防止哈希碰撞攻擊,相同 key 在不同 map 中產(chǎn)生不同哈希值
  • 計算桶數(shù)量指數(shù) B:根據(jù)負(fù)載因子確定合適的桶數(shù)量(2^B 個桶),循環(huán)增加 B 直到滿足:6.5 * 2^B >= hint
  • 分配桶數(shù)組:若 B == 0(hint=0),延后到首次寫入時分配;其他情況,調(diào)用makeBucketArray 分配主桶數(shù)組(長度為 2^B),如果 B >= 4 額外預(yù)分配溢出桶(減少運行時分配開銷,這里也說明正常桶與溢出桶是內(nèi)存地址連續(xù)的數(shù)組)
  • 溢出桶管理:若存在預(yù)分配溢出桶(nextOverflow != nil),初始化 h.extra 結(jié)構(gòu),記錄可用溢出桶鏈表。最后一個溢出桶的overflow指針會指向第一個正常桶,以此形成一個環(huán)。
func makemap_small() *hmap {
   h := new(hmap)
   h.hash0 = fastrand()
   return h
}

func makemap(t *maptype, hint int, h *hmap) *hmap {
   // 進行內(nèi)存大小的檢查,如果溢出或者內(nèi)存超出最大內(nèi)存空間,將hint(元素個數(shù))設(shè)置為0
   mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
   if overflow || mem > maxAlloc {
      hint = 0
   }

   // 初始化 Hmap,即如果當(dāng)前Hamp為空,則new hmap
   // 設(shè)置map的哈希計算種子隨機數(shù)hash0
   if h == nil {
      h = new(hmap)
   }
   h.hash0 = fastrand()

   // Find the size parameter B which will hold the requested # of elements.
   // For hint < 0 overLoadFactor returns false since hint < bucketCnt.
   // 按照提供的元素個數(shù),根據(jù)負(fù)載因子計算合理的 B 值,以確保 6.5 * 2 ^ B >= hint
   B := uint8(0)
   for overLoadFactor(hint, B) {
      B++
   }
   h.B = B

   // allocate initial hash table
   // if B == 0, the buckets field is allocated lazily later (in mapassign)
   // If hint is large zeroing this memory could take a while.
   // 初始化 hash table
   // 如果 B 等于 0,那么 buckets 就會在賦值( mapassign )的時候再分配
   // 如果長度比較大,分配內(nèi)存會花費長一點
   if h.B != 0 {
      var nextOverflow *bmap
      h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
      if nextOverflow != nil {
         h.extra = new(mapextra)
         h.extra.nextOverflow = nextOverflow
      }
   }

   return h
}

func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
   // uintptr(1) << ( b & (sys.PtrSize*8-1))  2^b
   base := bucketShift(b)
   nbuckets := base

   // 當(dāng)桶的數(shù)量小于2^4 時,由于數(shù)據(jù)較少、使用溢出桶的可能性較低,
   // 這時就會省略創(chuàng)建溢出桶的過程以減少額外開銷
   if b >= 4 {
      // 當(dāng)桶的數(shù)量多于2^4時,就會額外創(chuàng)建 2^(b-4)個溢出桶
      // 根據(jù)內(nèi)存的分配規(guī)則,計算出合適的內(nèi)存大小,并確定桶的數(shù)量
      nbuckets += bucketShift(b - 4)
      sz := t.bucket.size * nbuckets
      up := roundupsize(sz)
      if up != sz {
         nbuckets = up / t.bucket.size
      }
   }

   // 如果桶之前沒有分配內(nèi)存,就初始化一個數(shù)組
   // 反之,直接沿用之前的,并清理掉本次初始化所需要內(nèi)存大小的內(nèi)存,備用
   if dirtyalloc == nil {
      buckets = newarray(t.bucket, int(nbuckets))
   } else {
      // dirtyalloc was previously generated by
      // the above newarray(t.bucket, int(nbuckets))
      // but may not be empty.
      buckets = dirtyalloc
      size := t.bucket.size * nbuckets
      if t.bucket.ptrdata != 0 {
         memclrHasPointers(buckets, size)
      } else {
         memclrNoHeapPointers(buckets, size)
      }
   }

   // 如果創(chuàng)建的桶數(shù)量不等于2^b,說明分配了額外的溢出桶
   if base != nbuckets {
      // 2^b個桶后面就是溢出桶
      nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))

      // 取nextOverflow 里面的最后一個元素,并把最后一個buckets 的末尾偏移的指針指向空閑的bucket (目前就是第一個buckets了)
      last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize)))
      last.setoverflow(t, (*bmap)(buckets))
   }
   return buckets, nextOverflow
}

下圖是不同B值時,初始化得到的map,如果B小于4,則編譯器不會為map分配溢出桶(認(rèn)為map的規(guī)模比較小,需要使用到溢出桶的概率不大);只有在B大于等于4時,才會為map分配 2^(B-4)個溢出桶,需要注意的是正常桶與溢出桶在底層是一個內(nèi)存地址連續(xù)的數(shù)組!

3.2 map的賦值

map的賦值操作核心是:通過hash函數(shù),找到key插入到bmap數(shù)據(jù)的下標(biāo)索引,然后就需要遍歷該下標(biāo)包含的所有bucket,尋找第一個能插入的位置或者尋找該key是否已經(jīng)存在。hash值在這里的主要作用有兩個:

  • tophash:由于一個bucket存儲了8個鍵值對,為了快速比較key,編譯器會將hash值的前8位(64位操作系統(tǒng))存儲到bucket到tophash數(shù)組。
  • 確定bmap的索引:hash值與map的B值進行mask操作,確定該key存儲的下標(biāo)位置。

賦值操作底層mapassign函數(shù)的主要流程:

1. 安全檢查和初始化

  • 空 map 檢查:對 nil map 賦值會 panic
  • 并發(fā)寫檢查:檢測到其他 goroutine 正在寫 map 時拋出異常(Go map 非并發(fā)安全)
  • 哈希計算:使用類型特定的哈希函數(shù)計算鍵的哈希值
  • 標(biāo)記寫操作:設(shè)置 hashWriting 標(biāo)志位(防止并發(fā)寫)
  • 延遲初始化:若桶數(shù)組未分配,分配一個桶(最小化空 map 開銷)

2. 定位桶和搜索鍵

雙層循環(huán)搜索:外層遍歷對應(yīng)index下所有的bucket,內(nèi)層循環(huán)處理每個桶的 8 個槽。

  • 遍歷時,需要記錄第一個可以插入的位置。
  • 同時,需要遍歷完全插入位置下,所有的bucket。如果遇到tophash相等,進一步判斷key是否一致,key也相等,則更新key的信息并結(jié)束循環(huán)。
  • 遇到 emptyRest(后續(xù)全空)時,提前終止搜索。

3. 鍵不存在時的處理

  • 擴容條件:負(fù)載因子超標(biāo)(count/(2^B) > 6.5);溢出桶過多(noverflow >= 2^min(B, 15))。
  • 擴容后重試:桶布局改變需重新定位
  • 分配新溢出桶:當(dāng)所有桶都無空閑槽時,則申請一個溢出桶

4. 收尾工作

  • 返回值的存儲位置:調(diào)用方通過此指針寫入值
  • 間接值處理:若值類型為指針,返回實際值地址
/*
 t *maptype:map 的類型信息
 h *hmap:map 的底層結(jié)構(gòu)
 key unsafe.Pointer:要插入或更新的鍵
 返回:指向值存儲位置的指針(寫入值需通過此指針)
*/
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   // 對于nil的map不能進行寫操作,直接panic
   if h == nil {
      panic(plainError("assignment to entry in nil map"))
   }
   if raceenabled {
      callerpc := getcallerpc()
      pc := funcPC(mapassign)
      racewritepc(unsafe.Pointer(h), callerpc, pc)
      raceReadObjectPC(t.key, key, callerpc, pc)
   }
   if msanenabled {
      msanread(key, t.key.size)
   }

   // 如果有別的goroutine正在寫此map,即發(fā)生了并發(fā)寫,直接異常退出
   if h.flags&hashWriting != 0 {
      throw("concurrent map writes")
   }
   // 計算需要寫入的key的hash值
   hash := t.hasher(key, uintptr(h.hash0))

   // 調(diào)用hasher函數(shù)時,可能發(fā)生paninc,因此沒法完成一次寫操作
   // 如果hasher沒有發(fā)生panic,那么將flags設(shè)置成flags += 4
   h.flags ^= hashWriting

   // 如果bucket沒有被分配內(nèi)存,則分配一個bucket(延遲初始化)
   if h.buckets == nil {
      h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   }

again:
   //  計算低 8 位 hash,根據(jù)計算出的 bucketMask 選擇對應(yīng)的 bucket 編號
   bucket := hash & bucketMask(h.B)
   //  如果map正在擴容,則完成搬遷工作
   if h.growing() {
      growWork(t, h, bucket)
   }
   // 計算key對應(yīng)桶編號的地址,以及hash值的高8位
   b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   top := tophash(hash)

   var inserti *uint8            //  需要寫入tophash數(shù)組的下標(biāo)
   var insertk unsafe.Pointer    //  寫入key的對象指針(地址)
   var elem unsafe.Pointer       //  寫入value的對象指針(地址),即返回值
bucketloop:
   //  開啟雙層循環(huán),外層遍歷bucket的所有overflow桶,內(nèi)層遍歷每個bucket的cell
   //  目的:找到空的cell(key不存在),或者top所在的位置(key已存在)
   for {
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top { // 當(dāng)前top不一致,繼續(xù)比對下一個
            // 找到第一個空的cell,并保存下表以及地址信息
            if isEmpty(b.tophash[i]) && inserti == nil {
               inserti = &b.tophash[i]
               insertk = add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
               elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            }
            // 此cell為空且后面也都是空cell,那么inserti必定已不為空。
            // 這種情況直接退出bucket cell的遍歷
            if b.tophash[i] == emptyRest {
               break bucketloop
            }
            continue
         }

         // 如果b.tophash[i] == top,計算key對應(yīng)的地址
         // k是指針對象,解引用
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         if t.indirectkey() {
            k = *((*unsafe.Pointer)(k))
         }

         // 如果相同的 hash 位置的 key 和要插入的 key 字面上不相等
         // 如果兩個 key 的首八位后最后八位哈希值一樣,就會進行其值比較,算是一種哈希碰撞吧
         if !t.key.equal(key, k) {
            continue
         }
         // map已經(jīng)有此key存在了,那么直接更新
         if t.needkeyupdate() {
            typedmemmove(t.key, k, key)
         }
         elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
         goto done
      }

      //  bucket 的 8 個槽沒有滿足條件的能插入或者能更新的,去 overflow 里繼續(xù)找
      //  overflow 為 nil,說明到了 overflow 鏈表的末端了,退出外層循環(huán)
      ovf := b.overflow(t)
      if ovf == nil {
         break
      }
      // 賦值為鏈表的下一個元素,繼續(xù)循環(huán)
      b = ovf
   }

   // 沒有找到 key,分配新的空間
   // 如果觸發(fā)了最大的 load factor,或者已經(jīng)有太多 overflow buckets
   // 并且這個時刻沒有在進行 growing 的途中,那么就開始 growing
   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
   }

   if inserti == nil {
      // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
      // 前面在桶里找的時候,沒有找到能塞這個 tophash 的位置
      // 說明當(dāng)前所有 buckets 都是滿的,分配一個新的 bucket
      newb := h.newoverflow(t, b)
      inserti = &newb.tophash[0]
      insertk = add(unsafe.Pointer(newb), dataOffset)
      elem = add(insertk, bucketCnt*uintptr(t.keysize))
   }

   // store new key/elem at insert position
   if t.indirectkey() { // 如果鍵的比較大,則直接使用指針存儲
      kmem := newobject(t.key)
      // 二級指針,insertk看作是指向指針的指針
      *(*unsafe.Pointer)(insertk) = kmem
      insertk = kmem
   }
   if t.indirectelem() {
      vmem := newobject(t.elem)
      *(*unsafe.Pointer)(elem) = vmem
   }
   typedmemmove(t.key, insertk, key)
   *inserti = top
   h.count++

done:
   // 禁止并發(fā)寫
   if h.flags&hashWriting == 0 {
      throw("concurrent map writes")
   }
   // flags對hashWriting按位置0,'^='表示按右邊hashWriting二進制為1的位置,置0
   // 還原寫操作之前的flags
   h.flags &^= hashWriting
   if t.indirectelem() {
      // 如果value是個大對象,則bucket中存儲的是對象地址unsafe.Pointer,取出存放value對象的地址
      elem = *((*unsafe.Pointer)(elem))
   }
   return elem
}

3.3 map的查找

mapaccess1、mapaccess2、mapaccessk是常用的map查找函數(shù),三個函數(shù)的主要實現(xiàn)基本類似,主要區(qū)別在于函數(shù)的返回值不同。

  • mapaccess1只有一個value的返回值,v := m[k]時調(diào)用,如果k不存在,返回的是value類型對應(yīng)的零值
  • mapaccess2返回value,bool,v, ok := m[k]時調(diào)用,如果k不存在,返回是value類型對應(yīng)的零值,false
  • mapaccessk返回key,value,如果k不存在,返回nil,nil

下面主要分析下mapaccess2函數(shù)的實現(xiàn):

安全性檢查

  • 空 map 處理:如果 map 為 nil 或元素數(shù)為 0,直接返回零值和 false
  • 特殊處理:如果鍵類型可能引發(fā) panic(如函數(shù)類型),調(diào)用哈希函數(shù)觸發(fā) panic
  • 讀寫沖突檢測:當(dāng)其他 goroutine 正在寫 map 時拋出異常(Go map 非并發(fā)安全)

計算哈希和定位桶

  • bucketMask(h.B):生成用于取模的掩碼(如 B=3 時,mask=0b111)
  • 桶定位公式:桶地址 = buckets起始地址 + (hash & mask) * 桶大小

擴容期間的特殊處理:當(dāng) map 正在擴容時,數(shù)據(jù)可能存在于新舊桶中(擴容有等量擴容與雙倍擴容兩種,詳細解釋見3.4節(jié)),如果是雙倍擴容,且該下標(biāo)還沒有遷移完成,則在老桶中查找

雙層循環(huán)搜索鍵值對

  • tophash 比較:先比較哈希高8位,快速過濾不匹配項
  • emptyRest 優(yōu)化:遇到標(biāo)記為 emptyRest 的槽位,表示后續(xù)全部為空,直接跳出循環(huán)

鍵值定位

  • 鍵位置:桶地址 + 數(shù)據(jù)偏移 + 索引 * 鍵大小
  • 值位置:桶地址 + 數(shù)據(jù)偏移 + 8*鍵大小 + 索引 * 值大小
  • 間接存儲處理:若鍵或值為指針類型,需解引用獲取實際數(shù)據(jù)
  • 未找到處理:返回預(yù)定義的零值地址和 false
/*
    t *maptype:map 的類型信息
    h *hmap:map 的底層結(jié)構(gòu)
    key unsafe.Pointer:要查找的鍵
    返回值:
        unsafe.Pointer:指向值的指針(未找到時指向零值)
        bool:表示鍵是否存在
*/
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool) {
   if raceenabled && h != nil {
      callerpc := getcallerpc()
      pc := funcPC(mapaccess2)
      racereadpc(unsafe.Pointer(h), callerpc, pc)
      raceReadObjectPC(t.key, key, callerpc, pc)
   }
   if msanenabled && h != nil {
      msanread(key, t.key.size)
   }

   // 如果map為空,或者元素個數(shù)為零,直接返回零值
   if h == nil || h.count == 0 {
      if t.hashMightPanic() {
         t.hasher(key, 0)
      }
      return unsafe.Pointer(&zeroVal[0]), false
   }

   // 讀、寫沖突
   if h.flags&hashWriting != 0 {
      throw("concurrent map read and map write")
   }

   // 計算哈希值,并且加入 hash0 引入隨機性
   hash := t.hasher(key, uintptr(h.hash0))
   // 如果 B = 3,那么結(jié)果用二進制表示就是 111,2^B-1
   m := bucketMask(h.B)
   // b 就是存儲key所在的 bucket 的地址
   b := (*bmap)(unsafe.Pointer(uintptr(h.buckets) + (hash&m)*uintptr(t.bucketsize)))

   // h.oldbuckets != nil時,說明 map 發(fā)生了擴容。這時候,新的 buckets 里可能還沒有老的內(nèi)容,
   // 所以一定要在老的里面找,否則有可能發(fā)生“消失”的詭異現(xiàn)象
   if c := h.oldbuckets; c != nil {
      if !h.sameSizeGrow() {
         // 如果不是等量擴容,新bucket的數(shù)量是老bucket的兩倍
         m >>= 1
      }
      // 求出 key 在老的 map 中的 bucket 位置
      oldb := (*bmap)(unsafe.Pointer(uintptr(c) + (hash&m)*uintptr(t.bucketsize)))
      // 如果oldb 沒有搬遷到新的 bucket,那就在老的 bucket 中尋找
      if !evacuated(oldb) {
         b = oldb
      }
   }
   // 計算高 8 位的 hash,相當(dāng)于右移 56 位,只取高8位
   top := tophash(hash)
bucketloop:
   // 兩層循環(huán),第一層遍歷bucket后面所有的溢出桶
   //         第二層遍歷每個桶內(nèi)部的8個key位置               
   for ; b != nil; b = b.overflow(t) {
      for i := uintptr(0); i < bucketCnt; i++ {
         // 如果top不匹配
         if b.tophash[i] != top {
            // emptyRest標(biāo)記此cell后面所有的key(包括overflow桶)都為空,此時直接跳出循環(huán)
            if b.tophash[i] == emptyRest {
               break bucketloop
            }
            continue
         }

         // 通過 bmap的地址+dataOffset+i*keysize 定位key的位置
         dataOffset = unsafe.Offsetof(struct{
            b bmap // bmap理解為[bucketCnt]uint8
            v int64
         }{}.v)
         
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         if t.indirectkey() {  // 如果key是指針,那么解引用
            k = *((*unsafe.Pointer)(k)) // 先將k轉(zhuǎn)化為*unsafe.Pointer類型,然后取出該地址存儲的值
         }
         // 如果key相等,定位value的位置,在map中找到了key-value,然后返回
         if t.key.equal(key, k) {
            e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            if t.indirectelem() { // 如果value是指針,那么解引用
               e = *((*unsafe.Pointer)(e))
            }
            return e, true
         }
      }
   }
   // 如果遍歷完所有的bucket(包括溢出桶),還沒找到,則返回零值
   return unsafe.Pointer(&zeroVal[0]), false
}

3.4 map的擴容

擴容是hash table中比較常見的一種操作,主要用于提高查詢效率。Go map的擴容觸發(fā)條件如下:

是不是已經(jīng)到了 load factor 的臨界點,即元素個數(shù) >= 桶個數(shù)*6.5,這時候說明大部分的桶可能都快滿了,如果插入新元素,有大概率需要掛在 overflow 的桶上。

overflow 的桶是不是太多了,

當(dāng) bucket 總數(shù) < 2 ^ 15 時,overflow 的 bucket 總數(shù) >= bucket 的總數(shù)

當(dāng) bucket 總數(shù) >= 2 ^ 15 時,overflow 的 bucket >= 2 ^ 15

滿足上述兩種情況時,就被認(rèn)為溢出桶太多了。為啥會導(dǎo)致這種情況呢?是因為我們對 map 一邊插入,一邊刪除,會導(dǎo)致其中很多桶出現(xiàn)空洞,這樣使得 bucket 使用率不高,值存儲得比較稀疏。在查找時效率會下降。

// 裝載因子超過 6.5
func overLoadFactor(count int64, B uint8) bool {
   return count >= bucketCnt && float32(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// overflow buckets 太多
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
   if B > 15 {
      B = 15
   }
   // The compiler doesn't see here that B < 16; mask B to generate shorter shift code.
   return noverflow >= uint16(1)<<(B&15)
}

針對上述兩種情況,采用了不同的解決方法:

  • 針對 1,將 B + 1,進而 hmap 的 bucket 數(shù)組擴容一倍;
  • 針對 2,通過移動 bucket 內(nèi)容,使其傾向于緊密排列從而提高 bucket 利用率(等量擴容)。

3.4.1 hashGrow函數(shù)

hashGrow函數(shù)只有在往map中新插入一個值,且需要觸發(fā)擴容時才會被調(diào)用。該函數(shù)主要根據(jù)擴容條件判斷需要執(zhí)行哪一種擴容,然后申請新的bucket內(nèi)存,更新bucket、oldbucket的信息,具體的遷移工作是由growWork 和 evacuate函數(shù)中完成的。Go map的擴容也采用的漸進式遷移,每一次賦值、刪除操作時,如果map處于擴容狀態(tài),則會保證key對應(yīng)的索引完全遷移(這樣,后續(xù)的操作只需要在h.bucket中完成即可),同時將h.nevacuate指示的下標(biāo)索引對應(yīng)的所有bucket也完成遷移。

func hashGrow(t *maptype, h *hmap) {
   // If we've hit the load factor, get bigger.
   // Otherwise, there are too many overflow buckets, so keep the same number of buckets and "grow" laterally.
   // 如果 load factor 超過了閾值,那么需要對 map 進行擴容,即 B = B + 1,bucket 總數(shù)會變?yōu)樵瓉淼亩?
   // 如果還沒到閾值,那么只需要保持相同數(shù)量的 bucket,橫向拍平就行了(等量擴容)
   bigger := uint8(1)
   if !overLoadFactor(h.count+1, h.B) {
      bigger = 0
      h.flags |= sameSizeGrow // 如果flags原先的值小于sameSizeGrow,h.flags += sameSizeGrow
   }

   // 將原先的bucket分給oldbuckets,然后申請新的bucket內(nèi)存
   oldbuckets := h.buckets
   newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)

   // 先把 h.flags 中 iterator 和 oldIterator 對應(yīng)位清 0,然后如果發(fā)現(xiàn) iterator 位為 1,那就把它轉(zhuǎn)接到 oldIterator 位,使得 oldIterator 標(biāo)志位變成 1。
   // 潛臺詞就是:buckets 現(xiàn)在掛到了 oldBuckets 名下了,對應(yīng)的標(biāo)志位也轉(zhuǎn)接過去吧。
   flags := h.flags &^ (iterator | oldIterator)
   if h.flags&iterator != 0 {
      flags |= oldIterator
   }

   // 更新map的信息
   h.B += bigger
   h.flags = flags
   h.oldbuckets = oldbuckets
   h.buckets = newbuckets
   h.nevacuate = 0
   h.noverflow = 0

   // 將原先的overflow搬到oldoverflow
   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
   }
   // 如果新的bucket有overflow bucket,賦值給nextOverflow
   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().
   // 實際的哈希表元素的拷貝工作是在 growWork 和 evacuate 中增量慢慢地進行的
}

3.4.3 evacuate函數(shù)

evacuate函數(shù)實現(xiàn)遷移的核心點在于:

  • evacDst 結(jié)構(gòu):跟蹤遷移目標(biāo)位置

等量擴容:只使用 x(相同索引位置,平行遷移)

翻倍擴容:使用 xy 兩個目標(biāo),將原來一個索引下的bucket內(nèi)容分配到新bmap數(shù)組的兩個相關(guān)索引下:

  • x:新桶數(shù)組低位(索引 = oldbucket
  • y:新桶數(shù)組高位(索引 = oldbucket + newbit

在翻倍擴容的時候,雖然鍵的哈希值沒有變化,但通過精妙的遷移策略和新索引計算機制,仍然能確保鍵的正確查找!翻倍擴容時,新掩碼(newbit) = 1 << B(B 是舊桶數(shù)量的指數(shù)),遷移到新桶數(shù)組到高位或地位,決定于hash & newbit。然后在查找時,使用新掩碼計算索引,在不改變hash函數(shù)的情況完美解決查找問題。(新舊mask的區(qū)別就是:新mask比舊值多了 B+1 bit位的判斷,后 B bit位還是保持一致,所以可以利用hash的第 B+1位值來確定key遷移到低位還是高位)

新索引 = {
舊索引 (當(dāng) hash & newbit == 0 時)
舊索引 + newbit (當(dāng) hash & newbit != 0 時)
} ======> 新索引 = hash & (newMask),新mask的第 B+1 bit位的值 == 2^B
newMask = (1 << (B+1)) - 1 = (1 << B) * 2 - 1 = newbit*2 - 1

假設(shè):

  • 舊 B=2 (4個桶,掩碼 0b11)
  • 新 B=3 (8個桶,掩碼 0b111)
  • newbit = 1<<2 = 4 (0b100)
  • 鍵哈希值:h = 13 (二進制 0b1101)
階段計算過程結(jié)果
舊索引h & 0b11 = 0b1101 & 0b00111 (0b01)
遷移決策h & newbit = 0b1101 & 0b01004 (非0) → 遷移到高位
新索引h & 0b111 = 0b1101 & 0b01115 (0b101)
驗證舊索引(1) + newbit(4)5

// evacDst is an evacuation destination.
type evacDst struct {
   b *bmap          // current destination bucket
   i int            // key/elem index into b
   k unsafe.Pointer // pointer to current key storage
   e unsafe.Pointer // pointer to current elem storage
}

// 該函數(shù)用于實現(xiàn)hmap擴容時,數(shù)據(jù)的搬遷工作
// 如果是等量擴容,那么就初始化一個evacDst
// 如果是翻倍擴容,那么就初始化兩個evacDst
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
   // 定位舊bucket的地址以及擴容前map的容量
   b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
   newbit := h.noldbuckets()
   // 如果 b 沒有被搬遷過
   if !evacuated(b) {
      // xy contains the x and y (low and high) evacuation destinations.
      // xy 包含的是移動的目標(biāo)
      // x 表示新 bucket 數(shù)組的前(low)半部分,y 表示新 bucket 數(shù)組的后(high)半部分
      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.e = add(x.k, bucketCnt*uintptr(t.keysize))

      if !h.sameSizeGrow() {
         // Only calculate y pointers if we're growing bigger.
         // Otherwise GC can see bad pointers.
         // 如果不是等 size 擴容,前后 bucket 序號有變,使用 y 來進行搬遷
         // 擴容后的map bucket數(shù)量是原先的兩倍,x,y分別各占一半,數(shù)量與擴容前一樣
         // y部分桶的編號: oldbucket+newbit
         y := &xy[1]
         y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
         y.k = add(unsafe.Pointer(y.b), dataOffset)
         y.e = add(y.k, bucketCnt*uintptr(t.keysize))
      }

      // 遍歷所有的 bucket,包括 overflow buckets,b 是老的 bucket 地址
      for ; b != nil; b = b.overflow(t) {
         // 從oldbucket的第一個cell開始
         k := add(unsafe.Pointer(b), dataOffset)
         e := add(k, bucketCnt*uintptr(t.keysize))
         // 遍歷 bucket 中的所有 cell
         for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
            // 當(dāng)前 cell 的 top hash 值
            top := b.tophash[i]
            // 如果 cell 為空,即沒有 key
            if isEmpty(top) {
               // 那就標(biāo)志它被"搬遷"過,繼續(xù)下一個cell
               b.tophash[i] = evacuatedEmpty
               continue
            }

            // 正常不會出現(xiàn)這種情況
            // 未被搬遷的 cell 只可能是 empty 或是正常的 top hash(大于 minTopHash)
            if top < minTopHash {
               throw("bad map state")
            }
            k2 := k
            if t.indirectkey() {
               k2 = *((*unsafe.Pointer)(k2))
            }

            var useY uint8
            if !h.sameSizeGrow() {
               // Compute hash to make our evacuation decision (whether we need
               // to send this key/elem to bucket x or bucket y).
               // 計算哈希,以判斷我們的數(shù)據(jù)要轉(zhuǎn)移到哪一部分的 bucket,
               // 可能是 x 部分,也可能是 y 部分
               hash := t.hasher(k2, uintptr(h.hash0))
               if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
                  // If key != key (NaNs), then the hash could be (and probably
                  // will be) entirely different from the old hash. Moreover,
                  // it isn't reproducible. Reproducibility is required in the
                  // presence of iterators, as our evacuation decision must
                  // match whatever decision the iterator made.
                  // Fortunately, we have the freedom to send these keys either
                  // way. Also, tophash is meaningless for these kinds of keys.
                  // We let the low bit of tophash drive the evacuation decision.
                  // We recompute a new random tophash for the next level so
                  // these keys will get evenly distributed across all buckets
                  // after multiple grows.
                  useY = top & 1
                  top = tophash(hash)
               } else {
                  // 根據(jù)hash & newbit 來確定新bucket的索引,確保遷移完成之后,
                  // 使用原先的hash值 & 新的mask 還能找到正確的索引
                  if hash&newbit != 0 {
                     useY = 1
                  }
               }
            }

            if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
               throw("bad evacuatedN")
            }

            // 在oldbucket對應(yīng)的cell中標(biāo)記top的搬遷狀態(tài)
            b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
            dst := &xy[useY]                 // evacuation destination

            // 當(dāng)前bucket中已經(jīng)放滿了元素,需要使用overflow bucket
            if dst.i == bucketCnt {
               dst.b = h.newoverflow(t, dst.b)
               dst.i = 0
               dst.k = add(unsafe.Pointer(dst.b), dataOffset)
               dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
            }
            dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
            if t.indirectkey() {
               *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
            } else {
               typedmemmove(t.key, dst.k, k) // copy elem
            }
            if t.indirectelem() {
               *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
            } else {
               typedmemmove(t.elem, dst.e, e)
            }
            dst.i++
            // These updates might push these pointers past the end of the
            // key or elem arrays.  That's ok, as we have the overflow pointer
            // at the end of the bucket to protect against pointing past the
            // end of the bucket.
            dst.k = add(dst.k, uintptr(t.keysize))
            dst.e = add(dst.e, uintptr(t.elemsize))
         }
      }
      // Unlink the overflow buckets & clear key/elem to help GC.
      // 如果沒有協(xié)程在使用老的 buckets,就把老 buckets 清除掉,幫助gc
      if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
         b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
         // Preserve b.tophash because the evacuation state is maintained there.
         // 只清除bucket 的 key,value 部分,保留 top hash 部分,指示搬遷狀態(tài)
         ptr := add(b, dataOffset)
         n := uintptr(t.bucketsize) - dataOffset
         memclrHasPointers(ptr, n)
      }
   }

   // 更新搬遷進度,如果此次搬遷的 bucket 等于當(dāng)前進度
   if oldbucket == h.nevacuate {
      advanceEvacuationMark(h, t, newbit)
   }
}

3.5 map的刪除

map的刪除主要流程就是需要在key所在的索引bmap鏈表中查找到對應(yīng)的值,進行內(nèi)容的刪除釋放。這里需要特別注意的是,為了提升查找效率,有一個emptyRest前向傳播機制:如果被刪除的key后續(xù)位置都是emptyRest,則需要將其前面標(biāo)記為emptyOne的cell升級為emptyRest,表示從這個cell往后不再有數(shù)據(jù)。

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {

   if raceenabled && h != nil  {
      callerpc := getcallerpc()
      pc := funcPC(mapdelete)
      racewritepc(unsafe.Pointer(h), callerpc, pc)
      raceReadObjectPC(t.key, key, callerpc, pc)
   }
   if msanenabled && h != nil{
      msanread(key, t.key.size)
   }

   // 如果map為空,或者元素個數(shù)為零,直接返回
   if h == nil || h.count == 0 {
      if t.hashMightPanic() {
         t.hasher(key, 0)
      }
      return
   }

   // 有g(shù)oroutine在寫map時,無法完成刪除操作
   if h.flags&hashWriting != 0 {
      throw("concurrent map writes")
   }
   // 計算需要寫入的key的hash值
   hash := t.hasher(key, uintptr(h.hash0))

   // 調(diào)用hasher函數(shù)時,可能發(fā)生paninc,因此沒法完成一次寫操作
   // 如果hasher沒有發(fā)生panic,那么將flags設(shè)置成flags += 4
   h.flags ^= hashWriting

   //  計算低 8 位 hash,根據(jù)計算出的 bucketMask 選擇對應(yīng)的 bucket 編號
   bucket := hash & bucketMask(h.B)
   //  如果map正在擴容,則完成搬遷工作
   if h.growing() {
      growWork(t, h, bucket)
   }
   // 計算key對應(yīng)桶編號的地址,以及hash值的高8位
   b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   bOrig := b
   top := tophash(hash)
search:
   // 兩層循環(huán),第一層遍歷bucket后面所有的溢出桶
   //         第二層遍歷每個桶內(nèi)部的8個key位置               
   for ; b != nil; b = b.overflow(t) {
      for i := uintptr(0); i < bucketCnt; i++ {
         // 如果top不匹配
         if b.tophash[i] != top {
            // emptyRest標(biāo)記此cell后面所有的key(包括overflow桶)都為空,此時直接跳出循環(huán)
            if b.tophash[i] == emptyRest {
               break search
            }
            continue
         }

         // 如果b.tophash[i] == top,計算key對應(yīng)的地址
         // k是指針對象,解引用
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         // 為了保存key的原始類型,便于后續(xù)的清理
         k2 := k
         if t.indirectkey() {
            k2 = *((*unsafe.Pointer)(k2))
         }

         // 如果相同的 hash 位置的 key 和要插入的 key 字面上不相等
         // 如果兩個 key 的首八位后最后八位哈希值一樣,就會進行其值比較,算是一種哈希碰撞
         if !t.key.equal(key, k2) {
            continue
         }

         // Only clear key if there are pointers in it.
         if t.indirectkey() {
            *(*unsafe.Pointer)(k) = nil
         } else if t.key.ptrdata != 0 {
            memclrHasPointers(k, t.key.size)
         }
         e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
         if t.indirectelem() {
            *(*unsafe.Pointer)(e) = nil
         } else if t.elem.ptrdata  != 0 {
            memclrHasPointers(e, t.elem.size)
         } else {
            memclrNoHeapPointers(e, t.elem.size)
         }

         // 標(biāo)記tophash的狀態(tài)
         b.tophash[i] = emptyOne
         // If the bucket now ends in a bunch of emptyOne states, change those to emptyRest states.
         // It would be nice to make this a separate function, but for loops are not currently inlineable.
         if i == bucketCnt-1 { // 刪除的key位于bucket的尾巴
            // 如果后續(xù)還有overflow桶,且桶內(nèi)部還有元素,那么直接跳到notLast
            // 將此tophash標(biāo)記為emptyOne即可
            if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
               goto notLast
            }
         } else {
            // 如果key不是最后一個,且后續(xù)cell還有元素,也直接跳到notLast
            if b.tophash[i+1] != emptyRest {
               goto notLast
            }
         }
         for {
            // 刪除的key后面不再有元素,需要將tophash標(biāo)記為emptyRest
            // 同時往前尋找,并將前面tophash為emptyOne的位置標(biāo)記為emptyRest
            b.tophash[i] = emptyRest
            if i == 0 {
               if b == bOrig {
                  break // beginning of initial bucket, we're done.
               }
               // Find previous bucket, continue at its last entry.
               c := b
               // 從key的bucket開始,查找當(dāng)前bucket的前一個桶地址
               for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
               }
               // bucket內(nèi)部從最后一個cell開始查找tophash為emptyOne的cell
               i = bucketCnt - 1
            } else {
               i--
            }
            // 查找到一個有內(nèi)容的tophash,結(jié)束循環(huán)
            if b.tophash[i] != emptyOne {
               break
            }
         }
      notLast:
         h.count--
         // Reset the hash seed to make it more difficult for attackers to
         // repeatedly trigger hash collisions. See issue 25237.
         if h.count == 0 {
            h.hash0 = fastrand()
         }
         break search
      }
   }

   // 禁止并發(fā)寫
   if h.flags&hashWriting == 0 {
      throw("concurrent map writes")
   }
   // flags對hashWriting按位置0,
   // '^='表示按右邊hashWriting二進制為1的位置,置0,其他位置與flags保持一致
   // 還原寫操作之前的flags
   h.flags &^= hashWriting
}

3.6 map的遍歷

3.6.1 hiter結(jié)構(gòu)體

在對map進行遍歷時,會借助迭代器hiter輔助完成整個map的循環(huán)遍歷,其中startBucket標(biāo)記此次遍歷的起始位置,wrapped標(biāo)記遍歷是否從頭開始,checkBucket則是用于擴容中進行遍歷時,堅持oldBucket中的數(shù)據(jù)。

type hiter struct {
        // key 指針,保存此次遍歷得到的key
        key         unsafe.Pointer
        // value 指針,保存此次遍歷得到的value
        value       unsafe.Pointer
        // map 類型,包含如 key size 大小等
        t           *maptype
        // map header
        h           *hmap
        // 初始化時指向的 bucket
        buckets     unsafe.Pointer
        // 當(dāng)前遍歷到的 bmap
        bptr        *bmap
        overflow    [2]*[]*bmap
        // 起始遍歷的 bucet 編號
        startBucket uintptr
        // 遍歷開始時 cell 的編號(每個 bucket 中有 8 個 cell)
        offset      uint8
        // 是否從頭遍歷了
        wrapped     bool
        // B 的大小
        B           uint8
        // 指示當(dāng)前 cell 序號
        i           uint8
        // 指向當(dāng)前的 bucket
        bucket      uintptr
        // 因為擴容,需要檢查的 bucket
        checkBucket uintptr
}

3.6.2 mapiternext函數(shù)

對map進行遍歷時,首先會調(diào)用mapiterinit函數(shù),初始化hiter,該函數(shù)邏輯比較簡單,主要就是隨機確定遍歷起始位置,這里的起始位置包括:bmap的數(shù)組的起始下標(biāo)、bmap bucket內(nèi)部cell的起始點。隨后調(diào)用mapiternext函數(shù)開始執(zhí)行具體的遍歷操作(每調(diào)用一次mapiternext函數(shù)獲取一個map中的鍵值對),該過程的主要流程如下:

1. 首先檢查是否有并發(fā)寫操作,如果有則拋出異常。

2. 獲取迭代器當(dāng)前的狀態(tài)(當(dāng)前遍歷的bucket,當(dāng)前bucket內(nèi)的位置i,當(dāng)前bucket指針b等)。

3. 如果當(dāng)前bucket(b)為nil,說明需要處理下一個bucket或者已經(jīng)遍歷完一圈。

  • 如果當(dāng)前bucket序號(bucket)等于起始bucket(it.startBucket)且已經(jīng)標(biāo)記為繞回(wrapped),說明已經(jīng)遍歷完所有bucket,設(shè)置key和elem為nil并返回。
  • 如果map正在擴容且迭代器開始時的B(it.B)等于當(dāng)前map的B(h.B),說明迭代開始后擴容未完成,需要處理舊桶:
  • 計算對應(yīng)的舊桶(oldbucket)地址。
  • 如果該舊桶尚未遷移(evacuated),則設(shè)置checkBucket為當(dāng)前bucket(用于后續(xù)判斷鍵是否屬于當(dāng)前新桶),并繼續(xù)遍歷舊桶。
  • 如果已經(jīng)遷移,則直接遍歷新桶中對應(yīng)位置的桶,并將checkBucket設(shè)置為noCheck。
  • 否則,直接遍歷新桶中當(dāng)前bucket位置的桶。
  • 然后bucket序號加1,如果達到bucket總數(shù)(2^B),則重置為0并標(biāo)記wrapped為true(表示已經(jīng)繞回一圈)。
  • 重置i為0,開始遍歷新桶。

4. 遍歷當(dāng)前bucket(b)的8個cell(槽位),注意這里不是從0開始,而是根據(jù)it.offset進行偏移(使用offi = (i+it.offset) & (bucketCnt-1))以實現(xiàn)隨機開始。

  • 如果tophash[offi]為空(emptyOne或evacuatedEmpty)則跳過。
  • 獲取鍵k和值e的地址。
  • 如果checkBucket不為noCheck(說明在擴容過程中且當(dāng)前遍歷的是舊桶),則需要判斷該鍵是否屬于當(dāng)前迭代的新桶(checkBucket):
  • 對于正常鍵(非NaN),計算其哈希值并判斷它是否屬于checkBucket,如果不屬于則跳過。
  • 對于NaN(k!=k),使用tophash的低位來決定它應(yīng)該去哪個桶,如果與checkBucket的高位不匹配則跳過。
  • 如果鍵值有效,則判斷該槽位是否已經(jīng)被遷移(evacuatedX或evacuatedY)且鍵是正常的(可比較且相等):
  • 如果未被遷移,或者鍵是NaN(不可比較),則直接使用當(dāng)前找到的鍵值對(因為此時數(shù)據(jù)還未遷移或無法比較,所以認(rèn)為有效)。
  • 否則,說明在迭代過程中map已經(jīng)擴容完成,該鍵可能已經(jīng)被遷移,需要從新map中查找(調(diào)用mapaccessK):如果返回的鍵為nil,說明該鍵已被刪除,跳過;否則使用返回的鍵值對。

5. 設(shè)置迭代器的狀態(tài)(key, elem, bucket, bptr, i, checkBucket)并返回。

6. 如果當(dāng)前bucket的8個cell都遍歷完了,則跳到overflow bucket(如果有),重置i為0,然后跳轉(zhuǎn)到next標(biāo)簽繼續(xù)處理。

func mapiternext(it *hiter) {
   h := it.h
   if raceenabled {
      callerpc := getcallerpc()
      racewritepc(unsafe.Pointer(h), callerpc, funcPC(mapiternext))
   }

   // 如果有g(shù)oroutine正在寫,拋出異常
   if h.flags&hashWriting != 0 {
      throw("concurrent map iteration and writes")
   }

   t := it.t
   bucket := it.bucket
   b := it.bptr
   i := it.i
   checkBucket := it.checkBucket

next:
   // 后續(xù)沒有overflow bucket需要遍歷
   if b == nil {
      // 當(dāng)前遍歷的bucket=startBucket,即完成循環(huán)回到最初的位置
      // 且該bucket已經(jīng)從頭到尾遍歷完了,map的遍歷結(jié)束
      if bucket == it.startBucket && it.wrapped {
         // end of iteration
         it.key = nil
         it.elem = nil
         return
      }

      // 如果map正處于擴容狀態(tài),還需要遍歷oldbucket
      if h.growing() && it.B == h.B {
         // Iterator was started in the middle of a grow, and the grow isn't done yet.
         // If the bucket we're looking at hasn't been filled in yet (i.e. the old
         // bucket hasn't been evacuated) then we need to iterate through the old
         // bucket and only return the ones that will be migrated to this bucket.
         oldbucket := bucket & it.h.oldbucketmask()
         // 根據(jù)bucket num在oldbucket的編號位置,計算bucket的地址
         b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
         if !evacuated(b) {
            // 如果oldbucket中此編號的bucket沒有完成搬遷,那么標(biāo)記check
            checkBucket = bucket
         } else {
            // 如果oldbucket中此編號的bucket完成了搬遷,直接遍歷newbucket中對應(yīng)位置的bucket
            b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
            checkBucket = noCheck
         }
      } else {
         b = (*bmap)(add(it.buckets, bucket*uintptr(t.bucketsize)))
         checkBucket = noCheck
      }
      // 指向下一個bucket
      bucket++
      // 判斷是否已經(jīng)遍歷到了末尾,如果是,則需要從頭重新開始遍歷,
      // 直至bucket == startbucket,標(biāo)記一次完整的遍歷
      if bucket == bucketShift(it.B) {
         bucket = 0
         it.wrapped = true
      }
      i = 0
   }

   // 遍歷bucket的8個cell,但不是從頭開始遍歷的
   for ; i < bucketCnt; i++ {
      offi := (i + it.offset) & (bucketCnt - 1)
      // 如果tophash為空,即沒有數(shù)據(jù),直接檢查下一個
      if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
         // TODO: emptyRest is hard to use here, as we start iterating
         // in the middle of a bucket. It's feasible, just tricky.
         continue
      }
      k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
      if t.indirectkey() {
         k = *((*unsafe.Pointer)(k))
      }

      e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
      if checkBucket != noCheck && !h.sameSizeGrow() {
         // Special case: iterator was started during a grow to a larger size
         // and the grow is not done yet. We're working on a bucket whose
         // oldbucket has not been evacuated yet. Or at least, it wasn't
         // evacuated when we started the bucket. So we're iterating
         // through the oldbucket, skipping any keys that will go
         // to the other new bucket (each oldbucket expands to two buckets during a grow).
         if t.reflexivekey() || t.key.equal(k, k) {
            // If the item in the oldbucket is not destined for the current new bucket in the iteration, skip it.
            hash := t.hasher(k, uintptr(h.hash0))
            if hash&bucketMask(it.B) != checkBucket {
               continue
            }
         } else {
            // Hash isn't repeatable if k != k (NaNs).  We need a
            // repeatable and randomish choice of which direction
            // to send NaNs during evacuation. We'll use the low
            // bit of tophash to decide which way NaNs go.
            // NOTE: this case is why we need two evacuate tophash
            // values, evacuatedX and evacuatedY, that differ in their low bit.
            if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
               continue
            }
         }
      }
      if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
         !(t.reflexivekey() || t.key.equal(k, k)) {
         // This is the golden data, we can return it.
         // OR
         // key!=key, so the entry can't be deleted or updated, so we can just return it.
         // That's lucky for us because when key!=key we can't look it up successfully.
         it.key = k
         if t.indirectelem() {
            e = *((*unsafe.Pointer)(e))
         }
         it.elem = e
      } else {
         // The hash table has grown since the iterator was started.
         // The golden data for this key is now somewhere else.
         // Check the current hash table for the data.
         // This code handles the case where the key has been deleted, updated, or deleted and reinserted.
         // NOTE: we need to regrab the key as it has potentially been
         // updated to an equal() but not identical key (e.g. +0.0 vs -0.0).
         rk, re := mapaccessK(t, h, k)
         if rk == nil {
            continue // key has been deleted
         }
         it.key = rk
         it.elem = re
      }
      it.bucket = bucket
      if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
         it.bptr = b
      }
      it.i = i + 1
      it.checkBucket = checkBucket
      return
   }

   // 通過it.i走到此處,遍歷overflow bucket
   b = b.overflow(t)
   i = 0
   goto next
}

總結(jié)

以上為個人經(jīng)驗,希望能給大家一個參考,也希望大家多多支持腳本之家。

相關(guān)文章

  • Go語言什么時候該使用指針

    Go語言什么時候該使用指針

    本文主要介紹了Go語言什么情況下應(yīng)該使用指針,文中通過示例代碼介紹的非常詳細,具有一定的參考價值,感興趣的小伙伴們可以參考一下
    2022-01-01
  • Golang工具庫viper的使用教程

    Golang工具庫viper的使用教程

    viper?是?go?項目中用來讀取配置文件的庫,支持讀取?yaml、toml、json、hcl、env?等格式的配置文件,下面就來和大家聊聊它的具體使用吧
    2023-07-07
  • golang特有程序結(jié)構(gòu)入門教程

    golang特有程序結(jié)構(gòu)入門教程

    GO語言是一門不錯的編程語言能夠到達靜態(tài)編譯語言的安全和性能,在本文中重點給大家介紹goland特有程序結(jié)構(gòu)及引用類型別名的特征,感興趣的朋友跟隨小編一起看看吧
    2021-06-06
  • OpenTelemetry-go的SDK使用方法詳解

    OpenTelemetry-go的SDK使用方法詳解

    這篇文章主要介紹了OpenTelemetry-go的SDK使用方法,OpenTelemetry幫我們實現(xiàn)了相應(yīng)語言的SDK,所以我們只需要進行調(diào)用即可,本文根據(jù)官方文檔實例講解,需要的朋友可以參考下
    2022-09-09
  • Go?time包AddDate使用解惑實例詳解

    Go?time包AddDate使用解惑實例詳解

    這篇文章主要為大家介紹了Go?time包AddDate使用解惑實例詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2022-09-09
  • golang包循環(huán)引用的幾種解決方案總結(jié)

    golang包循環(huán)引用的幾種解決方案總結(jié)

    golang有包循環(huán)引用問題,用過的應(yīng)該都知道,下面這篇文章主要給大家介紹了關(guān)于golang包循環(huán)引用的幾種解決方案,文中通過實例代碼介紹的非常詳細,需要的朋友可以參考下
    2022-09-09
  • Go類型斷言提取測試接口值動態(tài)類型及靜態(tài)轉(zhuǎn)換確保類型接口編譯安全

    Go類型斷言提取測試接口值動態(tài)類型及靜態(tài)轉(zhuǎn)換確保類型接口編譯安全

    這篇文章主要為大家介紹了Go類型斷言提取測試接口值動態(tài)類型及靜態(tài)轉(zhuǎn)換確保類型實現(xiàn)特定接口的編譯時安全性詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進步,早日升職加薪
    2023-10-10
  • 在Golang中實現(xiàn)RSA算法的加解密操作詳解

    在Golang中實現(xiàn)RSA算法的加解密操作詳解

    RSA 是一種非對稱加密算法,廣泛使用于數(shù)據(jù)的安全傳輸,crypto/rsa 是 Golang 中實現(xiàn)了 RSA 算法的一個標(biāo)準(zhǔn)庫,提供了生成公私鑰對、加解密數(shù)據(jù)、簽名和驗簽等功能,本文給大家介紹了在Golang中實現(xiàn)RSA算法的加解密操作,需要的朋友可以參考下
    2023-12-12
  • GoLang中Json?Tag用法實例總結(jié)

    GoLang中Json?Tag用法實例總結(jié)

    這篇文章主要給大家介紹了關(guān)于GoLang中Json?Tag用法的相關(guān)資料,文中通過實例代碼介紹的非常詳細,對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下
    2022-02-02
  • C語言的10大基礎(chǔ)算法

    C語言的10大基礎(chǔ)算法

    算法是一個程序和軟件的靈魂,作為一名優(yōu)秀的程序員,只有對一些基礎(chǔ)的算法有著全面的掌握,才會在設(shè)計程序和編寫代碼的過程中顯得得心應(yīng)手。這篇文章主要介紹了C語言的10大基礎(chǔ)算法,需要的朋友可以參考下
    2019-09-09

最新評論