go map 设计与实现

// go map 数据结构
type hmap struct {
  count     int            // map 的元素数量。调用 len(map) 的时候返回此值
  flags     uint8          // map 标记：iterator/oldIterator/hashWriting/sameSizeGrow
  B         uint8          // 指示了当前哈希表持有的 buckets 的数量（2^B 是 bucket 的数量）
  noverflow uint16         // 溢出桶的数量
  hash0     uint32         // 哈希种子，计算 key 的哈希的时候会传入哈希函数
  buckets   unsafe.Pointer // 指向 buckets 的数组，大小为 2^B。 如果元素个数为 0 则为 nil。
  // 哈希表扩容的时候记录 buckets 字段。
  // 增量扩容时，oldbuckets 的长度是 buckets 的一半。
  oldbuckets unsafe.Pointer
  nevacuate uintptr   // 指示扩容进度，小于此地址的 buckets 完成迁移
  extra     *mapextra // 可选字段
}
// mapextra 包含并非在所有 map 上都存在的字段。
// 下面 mapextra 注释是原文的翻译（看完了 map 的全部源码也还不是很懂这个结构体的作用，除了 nextOverflow 字段）。
type mapextra struct {
  // 如果 key 和 elem 都不包含指针并且是内联的，那么我们将 bucket type 标记为不包含指针。这避免了扫描此类 map。
  // 但是，bmap.overflow 是一个指针。 为了让溢出桶保持活动状态，
  // 我们将指向所有溢出桶的指针存储在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中。
  // overflow 和 oldoverflow 仅在 key 和 elem 不包含指针时使用。
  // overflow 包含 hmap.buckets 的溢出桶。
  // oldoverflow 包含 hmap.oldbuckets 的溢出桶。
  // 间接允许在 hiter 中存储指向切片的指针。
  overflow    *[]*bmap
  oldoverflow *[]*bmap
  // nextOverflow 持有指向空闲溢出桶的指针。
  nextOverflow *bmap
}
// go map 中的 bucket 结构体（实际保存 key/value 的地方）
type bmap struct {
  // tophash 通常包含此 bucket 中每个键的哈希值的最高的 8 位（1 字节）。
  // 如果 tophash[0] ＜ minTopHash，则 tophash[0] 为桶已迁移状态。
  // 这是一个长度为 8 的数组，因为一个 bucket 只能存储 8 个元素。
  // tophash 存储的是每一个元素的键的哈希的高 8 位。
  //（通过比较不同键的哈希的高 8 位可以提高 bucket 内的查找性能，因为键可能很大）
  tophash [bucketCnt]uint8
  
  // 然后是 8 个键，然后是 8 个值。（这里的 8 是代码写死的）
  // 注意：将所有键放在在一起，然后将所有值放在一起使代码比交替的 key/elem/key/elem/… 复杂一些，
  // 但它允许我们消除填充（减少内存对齐导致的内存浪费），例如 map[int64]int8，
  // 这种如果使用 key/elem 的方式存储则需要浪费几个字节用来对齐。
  keys [bucketCnt]keytype // 8 个键
  values [bucketCnt]valuetype // 8 个值
  overflow *bmap // 指向溢出桶的指针
}

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))

// bucket 是否已经完成迁移
// b 是 bucket 的指针
func evacuated(b *bmap) bool {
  h := b.tophash[0]
  return h > emptyOne && h < minTopHash
}
// 获取 b 的溢出桶
func (b *bmap) overflow(t *maptype) *bmap {
  // bmap 数据结构的最后一个指针就是指向溢出桶的指针
  return *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize))
}
// 设置 b 的溢出桶
// bmap 数据结构的最后一个指针指向溢出桶
func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
  *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-goarch.PtrSize)) = ovf
}
// 获取 b 中保存 keys 的指针（指向了桶内的第一个 key）
func (b *bmap) keys() unsafe.Pointer {
  return add(unsafe.Pointer(b), dataOffset)
}

// 这个 cell 是空的，并且在更高的索引或溢出处没有更多的非空 cell。
emptyRest = 0
// 这个 cell 是空的
emptyOne = 1
// key/elem 有效。 entry 已被迁移到较大的哈希表的前半部分（扩容了）。
evacuatedX = 2
// 同上，但迁移到大的哈希表的后半部分（扩容了）。
evacuatedY = 3
// cell 是空的，bucket 已经被迁移了
evacuatedEmpty = 4
// 正常填充单元格的最小 tophash。
minTopHash = 5

// tophash 计算 hash 的 tophash 值。
// 这是一个字节的大小的。（hash 最高的 8 位）
func tophash(hash uintptr) uint8 {
  // top 本质上就是 hash 的前面 8 个字节（goarch.PtrSize*8 - 8，左移位数：指针的字节大小 - 8 字节）
  top := uint8(hash >> (goarch.PtrSize*8 - 8))
  if top < minTopHash {
    top += minTopHash
  }
  return top
}

// makemap 是 make(map[k]v, hint) 的实现，创建一个 map。
// 如果编译器可以确定 map 或者第一个 bucket 可以在栈上创建，h 和/或 bucket 可能为 non-nil。
// 如果 h != nil，map 可以直接在 h 中创建。
// 如果 h.buckets != nil，buckets 指针指向的那个元素可以作为第一个 bucket。
func makemap(t *maptype, hint int, h *hmap) *hmap {
  // 计算所需要的内存大小
  mem, overflow := math.MulUintptr(uintptr(hint), t.bucket.size)
  // 如果溢出或者超出最大分配内存，则设置 hint = 0；
  // 这样的话，B 也会等于 0；
  // 则最终的 map 只会有一个 bucket（2^B = 1）
  if overflow || mem > maxAlloc {
    hint = 0
  }
  // 初始化 hmap（分配 hmap 结构体本身所需要的内存）
  if h == nil {
    h = new(hmap)
  }
  // 生成一个随机的哈希种子
  h.hash0 = fastrand()
  // 根据传入的 hint，计算出需要的最小桶数量。
  // 实际上是计算 B 的大小，桶的数量都是运行时通过 2^B 计算的。
  B := uint8(0)
  // 如果 hint 导致超过了负载因子，则将 B 加 1，一直加到小于负载因子。
  // 简单来说就是：hint / (2^B) > 负载因子，也就是 hint 个键值对放到所有桶中，
  // 每个桶中元素数量大于负载因子（6.5）的时候，则将 B 加 1。
  // 注：map 扩容的时候也是这个判断标准。
  for overLoadFactor(hint, B) {
    B++
  }
  h.B = B
  // 分配初始哈希表。
  // 如果 B==0，则稍后（在mapassign中）延迟分配桶字段。
  // 若 hint 较大，则清零此内存可能需要一段时间。
  if h.B != 0 {
    var nextOverflow *bmap
    // 初始化 buckets（分配 buckets 所需要的内存）
    h.buckets, nextOverflow = makeBucketArray(t, h.B, nil)
    // 如果 hint 比较大，则会预先分配溢出桶，记录到 extra 字段中。
    if nextOverflow != nil {
      h.extra = new(mapextra)
      h.extra.nextOverflow = nextOverflow
    }
  }
  return h
}

