// 聲明一個(gè)map變量，鍵是string類型，值是int類型
// 但此時(shí)m還是一個(gè)nil map，無法對(duì)其進(jìn)行寫入
var m map[string]int 
m["1"] = 1 // 報(bào)錯(cuò)，nil map無法寫入

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


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

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

m := make(map[string]int)
m["1"] = 1

type Person struct {
	name string
	age  int
}

m1 := map[string]Person{}
m1["Tom"].age++ // 錯(cuò)誤，因?yàn)閙ap的值是無法尋址的，這種情況需要接受舊值，將修改完后的值重新賦值

m2 := map[string]*Person{}
m2["Tom"].age++ // 正確，這種情況下沒有改變map中的value，而是通過指針找到對(duì)應(yīng)存儲(chǔ)的值進(jìn)行修改

var m map[string]int
fmt.Println(m["1"]) // nil map可以進(jìn)行查找，返回的是value的默認(rèn)零值

// 如果需要判斷key是否存在于map中，則可以使用如下寫法
if _, ok := m["1"]; ok {
    fmt.Println("key存在")
} else {
    fmt.Println("key不存在")
}

var m map[string]int
delete(m ,"1")

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

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

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

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

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
}

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


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

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

func makemap_small() *hmap {
   h := new(hmap)
   h.hash0 = fastrand()
   return h
}

func makemap(t *maptype, hint int, h *hmap) *hmap {
   // 進(jìn)行內(nèi)存大小的檢查，如果溢出或者內(nèi)存超出最大內(nèi)存空間，將hint（元素個(gè)數(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的哈希計(jì)算種子隨機(jī)數(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.
   // 按照提供的元素個(gè)數(shù)，根據(jù)負(fù)載因子計(jì)算合理的 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 就會(huì)在賦值（ mapassign ）的時(shí)候再分配
   // 如果長度比較大，分配內(nèi)存會(huì)花費(fèi)長一點(diǎn)
   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í)，由于數(shù)據(jù)較少、使用溢出桶的可能性較低，
   // 這時(shí)就會(huì)省略創(chuàng)建溢出桶的過程以減少額外開銷
   if b >= 4 {
      // 當(dāng)桶的數(shù)量多于2^4時(shí)，就會(huì)額外創(chuàng)建 2^(b-4)個(gè)溢出桶
      // 根據(jù)內(nèi)存的分配規(guī)則，計(jì)算出合適的內(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)存，就初始化一個(gè)數(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個(gè)桶后面就是溢出桶
      nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))

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

/*
 t *maptype：map 的類型信息
 h *hmap：map 的底層結(jié)構(gòu)
 key unsafe.Pointer：要插入或更新的鍵
 返回：指向值存儲(chǔ)位置的指針（寫入值需通過此指針）
*/
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   // 對(duì)于nil的map不能進(jìn)行寫操作，直接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")
   }
   // 計(jì)算需要寫入的key的hash值
   hash := t.hasher(key, uintptr(h.hash0))

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

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

again:
   //  計(jì)算低 8 位 hash，根據(jù)計(jì)算出的 bucketMask 選擇對(duì)應(yīng)的 bucket 編號(hào)
   bucket := hash & bucketMask(h.B)
   //  如果map正在擴(kuò)容，則完成搬遷工作
   if h.growing() {
      growWork(t, h, bucket)
   }
   // 計(jì)算key對(duì)應(yīng)桶編號(hào)的地址，以及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的對(duì)象指針（地址）
   var elem unsafe.Pointer       //  寫入value的對(duì)象指針（地址），即返回值