// overLoadFactor 报告放置在 2^B 个桶中的键值对数量是否超过负载因子。
func overLoadFactor(count int, B uint8) bool {
  return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}

// makeBucketArray 初始化 map bucket 底层的数组（分配 buckets 的内存）。
// 1<<b 是要分配的最小存储桶数。
// dirtyalloc 应该是 nil（不为 nil，表示清空 map），或者是 makeBucketArray 之前使用相同的 t 和 b 参数分配的桶数组。
// 如果 dirtyalloc 为 nil，将分配一段新的内存；否则将清除 dirtyalloc 指向的内存，将其作为新分配的内存。
//
// 参数：
// t：底层表示 map 的类型
// b：bucket 的大小为 2^b
// dirtyalloc: 不为 nil 表示要清空，用于 mapclear 函数。
//
// 返回值：
// buckets：正常桶数组入口
// nextOverflow：溢出桶数组入口
func makeBucketArray(t *maptype, b uint8, dirtyalloc unsafe.Pointer) (buckets unsafe.Pointer, nextOverflow *bmap) {
  // bucket 数量 = 1 << b
  base := bucketShift(b)
  nbuckets := base
  // 对于小的 b，溢出桶不太可能。避免计算开销。
  // 桶的数量小于 2^4 时候，由于数据较少、使用溢出桶的可能性较低，
  // 会省略创建溢出桶的过程以减少额外开销。
  //
  // 但是大于等于 2^4 的时候，使用到溢出桶的可能性就会比较大，所以需要预先分配溢出桶。
  if b >= 4 {
    // 大于等于 2^4 的时候，额外创建 2^(B-4) 个溢出桶。
    nbuckets += bucketShift(b - 4)
    sz := t.bucket.size * nbuckets // 溢出桶所需要的内存大小
    up := roundupsize(sz)          // 计算需要的内存大小
    if up != sz {
      // 分配的内存与实际需要的内存不一样，
      // 可能会比 sz 大一点，重新计算 nbuckets。
      // 下面的 nbuckets 才是最终的 bucket 数量（普通桶 + 溢出桶的数量）
      nbuckets = up / t.bucket.size
    }
  }
  // buckets 所在的内存初始化/清空（mapclear）
  if dirtyalloc == nil {
    // 创建新的 bucket 数组
    buckets = newarray(t.bucket, int(nbuckets))
  } else {
    // 清空原有的内存
    buckets = dirtyalloc
    // buckets 所需要的总内存大小（单位：字节）
    size := t.bucket.size * nbuckets
    // 清空 buckets 开始的 size 字节大小的内存
    if t.bucket.ptrdata != 0 {
      // 有指针
      memclrHasPointers(buckets, size)
    } else {
      memclrNoHeapPointers(buckets, size)
    }
  }
  // 上面 b >= 4 的情况
  if base != nbuckets {
    // 处理一下预先分配的溢出桶。
    nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize)))  // buckets 和溢出桶内存是相邻的，计算第一个溢出桶的指针
    last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize))) // 最后一个溢出桶
    last.setoverflow(t, (*bmap)(buckets))                             // 最后一个溢出桶的 overflow 指针链接到第一个普通桶
  }
  
  // 返回普通桶、溢出桶的指针
  return buckets, nextOverflow
}

// 在迭代 map 的时候，返回键值对。
// 参数：
// t: map 类型元信息（记录了 map 中的 key/value 的类型等信息，比如 key 的大小，可用于计算内存偏移）
// h: map 结构体类型（也就是实际的哈希表类型）
// key: 需要查找的 key
// 返回值：
// 第一个返回值：当前遍历到的 key 的指针
// 第二个返回值：当前遍历到的 key 对应的值的指针
func mapaccessK(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, unsafe.Pointer) {
  // map 是空的
  if h == nil || h.count == 0 {
    return nil, nil
  }
  // 根据 key 和 hash0 计算 hash
  hash := t.hasher(key, uintptr(h.hash0))
  // hash 的掩码，类似 IP 的掩码
  //（比如，假设 B = 3，一共有 8 个元素，索引为 0～7，那么掩码 m 表示为二进制就是 111）。
  // 用于跟 hash 值做 & 运算（hash & m），得到 hash 对应 bucket 的索引（0～m）
  m := bucketMask(h.B)
  // 根据 hash 计算 bucket 地址，b 是 hash 匹配到的 bucket
  b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
  // 正在扩容，如果 bucket 还没迁移到新的地址，则需要从 oldbuckets 中访问
  if c := h.oldbuckets; c != nil {
    // 不是等量扩容，需要从旧桶中读取，所以 m 要移除最高位（右移一位）
    if !h.sameSizeGrow() {
      // 不是等量扩容，则将 m 除以 2，因为是 2 倍扩容，
      // 所以 buckets 的大小为 oldbuckets 长度的 2 倍，
      // 除以 2 才是旧的桶数量
      m >>= 1
    }
    // key 在 oldbuckets 中的地址
    oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
    if !evacuated(oldb) {
      // b 尚未迁移到新的 buckets 中，还在 oldbuckets 中
      // 则需要从旧桶中查找
      b = oldb
    }
  }
  // 计算 tophash
  top := tophash(hash)
bucketloop:
  for ; b != nil; b = b.overflow(t) {
    // 从 bucket 中查找，一个 bucket 可以存储的元素个数是 bucketCnt，也就是 8
    for i := uintptr(0); i < bucketCnt; i++ {
      // tophash 不匹配，肯定不是这个槽
      if b.tophash[i] != top {
        // bucket 剩余的槽是空的，不用再找了，跳出循环
        if b.tophash[i] == emptyRest {
          break bucketloop
        }
        // 继续比较下一个槽
        continue
      }
      // tophash 匹配
      // 接下来将这个槽的 key 取出来
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      // key 是指针类型
      if t.indirectkey() {
        k = *((*unsafe.Pointer)(k))
      }
      // 比较 key 跟 k 是否相等
      if t.key.equal(key, k) {
        // 相等则读取对应的值（表示找到了匹配的 key 了）
        e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
        // 值是指针类型
        if t.indirectelem() {
          e = *((*unsafe.Pointer)(e))
        }
        // 找到了，返回键值对
        return k, e
      }
      
      // 注意：执行到这里，说明 tophash 相等，
      // 但是 key 不匹配，仍然需要继续遍历。
    }
  }
  // 普通桶和溢出桶的所有槽都找不到，返回 nil
  return nil, nil
}

m := bucketMask(h.B)
// b 就是定位到的 bucket 所在的内存地址
b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))

// 读取 bucket 中的第 i 个 key。
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
// 读取 bucket 中的第 i 个 value
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))

if t.indirectkey() {
    k = *((*unsafe.Pointer)(k))
}
if t.indirectelem() {
    e = *((*unsafe.Pointer)(e))
}

func (mt *maptype) indirectkey() bool { // store ptr to key instead of key itself
  return mt.flags&1 != 0 // 存储了 key 的指针，而不是 key 本身
}
func (mt *maptype) indirectelem() bool { // store ptr to elem instead of elem itself
  return mt.flags&2 != 0 // 存储了 elem 的指针，而不是 elem 本身
}

k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))

// 功能：插入 key 或者修改 map 中的 key
// 参数：
// t：map 类型元信息
// h：map 结构体（实际保存键值对的地方）
// key：我们要修改或者插入的 key
// 返回值：
// 只有一个，那就是我们插入或者修改之后的值。
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  if h == nil {
    panic(plainError("assignment to entry in nil map"))
  }
  // 并发写，直接报错
  if h.flags&hashWriting != 0 {
    fatal("concurrent map writes")
  }
  // 计算 key 的哈希值（是一个无符号整数）
  hash := t.hasher(key, uintptr(h.hash0))
  // 在调用 t.hasher 之后设置 hashWriting，
  // 因为 t.hasher 可能会 panic，在这种情况下，我们实际上还没有进行写操作。
  // 写标记。（如果读操作发现有写标志则会报错）
  h.flags ^= hashWriting
  // 如果 buckets 是空，则新建一个 bucket
  if h.buckets == nil {
    h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
  }
again:
  // bucket 指示第几个 bucket（命名貌似有点不合适）
  bucket := hash & bucketMask(h.B)
  // 正在扩容的话，则将 bucket 迁移到新桶
  if h.growing() {
    growWork(t, h, bucket)
  }
  // b 为即将要写入的 bucket
  b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
  // 计算 key 的 tophash
  top := tophash(hash)
  var inserti *uint8         // 要插入的 tophash 地址
  var insertk unsafe.Pointer // 要插入的键地址
  var elem unsafe.Pointer    // 要插入的值地址
bucketloop:
  for {
    // 循环 bucket 的槽
    for i := uintptr(0); i < bucketCnt; i++ {
      if b.tophash[i] != top {
        // tophash 不匹配，并且当前槽为空，则记录要插入的位置（找不到 key 的时候，最后会插入到这里）
        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))
          // 为什么找到了可以插入的地方，不中断循环？
          // 原因是，这个函数是寻找已经存在的 key 的（插入和修改都是用这个函数），
          // 如果对应的 key 保存到了后面的槽里面的话，这里直接中断循环就是不对的。
          // 因为在这种情况下，理应更新后面的那个槽。
        }
        // bucket 没有找到对应的 key，同时 bucket 中剩余的槽都是空的。
        // （这意味着 map 中找不到 key，需要插入这个 key 了）
        // 中止对 bucket 里面槽的遍历。
        if b.tophash[i] == emptyRest {
          break bucketloop
        }
        // 虽然找到了空闲的槽，但还是要查看 bucket 中的其他槽，看 key 是否已经存在。
        // （如果存在的话，修改 key 对应的值就可以了，当然这个函数里面不会修改，而是返回值的地址，从函数外部修改）
        // 这个很好理解，保存值的指针都拿到了，想修改就很简单了。
        // 如果 key 已经存在，则返回已存在 key 的对应的 elem 的地址。
        continue
      }
      // tophash 相等，依然需要比较 key 是否相等。
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      if t.indirectkey() {
        k = *((*unsafe.Pointer)(k))
      }
      // 但是 key 不想等，继续比较下一个槽
      if !t.key.equal(key, k) {
        continue
      }
      // tophash 相等、key 也相等，说明已经存在，更新它即可
      // 用 key 更新 k
      if t.needkeyupdate() {
        typedmemmove(t.key, k, key)
      }
      // 计算 value 所在的地址
      elem = add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
      // 找到了 key，直接跳转到 done
      goto done
    }
    // 当前的桶里面所有槽都找不到。
    // 继续遍历溢出桶（在溢出桶中查找 key 是否存在/有没有空余的槽）
    ovf := b.overflow(t)
    if ovf == nil {
      // 溢出桶也找不到，跳出循环
      break
    }
    // b 指向下一个溢出桶，下次循环遍历这个溢出桶
    b = ovf
  }
  // 未找到 key，需要插入这个新的 key。
  
  // 如果我们达到了最大负载系数或者我们有太多的溢出桶，
  // 同时，如果还没有开始扩容，那么现在开始扩容。
  if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
    // 扩容哈希表会使所有内容无效，因此需要再次尝试插入。
    // （上面循环获取到的插入位置的指针已经失效了，扩容之后插入的位置改变了，所以需要再次计算要插入的 bucket，以及要插入的槽中的位置）
    goto again
  }
  // 表明没有找到可以插入的地方，则新建一个溢出桶来保存，
  // 溢出桶的第一个元素就用来保存 key，返回溢出桶第一个元素 elem 的地址
    // （这意味着，我们要插入的桶，所有的槽都有数据了，并且也不是我们要找的 key，所需要溢出桶了）
    if inserti == nil {
    // 当前存储桶及其连接的所有溢出存储桶已满，分配一个新的溢出桶。
    newb := h.newoverflow(t, b)
    // 溢出桶的第一个 tophash 的指针
    inserti = &newb.tophash[0]
    // 溢出桶的第一个 key 的指针
    insertk = add(unsafe.Pointer(newb), dataOffset)
    // 溢出桶的第一个 value 的指针
    elem = add(insertk, bucketCnt*uintptr(t.keysize))
  }
  // 在插入位置存储新 key/elem
  if t.indirectkey() {                   // 这意味着需要给 key 分配内存来保存它
    kmem := newobject(t.key)           // 给 key 分配内存（kmem 是保存 key 的内存指针）
    *(*unsafe.Pointer)(insertk) = kmem // bucket 里面的 key 保存新分配的内存指针
    insertk = kmem                     // insertk 指向新分配的地址（跟上一行并不重复）
    // 最终效果是，insertk 和 kmem 指向了新分配的保存 key 的内存地址。
    // 当然，insertk = kmem 不需要也可以，但这样一来下面也要改成：
    // if t.indirectkey() {
    //     typedmemmove(t.key, kmem, key)
    // } else {
    //     typedmemmove(t.key, insertk, key)
    // }
  }
  if t.indirectelem() {
    vmem := newobject(t.elem)       // 给 elem 分配内存
    *(*unsafe.Pointer)(elem) = vmem // bucket 里面 elem 的槽保存新分配的地址
  }
  // 移动 key 到 insertK（保存新的 key）
  typedmemmove(t.key, insertk, key)
  // 保存 tophash
  *inserti = top
  // map 元素个数 +1
  h.count++