bucketloop:
   //  開啟雙層循環(huán)，外層遍歷bucket的所有overflow桶，內(nèi)層遍歷每個(gè)bucket的cell
   //  目的：找到空的cell（key不存在），或者top所在的位置（key已存在）
   for {
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top { // 當(dāng)前top不一致，繼續(xù)比對(duì)下一個(gè)
            // 找到第一個(gè)空的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，計(jì)算key對(duì)應(yīng)的地址
         // k是指針對(duì)象，解引用
         k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
         if t.indirectkey() {
            k = *((*unsafe.Pointer)(k))
         }

         // 如果相同的 hash 位置的 key 和要插入的 key 字面上不相等
         // 如果兩個(gè) key 的首八位后最后八位哈希值一樣，就會(huì)進(jìn)行其值比較，算是一種哈希碰撞吧
         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 個(gè)槽沒有滿足條件的能插入或者能更新的，去 overflow 里繼續(xù)找
      //  overflow 為 nil，說明到了 overflow 鏈表的末端了，退出外層循環(huán)
      ovf := b.overflow(t)
      if ovf == nil {
         break
      }
      // 賦值為鏈表的下一個(gè)元素，繼續(xù)循環(huán)
      b = ovf
   }

   // 沒有找到 key，分配新的空間
   // 如果觸發(fā)了最大的 load factor，或者已經(jīng)有太多 overflow buckets
   // 并且這個(gè)時(shí)刻沒有在進(jìn)行 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.
      // 前面在桶里找的時(shí)候，沒有找到能塞這個(gè) tophash 的位置
      // 說明當(dāng)前所有 buckets 都是滿的，分配一個(gè)新的 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() { // 如果鍵的比較大，則直接使用指針存儲(chǔ)
      kmem := newobject(t.key)
      // 二級(jí)指針，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對(duì)hashWriting按位置0，'^='表示按右邊hashWriting二進(jìn)制為1的位置，置0
   // 還原寫操作之前的flags
   h.flags &^= hashWriting
   if t.indirectelem() {
      // 如果value是個(gè)大對(duì)象，則bucket中存儲(chǔ)的是對(duì)象地址unsafe.Pointer，取出存放value對(duì)象的地址
      elem = *((*unsafe.Pointer)(elem))
   }
   return elem
}