done:
  // 并发写则报错（多个协程同时写 map）
  if h.flags&hashWriting == 0 { // 写标志被清除了
    fatal("concurrent map writes")
  }
  // 清除写标志
  h.flags &^= hashWriting
    // bucket 中的值保存的是指针，这个时候就不能返回 bucket 中值的地址了，而是返回 bucket 中值指向的另外一个地址的指针。
  if t.indirectelem() {
    // 获取指向 elem 实际存储地址的指针
    elem = *((*unsafe.Pointer)(elem))
  }
  // 返回存储值的指针
  return elem
}

// 从 map 中删除 key（以及对应的 elem）
// 参数：
// t：map 类型元数据的结构体
// h：实际保存键值对的桶
// key：需要删除的 key
func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
  // map 是空的
  if h == nil || h.count == 0 {
    // 如果 key 的类型不可哈希则 panic
    if t.hashMightPanic() {
      t.hasher(key, 0) // see issue 23734
    }
    return
  }
  // 并发写则抛出 fatal 错误
  if h.flags&hashWriting != 0 {
    fatal("concurrent map writes")
  }
  // 计算 key 的 hash
  hash := t.hasher(key, uintptr(h.hash0))
  // 在调用 t.hasher 之后设置 hashWriting，
  // 因为 t.hasher 可能会 panic ，在这种情况下，我们实际上没有执行 write（delete）。
  h.flags ^= hashWriting
  // 计算 key 落在哪一个 bucket 中
  bucket := hash & bucketMask(h.B)
  // 如果正在扩容，则迁移 bucket 到新的内存地址中（迁移到新的桶）
  // (迁移当前正在访问的 bucket)
  if h.growing() {
    growWork(t, h, bucket)
  }
  // 获取 bucket 实例（key 所在的 bucket）
  b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
  // 记录原始的 bucket 实例
  //（目的是为了方便加 emptyRest 标记）
  bOrig := b
  // 计算 tophash
  top := tophash(hash)
search:
  // 在 bucket 内进行搜索
  for ; b != nil; b = b.overflow(t) {
    // 遍历 bucket 的每一个槽
    for i := uintptr(0); i < bucketCnt; i++ {
      // tophash 不想等的时候，需要判断后面是否还有元素
      if b.tophash[i] != top {
        // 从 i 开始 bucket 后面都是空的了，
        // 中止搜索过程（去除写标记，函数执行完毕）
        if b.tophash[i] == emptyRest {
          break search
        }
        // 还有元素，继续搜索
        continue
      }
      // tophash 相等
      // 获取 key 在 bucket 中的内存地址
      k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
      k2 := k // k2 代表的是指向实际存储 key 的指针（unsafe.Pointer） 
      // k2 指向原始的地址
      if t.indirectkey() {
        k2 = *((*unsafe.Pointer)(k2))
      }
      // key 不想等，继续检查下一个 slot（continue）
      if !t.key.equal(key, k2) {
        continue
      }
      // 只有在键中有指针时才清除键。
      // 清空 key 的内存
      if t.indirectkey() {
        // 清除 bucket 里面保存 key 的内存
        //（bucket 只是存储了 key 的指针）
        *(*unsafe.Pointer)(k) = nil
      } else if t.key.ptrdata != 0 {
        // 清除包含指针的 key
        memclrHasPointers(k, t.key.size)
      }
      // 值的地址
      e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
      // 清空值
      if t.indirectelem() {
        // 清除 bucket 里面保存 elem 的内存
        *(*unsafe.Pointer)(e) = nil
      } else if t.elem.ptrdata != 0 {
        // 清除包含指针的 elem（值）
        memclrHasPointers(e, t.elem.size)
      } else {
        // 清除不包含指针的 elem 的内存
        memclrNoHeapPointers(e, t.elem.size)
      }
      // tophash 设置为空标记
      b.tophash[i] = emptyOne
      // 如果 bucket 现在以一堆 emptyOne 状态结束，
      // 将这些状态更改为 emptyRest 状态。
      // 最好将其作为一个单独的函数，但 for 循环当前不可内联。（所以用 goto）
      if i == bucketCnt-1 {
        // 要删除的 key 是 bucket 里面的最后一个元素。
        // 同时还有溢出桶，并且溢出桶里面还有元素 => 表明当前删除的 key 不是 bucket 以及溢出桶里面的最后一个元素。
        if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
          // 不是最后一个元素
          goto notLast
        }
      } else {
        // 要删除的 key 不是 bucket 的最后一个元素。
        // 并且后面还有元素。
        if b.tophash[i+1] != emptyRest {
          goto notLast
        }
      }
      
      // 执行到这里的时候，表明刚刚删除的 key 是 bucket 以及溢出桶中的最后一个元素。
      // 如果不是最后一个元素的话，上面的 if 判断已经跳转了。
      
      // 下面的 for 循环做的事情是：
      // 1. 将当前 key 的标志设置为：emptyRest，表示后面没有元素了。
      // 2. 从 bucket 的第一个 key 出发遍历所有的槽（包含溢出桶），
      //    将最后一个元素以后一直到被删除的 key 的中间的所有槽标记为 emptyRest
      // 目的是，在后续遍历的时候可以避免一些不必要的查找操作，见到 emptyRest 就可以直接中断循环了。
      // 例子，bucket 里 key 的内存布局为 | nil | a | nil | nil | b | nil |
      // b 被删除的时候，b 以及 a 后面的两个元素都要标记为 emptyRest（溢出桶同理）
      for {
        // 给当前遍历到的 bucket 槽打上 emptyRest 标记
        b.tophash[i] = emptyRest
        if i == 0 { // 当前的桶遍历完了（因为是从后往前遍历）
          // b 是普通桶（不是溢出桶）
          if b == bOrig {
            // 所有空的槽都处理完了
            break
          }
          // b 是上一次循环处理的桶
          c := b // c 是上一个 b 
          // 查找上一个存储桶，在其最后一个条目处继续。 
          // 如：bucket <- overflow1 <- overflow2 <- ... <- overflowN
          // 假设 c 是 overflow2，那么下面的循环过后，b 就是 overflow1
          // prevB.overflow = b  => 找 prevB，也即：遍历完当前的桶，找前一个桶。
          for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {
          }
          // b 指向了前一个 bucket（前一个桶）
          // 处理前一个 bucket 的最后一个槽
          i = bucketCnt - 1
        } else {
          // 继续处理前一个槽
          i--
        }
        // 找到了一个不是空的槽，表示有数据了，不需要再打 emptyRest 标记了。
        if b.tophash[i] != emptyOne {
          break
        }
      }
      // 被删除的元素如果不是最后一个元素，直接跳转到这里。
    notLast:
      // 找到了元素，并且删除了。
      // map 的元素个数减 1
      h.count--
      // 重置哈希种子，使攻击者更难重复触发哈希冲突。见 issue 25237。
      if h.count == 0 {
        h.hash0 = fastrand()
      }
      // 在 bucket 内找到了对应的元素，并且删除了。
      // 退出循环。
      break search
    }
  }
  // 如果当前没有写标记，则抛出 fatal 错误（不能并发读写 map）
  if h.flags&hashWriting == 0 {
    fatal("concurrent map writes")
  }
  // 清除写标记
  h.flags &^= hashWriting
}

// 条件：
// 1. 没有在扩容
// 2. 超过负载因子
// 3. 太多溢出桶
if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
    hashGrow(t, h)
}
// 判断是否超过负载因子。
func overLoadFactor(count int, B uint8) bool {
  return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
// 判断是否有太多的溢出桶了
// 多的标准是：
// B <= 15 的时候，溢出桶数量大于 2^B 的时候
// B > 15 的时候，溢出桶的数量大于 2^15 的时候
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
  // 如果阈值太低，我们会做额外的工作。
  // 如果阈值太高，则增长和收缩的 map 会保留大量未使用的内存。
  // “太多” 意味着（大约）与常规桶一样多的溢出桶。
  // 有关详细信息，请参见incrnoverflow。
  // B > 15 => 2 ^ 15，B <= 15 => 2 ^ B
  if B > 15 {
    B = 15
  }
  return noverflow >= uint16(1)<<(B&15)
}

// hash 扩容（这个方法只是分配了空间，实际上还没有做数据复制的操作）
// 参数：
// t：map 类型元信息
// h：实际保存键值对的结构体
func hashGrow(t *maptype, h *hmap) {
  // 扩容的两种情况：
  // 1、如果我们达到了负载系数，就要进行 2 倍扩容。
  // 2、否则，如果溢出桶太多，进行等量扩容。
  bigger := uint8(1)
  // 尚未超过负载因子，进行等量扩容
  if !overLoadFactor(h.count+1, h.B) {
    bigger = 0 // 等量扩容
    h.flags |= sameSizeGrow
  }
  // 记录旧的 buckets
  oldbuckets := h.buckets
  // 分配新的内存空间，oldbuckets 将会被渐进式迁移到 newbuckets 中
  newbuckets, nextOverflow := makeBucketArray(t, h.B+bigger, nil)
  // flags 标记有使用旧桶
  // 正在迭代的时候扩容
  // 先把 h.flags 中的迭代标记位清除。
  // 最后如果发现 h.flags 中还有迭代标记位，说明在扩容的过程中有新的迭代操作，
  // 那就把它转移到 oldIterator 中。
  flags := h.flags &^ (iterator | oldIterator)
  if h.flags&iterator != 0 {
    flags |= oldIterator
  }
  // 提交扩容操作
  h.B += bigger // 加上扩容的数量
  h.flags = flags
  h.oldbuckets = oldbuckets // 记录旧桶
  h.buckets = newbuckets    // 指向新的桶数组
  h.nevacuate = 0           // 0 个桶已完成迁移（当前函数只是分配空间，不做迁移）
  h.noverflow = 0           // 所有溢出桶没有了（移动到了 oldoverflow）
  // 记录扩容前的溢出桶
  if h.extra != nil && h.extra.overflow != nil {
    if h.extra.oldoverflow != nil {
      throw("oldoverflow is not nil")
    }
    h.extra.oldoverflow = h.extra.overflow
    h.extra.overflow = nil
  }
  // 扩容之后，h.B+bigger >= 4 了，预分配了溢出桶（扩容前没有溢出桶）
  // 所以这里要记录溢出桶
  if nextOverflow != nil {
    if h.extra == nil {
      h.extra = new(mapextra)
    }
    h.extra.nextOverflow = nextOverflow
  }
  // 哈希表数据的实际迁移过程是通过 growWork() 和 evacuate() 增量完成的。
}

// 桶迁移
// 参数：h 需要扩容的 map，t map 类型信息，bucket 旧桶的索引
// 1、迁移当前访问到的桶（mapassign、mapdelete 的时候）
// 2、继续逐个迁移 bucket，直到迁移完成（这个是从第一个桶开始迁移的）
func growWork(t *maptype, h *hmap, bucket uintptr) {
  // 迁移当前访问到的桶
  evacuate(t, h, bucket&h.oldbucketmask())
    // 继续逐个迁移 bucket，直到迁移完成
  if h.growing() {
    evacuate(t, h, h.nevacuate)
  }
}