/*
    t *maptype：map 的類型信息
    h *hmap：map 的底層結(jié)構(gòu)
    key unsafe.Pointer：要查找的鍵
    返回值：
        unsafe.Pointer：指向值的指針（未找到時(shí)指向零值）
        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為空，或者元素個(gè)數(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")
   }

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

   // h.oldbuckets ！= nil時(shí)，說明 map 發(fā)生了擴(kuò)容。這時(shí)候，新的 buckets 里可能還沒有老的內(nèi)容，
   // 所以一定要在老的里面找，否則有可能發(fā)生“消失”的詭異現(xiàn)象
   if c := h.oldbuckets; c != nil {
      if !h.sameSizeGrow() {
         // 如果不是等量擴(kuò)容，新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
      }
   }
   // 計(jì)算高 8 位的 hash，相當(dāng)于右移 56 位，只取高8位
   top := tophash(hash)
bucketloop:
   // 兩層循環(huán)，第一層遍歷bucket后面所有的溢出桶
   //         第二層遍歷每個(gè)桶內(nèi)部的8個(gè)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桶）都為空，此時(shí)直接跳出循環(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類型，然后取出該地址存儲(chǔ)的值
         }
         // 如果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
}

// 裝載因子超過 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)
}

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 超過了閾值，那么需要對(duì) map 進(jìn)行擴(kuò)容，即 B = B + 1，bucket 總數(shù)會(huì)變?yōu)樵瓉淼亩?
   // 如果還沒到閾值，那么只需要保持相同數(shù)量的 bucket，橫向拍平就行了（等量擴(kuò)容）
   bigger := uint8(1)
   if !overLoadFactor(h.count+1, h.B) {
      bigger = 0
      h.flags |= sameSizeGrow // 如果flags原先的值小于sameSizeGrow，h.flags += sameSizeGrow
   }

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

   // 先把 h.flags 中 iterator 和 oldIterator 對(duì)應(yīng)位清 0，然后如果發(fā)現(xiàn) iterator 位為 1，那就把它轉(zhuǎn)接到 oldIterator 位，使得 oldIterator 標(biāo)志位變成 1。
   // 潛臺(tái)詞就是：buckets 現(xiàn)在掛到了 oldBuckets 名下了，對(duì)應(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().
   // 實(shí)際的哈希表元素的拷貝工作是在 growWork 和 evacuate 中增量慢慢地進(jìn)行的
}

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

newMask = (1 << (B+1)) - 1 = (1 << B) * 2 - 1 = newbit*2 - 1

// 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ù)用于實(shí)現(xiàn)hmap擴(kuò)容時(shí)，數(shù)據(jù)的搬遷工作
// 如果是等量擴(kuò)容，那么就初始化一個(gè)evacDst
// 如果是翻倍擴(kuò)容，那么就初始化兩個(gè)evacDst
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
   // 定位舊bucket的地址以及擴(kuò)容前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 包含的是移動(dòng)的目標(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 擴(kuò)容，前后 bucket 序號(hào)有變，使用 y 來進(jìn)行搬遷
         // 擴(kuò)容后的map bucket數(shù)量是原先的兩倍，x，y分別各占一半，數(shù)量與擴(kuò)容前一樣
         // y部分桶的編號(hào)： 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的第一個(gè)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ù)下一個(gè)cell
               b.tophash[i] = evacuatedEmpty
               continue
            }

            // 正常不會(huì)出現(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).
               // 計(jì)算哈希，以判斷我們的數(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對(duì)應(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)
      }
   }

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

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為空，或者元素個(gè)數(shù)為零，直接返回
   if h == nil || h.count == 0 {
      if t.hashMightPanic() {
         t.hasher(key, 0)
      }
      return
   }

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

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

   //  計(jì)算低 8 位 hash，根據(jù)計(jì)算出的 bucketMask 選擇對(duì)應(yīng)的 bucket 編號(hào)
   bucket := hash & bucketMask(h.B)
   //  如果map正在擴(kuò)容，則完成搬遷工作
   if h.growing() {
      growWork(t, h, bucket)
   }
   // 計(jì)算key對(duì)應(yīng)桶編號(hào)的地址，以及hash值的高8位
   b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   bOrig := b
   top := tophash(hash)
search:
   // 兩層循環(huán)，第一層遍歷bucket后面所有的溢出桶
   //         第二層遍歷每個(gè)桶內(nèi)部的8個(gè)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桶）都為空，此時(shí)直接跳出循環(huán)
            if b.tophash[i] == emptyRest {
               break search
            }
            continue
         }

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

         // 如果相同的 hash 位置的 key 和要插入的 key 字面上不相等
         // 如果兩個(gè) key 的首八位后最后八位哈希值一樣，就會(huì)進(jìn)行其值比較，算是一種哈希碰撞
         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不是最后一個(gè)，且后續(xù)cell還有元素，也直接跳到notLast
            if b.tophash[i+1] != emptyRest {
               goto notLast
            }
         }
         for {
            // 刪除的key后面不再有元素，需要將tophash標(biāo)記為emptyRest
            // 同時(shí)往前尋找，并將前面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的前一個(gè)桶地址
               for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
               }
               // bucket內(nèi)部從最后一個(gè)cell開始查找tophash為emptyOne的cell
               i = bucketCnt - 1
            } else {
               i--
            }
            // 查找到一個(gè)有內(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對(duì)hashWriting按位置0，
   // '^='表示按右邊hashWriting二進(jìn)制為1的位置，置0，其他位置與flags保持一致
   // 還原寫操作之前的flags
   h.flags &^= hashWriting
}

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

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正處于擴(kuò)容狀態(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的編號(hào)位置，計(jì)算bucket的地址
         b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
         if !evacuated(b) {
            // 如果oldbucket中此編號(hào)的bucket沒有完成搬遷，那么標(biāo)記check
            checkBucket = bucket
         } else {
            // 如果oldbucket中此編號(hào)的bucket完成了搬遷，直接遍歷newbucket中對(duì)應(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
      }
      // 指向下一個(gè)bucket
      bucket++
      // 判斷是否已經(jīng)遍歷到了末尾，如果是，則需要從頭重新開始遍歷，
      // 直至bucket == startbucket，標(biāo)記一次完整的遍歷
      if bucket == bucketShift(it.B) {
         bucket = 0
         it.wrapped = true
      }
      i = 0
   }

   // 遍歷bucket的8個(gè)cell，但不是從頭開始遍歷的
   for ; i < bucketCnt; i++ {
      offi := (i + it.offset) & (bucketCnt - 1)
      // 如果tophash為空，即沒有數(shù)據(jù)，直接檢查下一個(gè)
      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
}