// 迁移的目的地（旧桶 -> 目标桶）
// evacuate 中会定义两个这个 evacDst 变量，
// 一个指向 h.buckets 的前半部分，一个指向后半部分。（对应前一个图的 x，y）
// 迁移的时候，会根据 key 的哈希值的倒数第 4 位来决定迁移到哪个 evacDst 中。
type evacDst struct {
  b *bmap          // 迁移目的地 bucket
  i int            // key/elem 在迁移目标 bucket 里面对应的下标
  k unsafe.Pointer // 目标 bucket 下一个保存 key 的地址指针
  e unsafe.Pointer // 目标 bucket 下一个保存 elem 的地址指针
}
// 扩容的时候，bucket 迁移的实现
// oldbucket 需要迁移的旧桶索引
func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
  // b 指向旧桶
  b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
  // 扩容之前的桶的数量
  // oldbucket+newbit 对应 y，oldbucket 对应 x
  newbit := h.noldbuckets()
  // 如果 b 尚未迁移，则进行迁移
  if !evacuated(b) {
    // xy 包含 x 和 y（低和高）迁移目的地。
    // 迁移的时候，在 h.buckets 中，前 noldbuckets 个桶就是 x，后 noldbuckets 个桶就是代表 y。
    var xy [2]evacDst
    // x 存储了新桶的地址
    x := &xy[0]
    // x 指向 oldbucket 可能迁移到的新桶（h.buckets 的前半部分）
    x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
    // x 桶中下一个用来保存旧桶的 key 的地址
    x.k = add(unsafe.Pointer(x.b), dataOffset)
    // x 桶中下一个用来保存旧桶的 elem 的地址
    x.e = add(x.k, bucketCnt*uintptr(t.keysize))
    // 如果不是等量扩容（有可能会迁移到 oldbucket+newbit 的位置上）
    if !h.sameSizeGrow() {
      y := &xy[1]
      // y 指向增量空间上的第 oldbucket+newbit 个位置
      y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
      // y 桶中下一个保存旧桶 key 的地址
      y.k = add(unsafe.Pointer(y.b), dataOffset)
      // y 桶中下一个保存旧桶 elem 的地址
      y.e = add(y.k, bucketCnt*uintptr(t.keysize))
    }
    // 开始迁移旧桶（同时也会迁移溢出桶）
    for ; b != nil; b = b.overflow(t) {
      // 旧 bucket 上第一个 key
      k := add(unsafe.Pointer(b), dataOffset)
      // 旧 bucket 上第一个 value
      e := add(k, bucketCnt*uintptr(t.keysize))
      // 遍历 bucket 的槽
      // 获取需要迁移的 key/elem(k/e) 对，迁移到新桶上(&xy[useY])
      for i := 0; i < bucketCnt; i, k, e = i+1, add(k, uintptr(t.keysize)), add(e, uintptr(t.elemsize)) {
        // 获取旧的 tophash
        top := b.tophash[i]
        // bucket 的这个槽是空的
        if isEmpty(top) {
          // 写入已迁移标记
          b.tophash[i] = evacuatedEmpty
          // 处理下一个 key/elem
          continue
        }
        // tophash 错误
        if top < minTopHash {
          throw("bad map state")
        }
        // 复制一份 k
        k2 := k
        // k2 指向实际的 key
        if t.indirectkey() {
          k2 = *((*unsafe.Pointer)(k2))
        }
        // useY 决定了是迁移到 x 还是 y，如果是等量扩容，那么就是迁移到 x
        var useY uint8
        // 如果不是等量扩容
        if !h.sameSizeGrow() {
          // 计算哈希以做出迁移决定（是否需要将此 key/elem 迁移到桶 x 或桶 y）。
          hash := t.hasher(k2, uintptr(h.hash0))
          if h.flags&iterator != 0 && !t.reflexivekey() && !t.key.equal(k2, k2) {
            // 下面这段是原英文注释的翻译（可能不太准确）：
            // 如果 key != key（不是一个数字），则散列可能（并且可能）与旧散列完全不同。
            // 此外，它是不可再现的。
            // 在迭代器存在的情况下，再现性是必需的，因为我们的迁移决策必须与迭代器所做的任何决策相匹配。
            // 幸运的是，我们可以任意发送这些 key。
            // 此外，tophash 对于这些类型的 key 没有意义。我们让 tophash 的最低位的决定如何迁移。
            // 我们为下一个级别重新计算一个新的随机 tophash，这样在多次扩容后，这些 key 将均匀分布在所有桶中。
            useY = top & 1
            top = tophash(hash)
          } else {
            // 原理参考上面那个图。
            if hash&newbit != 0 { // 取决于 oldB + 1 位是 0 还是 1
              useY = 1
            }
          }
        }
        if evacuatedX+1 != evacuatedY || evacuatedX^1 != evacuatedY {
          throw("bad evacuatedN")
        }
        // 记录旧桶的迁移状态
        b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
        // dst 是迁移的目标 bucket
        dst := &xy[useY]
        // 目标 bucket 装不下了，使用溢出桶
        if dst.i == bucketCnt {
          // 创建溢出桶
          dst.b = h.newoverflow(t, dst.b)
          dst.i = 0
          // dst.k 指向溢出桶的第一个 key 的地址
          dst.k = add(unsafe.Pointer(dst.b), dataOffset) 
          // dst.e 指向溢出桶的第一个 elem 的地址
          dst.e = add(dst.k, bucketCnt*uintptr(t.keysize))
        }
        // 使用 & 运算优化，不用进行边界检查
        // 记录 tophash
        dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
        // 将旧的 key/elem 复制到 dst 指向的槽
        if t.indirectkey() { // bucket 的 key 保存的是指针
          // 修改实际存储 key 的内存
          *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
        } else {
          // 修改 bucket 中保存 key 的内存
          typedmemmove(t.key, dst.k, k) // copy elem
        }
        if t.indirectelem() { // bucket 的 elem 保存的是指针
          // 修改实际存储 elem 的内存
          *(*unsafe.Pointer)(dst.e) = *(*unsafe.Pointer)(e)
        } else {
          // 修改 bucket 中保存 elem 的内存
          typedmemmove(t.elem, dst.e, e)
        }
        // 目标桶的元素个数 +1
        // dst 指向下一个空的槽（slot/cell）
        dst.i++
        // 这些更新可能会将这些指针推到 key 或 elem 数组的末尾。
        // 这没关系，因为我们在桶的末端有溢出桶指针，以防止指针指向桶的末端。
        // 如果指向数组末尾，在下次迁移的时候，会创建溢出桶。
        dst.k = add(dst.k, uintptr(t.keysize))
        dst.e = add(dst.e, uintptr(t.elemsize))
        // 上面有判断 dst.i == bucketCnt，所以这里不会溢出
      }
    }
    // 取消链接溢出桶并清除 key/elem 以帮助 GC。（清除旧桶的内存）
    if h.flags&oldIterator == 0 && t.bucket.ptrdata != 0 {
      b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
      // tophash 状态不能清除。
      // 但是 key/elem 都可以清除。
      ptr := add(b, dataOffset)
      n := uintptr(t.bucketsize) - dataOffset
      memclrHasPointers(ptr, n)
    }
  }
  // 刚刚迁移的桶，就是顺序迁移的下一个桶，
  // 则需要更新 nevacuate 字段，表示已经迁移了多少个桶
  if oldbucket == h.nevacuate {
    advanceEvacuationMark(h, t, newbit)
  }
}

// 记录迁移进度（从顺序迁移的位置往后遍历，保证 nevacuate 指向下一个尚未迁移的桶）
// 参数：h 需要扩容的 map，t map 类型信息，newbit 是旧桶的数量
func advanceEvacuationMark(h *hmap, t *maptype, newbit uintptr) {
  // nevacuate 索引加 1
  h.nevacuate++
  // 往后找一个未迁移的桶（最多遍历 1024 个桶）。
  stop := h.nevacuate + 1024
  if stop > newbit {
    stop = newbit
  }
  // 向后遍历，找到第一个未迁移的桶。
  for h.nevacuate != stop && bucketEvacuated(t, h, h.nevacuate) {
    h.nevacuate++
  }
  // 这意味着所有旧桶都迁移完了
  if h.nevacuate == newbit {
    // 扩容已经完成。释放旧的普通桶数组。
    h.oldbuckets = nil
    // 也可以丢弃旧的溢出桶。
    // 如果它们仍然被迭代器引用，那么迭代器将保存指向切片的指针。
    //（但是 h 不再需要保存指向切片的指针）
    if h.extra != nil {
      h.extra.oldoverflow = nil
    }
    // 移除等量扩容标志
    h.flags &^= sameSizeGrow
  }
}

stop := h.nevacuate + 1024
if stop > newbit {
    stop = newbit
}

// 哈希迭代结构。
type hiter struct {
  // 必须排在第一位。 写入 nil 表示迭代结束
  key unsafe.Pointer
  // 必须在第二个位置（参见 cmd/compile/internal/walk/range.go）。
  elem unsafe.Pointer
  t    *maptype       // map 的类型信息，包括 key、elem 的类型等信息
  h    *hmap          // 需要迭代的 hmap
  // hash_iter 初始化时的 bucket 指针
  buckets unsafe.Pointer
  // 当前正在遍历的 bucket
  bptr *bmap
  // 保持 hmap.buckets 的溢出桶存活
  overflow *[]*bmap
  // 保持 hmap.oldbuckets 的溢出桶存活
  oldoverflow *[]*bmap
  // bucket 迭代开始位置（随机选择的 bucket）
  startBucket uintptr
  // 在迭代期间开始的桶内偏移量（应该足够大以容纳 bucketCnt-1）
  offset uint8
  // 已经从桶数组的末尾环绕到开始
  wrapped     bool
  B           uint8   // 就是当前遍历的 hmap 的那个 B
  i           uint8   // 当前遍历的 bucket 内 key 的索引
  bucket      uintptr // 当前遍历的 bucket
  checkBucket uintptr
}

// mapiterinit 初始化用于 range 遍历 map 的 hiter 结构。（初始化 hiter）
// 'it' 指向的 hiter 结构由编译器顺序传递在堆栈上分配，或由 reflect_mapiterinit 在堆上分配。
// 两者都需要将 hiter 置零，因为结构包含指针。
func mapiterinit(t *maptype, h *hmap, it *hiter) {
  // hiter 记录 map 的类型信息
  it.t = t
  // 如果 map 是空的直接返回
  if h == nil || h.count == 0 {
    return
  }
  // 个人猜测：内存对齐判断，这个由编译器决定的
  if unsafe.Sizeof(hiter{})/goarch.PtrSize != 12 {
    throw("hash_iter size incorrect") // see cmd/compile/internal/reflectdata/reflect.go
  }
  // it 关联上 map
  it.h = h
  // 获取桶状态的快照
  it.B = h.B
  // 当前的 buckets
  it.buckets = h.buckets
  // bucket 里面没有包含指针
  if t.bucket.ptrdata == 0 {
    // 分配当前切片并记住指向当前切片和旧切片的指针。
    // 这将保持所有相关的溢出桶处于活动状态，即使在迭代时表增长和/或溢出桶添加到表中。
    h.createOverflow()
    it.overflow = h.extra.overflow
    it.oldoverflow = h.extra.oldoverflow
  }
  
  // 决定从哪里开始遍历。
  // 策略：随机选定一个 bucket，然后从该 bucket 开始遍历。
  // 生成随机数
  var r uintptr
  if h.B > 31-bucketCntBits {
    r = uintptr(fastrand64())
  } else {
    r = uintptr(fastrand())
  }
  // r => 扫描的入口（随机选的 bucket）
  it.startBucket = r & bucketMask(h.B)
  // 随机定位的 bucket 中的槽。
  it.offset = uint8(r >> h.B & (bucketCnt - 1))
  // 记录当前扫描的 bucket
  it.bucket = it.startBucket
  // 记住我们有一个迭代器。
  // 可以与另一个 mapiteinit() 同时运行。
  if old := h.flags; old&(iterator|oldIterator) != iterator|oldIterator {
    atomic.Or8(&h.flags, iterator|oldIterator)
  }
  // 开始遍历
  mapiternext(it)
}

for ; i < bucketCnt; i++ {
  // 桶内第 i 个元素
  offi := (i + it.offset) & (bucketCnt - 1)
}

// bucket 是当前要遍历的 bucket 的下标
// it.h.oldbucketmask() 是旧桶的 B 的掩码
oldbucket := bucket & it.h.oldbucketmask()

// 参数：迭代器实例
func mapiternext(it *hiter) {
  // 获取底层的 hmap 实例
  h := it.h
  // 正在插入、修改、删除 key 但时候，不能获取下一个 key，
  // 注意：这不能保证插入、修改、删除之后，进行迭代。
  if h.flags&hashWriting != 0 {
    fatal("concurrent map iteration and map write")
  }
  t := it.t           // *maptype
  bucket := it.bucket // 当前遍历到的 bucket 下标（int 类型）
  b := it.bptr        // 当前 bucket 的指针（实际的 bucket，bmap 指针类型）
  i := it.i           // 迭代器当前遍历到的位置（bucket 内 key 的位置）
  checkBucket := it.checkBucket // 这个用来判断是否是增量扩容的
next:
  // 注意：下面的 if 的功能是，获取下一个桶。
  // 如果 b 是 nil，有以下两种情况：
  // a. 第一次遍历，还没有遍历到任何 bucket。
  // b. 遍历完最后一个 bucket 了。
  if b == nil {
    // 已经迭代完了，直接退出函数
    if bucket == it.startBucket && it.wrapped {
      // for...range 查看到 key 是 nil 会中止迭代
      it.key = nil
      it.elem = nil
      return
    }
    // 如果正在扩容
    if h.growing() && it.B == h.B {
      // 迭代器是在扩容过程中启动的，扩容尚未完成。
      // 如果我们正在查看的存储桶尚未迁移，
      // 那么我们需要遍历旧存储桶，同时只返回将迁移到此存储桶的数据。
      // 那些需要迁移到另一个下标的桶则跳过。
      oldbucket := bucket & it.h.oldbucketmask()
      // 获取旧桶
      b = (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
      if !evacuated(b) { // 旧桶还没有迁移
        checkBucket = bucket
      } else { // 已经迁移了，获取新桶
        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++
    // 判断当前遍历的桶是否到最后一个桶了
    if bucket == bucketShift(it.B) {
      bucket = 0
      it.wrapped = true // 已经从第一个随机定位的 bucket 遍历到最后一个 bucket 了，下一个应该是第一个 bucket 了
    }
    // 开始遍历新的 bucket 的时候，重置 i
    i = 0
  }
  // 开始遍历桶内的键值对
  for ; i < bucketCnt; i++ {
    // 计算桶内键值对的下标（从随机的 it.offset 下标开始遍历）
    offi := (i + it.offset) & (bucketCnt - 1)
    // 如果槽是空的，或者 key 已经迁移，则跳过。
    if isEmpty(b.tophash[offi]) || b.tophash[offi] == evacuatedEmpty {
      continue
    }
    // 桶内第 i 个元素的 key 的指针
    // 获取 key 或 elem 的解析前面的小节有详细的解释了，不再赘述。
    k := add(unsafe.Pointer(b), dataOffset+uintptr(offi)*uintptr(t.keysize))
    if t.indirectkey() {
      k = *((*unsafe.Pointer)(k))
    }
    // 桶内第 i 个元素的 elem 的指针
    e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+uintptr(offi)*uintptr(t.elemsize))
    // 增量扩容的 key 判断
    // 需要判断迁移之后的 key 落入的是 h.buckets 的前半部分还是后半部分（x 还是 y）
    // 具体看上面的迁移实现。
    if checkBucket != noCheck && !h.sameSizeGrow() {
      if t.reflexivekey() || t.key.equal(k, k) {
        // key 是可比较的
        // 如果这个 key 将会被迁移到 h.buckets 的后半部分，跳过它
        hash := t.hasher(k, uintptr(h.hash0))
        if hash&bucketMask(it.B) != checkBucket {
          continue
        }
      } else {
        // 对于不可比较的 key，
        // 是由 tophash 的最低位来决定迁移到前半部分还是后半部分的。
        // 取 checkBucket 的最高位来比较，因为 checkBucket 的最高位决定了
        // 当前遍历的 bucket 是上半部分还是后半部分的 bucket。
        if checkBucket>>(it.B-1) != uintptr(b.tophash[offi]&1) {
          // 如果当前的 key 没有落入当前遍历的 bucket，则跳过它
          continue
        }
      }
    }
    
    if (b.tophash[offi] != evacuatedX && b.tophash[offi] != evacuatedY) ||
      !(t.reflexivekey() || t.key.equal(k, k)) {
      // 上面的判断：
      // 1、表示 key 还没有迁移。
      // 2、或者，key 是不可比较的。
      // 则直接返回
      it.key = k
      if t.indirectelem() {
        e = *((*unsafe.Pointer)(e))
      }
      it.elem = e
    } else {
      // 自迭代器启动以来，哈希表已扩容。
      // key 已经被迁移到其他地方。
      // 检查当前哈希表中的数据。
      // 此代码处理已删除、更新或删除并重新插入 key 的情况。
      // 注意：我们需要重新标记 key，因为它可能已更新为 equal() 但不是相同的 key（例如 +0.0 vs -0.0）。
      // 获取当前遍历到的 key/elem。
      rk, re := mapaccessK(t, h, k)
      if rk == nil {
        // key 已经被删除了，继续遍历下一个 key
        continue
      }
      // 外部是通过 it 的 key/elem 来获取当前遍历到的键值对的
      it.key = rk
      it.elem = re
    }
    // 记录当前迭代的 bucket
    it.bucket = bucket
    // 遍历到下一个 bucket 了，更新 bptr
    if it.bptr != b { // avoid unnecessary write barrier; see issue 14921
      it.bptr = b
    }
    // 迭代器的 i 指向 bucket 内的下一个 key
    it.i = i + 1
    // 记录是否需要检查 key 的标记
    it.checkBucket = checkBucket
    // 找到了键值对（保存在 it.key/it.elem 中了），返回。
    // mapiternext 外部可以通过 hiter 的 key/elem 属性来获取当前遍历到的 key/val。
    // 遍历下一个元素的时候，再次调用 mapiternext 函数。
    //（无所谓，hiter 会记住迭代到哪里的）
    // 也即：每遍历一个元素，调用一次 mapiternext 函数。
    return
  }
  // 当前的 bucket 遍历完了，那么继续从溢出桶中查找下一个元素。
  // b 指向溢出桶，迭代溢出桶
  b = b.overflow(t)
  // 遍历下一个桶了，key 从 0 开始遍历
  i = 0
  // 遍历当前 bucket 的溢出桶
  goto next
}