Go源码解析——Map篇

举个例子：我们来细看下 makeBucketArray 中「处理额外添加 bucket 的情况」的情况，我们以 b 为 5 为例子：

if base != nbuckets { //此时 base 为 2^5 = 32 ，nbuckets 为 2^5 + 2^(5-4)=34
    nextOverflow = (*bmap)(add(buckets, base*uintptr(t.bucketsize))) // step 1// 这里设置表示整体 buckets 的最后一个 bucket 
    last := (*bmap)(add(buckets, (nbuckets-1)*uintptr(t.bucketsize))) //step 2
    last.setoverflow(t, (*bmap)(buckets))//step 3: 将最后一个的 bucket(为bmp) 的 overflow 指针指向头部
}

makemap_small 源码:

func makemap_small() *hmap { //这里看到只是初始化了一个hash0,说明后续的初始化可能放在赋值中
    h := new(hmap)
    h.hash0 = fastrand()
    return h
}

总结：

• 无论是字面量初始化还是make初始化，当所需Map分配到堆上且所需长度<=8时，使用runtime.makemap_small()初始化。
• 无论是字面量初始化还是make初始化，当所需Map分配到不需要分配到堆上且所需长度<=8时，通过快速哈希方式创建。
• 其余情况会调用runtime.makemap()，该函数的执行过程如下：
• 校验是否内存溢出
• 获得随机哈希种子
• 计算传入长度所需的B值，这个值是最小值，即最小需要1<
• 如果B<4则不创建溢出bmap ，为的是节省资源，否则创建1<<(B-4)个溢出bmap
• 然后创建一个所需长度的连续的bmap数组，并且返回头指针给hmap.buckets。
• 设置溢出bmap（如果有）的一些信息。
• 返回*hmap，也就是说 make(map)返回的是一个hmap的指针。

Go 语言中读取 map 有两种语法：带 comma 和 不带 comma。当要查询的 key 不在 map 里，带 comma 的用法会返回一个 bool 型变量提示 key 是否在 map 中；而不带 comma 的语句则会返回一个 value 类型的零值。如果 value 是 int 型就会返回 0，如果 value 是 string 类型，就会返回空字符串。

value := m["name"]
fmt.Printf("value:%s", value)

value, ok := m["name"]
  if ok {
    fmt.Printf("value:%s", value)
  }

两种语法对应到底层两个不同的函数，那么在底层是如何定位到key的呢？稍后我们对函数进行源码分析。

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer
func mapaccess2(t *maptype, h *hmap, key unsafe.Pointer) (unsafe.Pointer, bool)

key 经过哈希计算后得到哈希值，共 64 个 bit 位（64位机，32位机就不讨论了，现在主流都是64位机），计算它到底要落在哪个桶时，只会用到最后 B 个 bit 位。还记得前面提到过的 B 吗？如果 B = 5，那么桶的数量，也就是 buckets 数组的长度是 2^5 = 32。例如，现在有一个 key 经过哈希函数计算后，得到的哈希结果是：

低5位，确定是哪个bucket（每个bucket只能存8对key-value，一旦超过就通过overflow指向下一个bmap）
高8位，确定是桶中的哪个位置（如果key的高8位存在于topbits数组中第i位置，那么key和value也是在对应的keys、values数组中第i个位置，存储时原理一致）

用最后的 5 个 bit 位，也就是 01010，值为 10，也就是 10 号桶。这个操作实际上就是取余操作，但是取余开销太大，所以代码实现上用的位操作代替。 再用哈希值的高 8 位，找到此 key 在 bucket 中的位置，这是在寻找已有的 key。最开始桶内还没有 key，新加入的 key 会找到第一个空位放入。 buckets 编号就是桶编号，当两个不同的 key 落在同一个桶中，也就是发生了哈希冲突。冲突的解决手段是用链表法：在 bucket 中，从前往后找到第一个空位。这样，在查找某个 key 时，先找到对应的桶，再去遍历 bucket 中的 key。

HOBHash 指的就是 top hash，每个bucket中topHash唯一。key 和 value 是各自放在一起的，并不是 key/value/… 这样的形式。可以省略掉 padding 字段，节省内存空间。
例如，有这样一个类型的 map：map[int64]int8，如果按照 key/value… 这样的模式存储，那在每一个 key/value 对之后都要额外 padding 7 个字节；而将所有的 key，value 分别绑定到一起，这种形式 key/key/…/value/value/…，则只需要在最后添加 padding，每个 bucket 设计成最多只能放 8 个 key-value 对，如果有第 9 个 key-value 落入当前的 bucket，那就需要再构建一个 bucket ，通过 overflow 指针连接起来。

上图中，假定 B = 5，所以 bucket 总数就是 2^5 = 32。首先计算出待查找 key 的哈希，使用低 5 位 00110，找到对应的 6 号 bucket，使用高 8 位 10010111，对应十进制 151，在 6 号 bucket 中寻找 tophash 值（HOB hash）为 151 的 key，找到了 2 号槽位，这样整个查找过程就结束了。
如果在 bucket 中没找到，并且 overflow 不为空，还要继续去 overflow bucket 中寻找，直到找到或是所有的 key 槽位都找遍了，包括所有的 overflow bucket。

map不支持并发安全，并发读写会产生panic​
如果map正在迁移，则优先从oldbuckets中查找kv

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   if raceenabled && h != nil {//启用数据竞争检测
      callerpc := getcallerpc()
      pc := funcPC(mapaccess1)
      racereadpc(unsafe.Pointer(h), callerpc, pc)
      raceReadObjectPC(t.key, key, callerpc, pc)
   }
   if msanenabled && h != nil {//启用-msan检测
      msanread(key, t.key.size)
   }
   if h == nil || h.count == 0 {//如果h什么都没有，返回零值
      if t.hashMightPanic() {
         t.hasher(key, 0) // see issue 23734
      }
      return unsafe.Pointer(&zeroVal[0])
   }
   //读写冲突，map不支持并发安全，并发读写会产生panic
   if h.flags&hashWriting != 0 {
      throw("concurrent map read and map write")
   }
   hash := t.hasher(key, uintptr(h.hash0))//计算hash值
   m := bucketMask(h.B)//m表示map中bucket的数量
   b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))//利用`hash mod m`可以计算bucket索引，b表示对应bucket的首地址
   // map正在迁移的场景，如果map正在迁移，则优先从oldbuckets中查找kv
   if c := h.oldbuckets; c != nil {
      if !h.sameSizeGrow() {//map是否在扩容迁移，如果是等量扩容迁移，则oldbuckets实际的bucket数量是m的一半（扩容会让bucket数量增加一倍）
         m >>= 1
      }
      // 根据hash值，查找oldbuckets中对应的bucket地址
      oldb := (*bmap)(add(c, (hash&m)*uintptr(t.bucketsize)))
       // 如果oldb的标志位不是撤离状态，则我们从oldb中查找kv
      if !evacuated(oldb) {
         b = oldb
      }
   }
    // top表示hash的高8位，如果hash高8位小于5，则top需要加上5；因为5表示`minTopHash`，top如果是小于等于5，都是表示特殊状态；正常的key的top值都是大于5的
   top := tophash(hash)
bucketloop:
// 逐个查找对应bucket和其溢出bucket
   for ; b != nil; b = b.overflow(t) {
   // 一个bucket有8对kv，逐个查找
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top {
            if b.tophash[i] == emptyRest {
            // 如果b.tophash[i] == emptyRest，表示剩下的kv对都是空的，所以直接跳出循环
               break bucketloop
            }
            continue
         }
         // 查找对应的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) {
         // 如果key相等，则找到对应的value 
            e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))
            if t.indirectelem() {
               e = *((*unsafe.Pointer)(e))
            }
            // 返回value
            return e
         }
      }
   }
   //返回对应的0值
   return unsafe.Pointer(&zeroVal[0])
}

函数整体流程：​

• 判断是否并发读写，如果是，则抛出panic；​
• 计算hash值，根据hash的地位找到对应的bucket，根据高8位，找到对应的kv槽位；​
• map迁移场景下，优先从oldbuckets中查找kv；​
• 比较key，相等则返回value，不等则返回0值；

func main() {// go tool compile -S -l -N main.go
    m1 := make(map[int8]int)
    m1[1] = 1
    m1[2] = 2
    m1[1] = 11
    fmt.Println(m1)
}

map 有很多种类的赋值语句,由于其核心流程是差不多的，我们以 mapassign 来分析

func mapassign(mapType *byte, hmap map[any]any, key *any) (val *any)
func mapassign_fast32(mapType *byte, hmap map[any]any, key any) (val *any)
func mapassign_fast32ptr(mapType *byte, hmap map[any]any, key any) (val *any)
func mapassign_fast64(mapType *byte, hmap map[any]any, key any) (val *any)
func mapassign_fast64ptr(mapType *byte, hmap map[any]any, key any) (val *any)
func mapassign_faststr(mapType *byte, hmap map[any]any, key any) (val *any)

向nil map赋值会引发panic​
map不支持并发读写

const(
    emptyRest      = 0 // this cell is empty, and there are no more non-empty cells at higher indexes or overflows. 不仅说明当前 cell 是空的，而且后面的索引以及 overflows 都为空
    emptyOne       = 1 // this cell is empty
    
    dataOffset = unsafe.Offsetof(struct {
        b bmap
        v int64
    }{}.v) // 表示 bmap 的大小，这里即表示了 [8]uint8 的大小
  
    hashWriting  = 4 // hmap 中 flags 中对应写入位
)

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
   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)
   }
   if h.flags&hashWriting != 0 {//map不支持并发读写
      throw("concurrent map writes")
   }
   //计算hash值
   hash := t.hasher(key, uintptr(h.hash0))

   //map状态设置为hashWriting
   h.flags ^= hashWriting

   if h.buckets == nil {
   //如果map没有初始化bucket，此时申请bucket空间
      h.buckets = newobject(t.bucket) // newarray(t.bucket, 1)
   }

again:
//根据hash的低5位确定在哪个桶
   bucket := hash & bucketMask(h.B)
   //判断是否在扩容
   if h.growing() {
   //将对应的bucket从hmap.oldbuckets迁移到新的buckets中
      growWork(t, h, bucket)
   }
   //目标bucket首地址
   b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize)))
   //hash高八位
   top := tophash(hash)

   var inserti *uint8
   var insertk unsafe.Pointer
   var elem unsafe.Pointer
bucketloop:
   for {
   // 遍历tophash查找key是否已经存在，或者是否有空位插入kv
      for i := uintptr(0); i < bucketCnt; i++ {
         if b.tophash[i] != top {
         // tophash中可能有多个空位，我们记录第一个空位的索引，后面的空位跳过
            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))
            }
            // tophash值表示剩余都是空位，则直接结束循环，因为后面全是空位，不会有相同的key在后面的槽位，此次操作必然是插入，而不是更新
            if b.tophash[i] == emptyRest {
               break bucketloop
            }
            continue
         }
         //获取对应位置的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
         }
         // 更新
         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是满的，而且没找到对应的key，溢出查找
      ovf := b.overflow(t)
      if ovf == nil {
         break
      }
      b = ovf
   }

 // 程序运行到此处，必然是由于没有找到相同的key，此次操作是插入，不是更新；
 // 插入一对kv，我们需要判断map是否需要扩容；
 // overLoadFactor函数用来判断map是否由于数据太多，需要增量1倍扩容
 // tooManyOverflowBuckets函数用来判断map是否需要等量迁移，map由于删除操作，溢出bucket很多，但是数据分布很稀疏，我们可以通过等量迁移，将数据更加紧凑的存储在一起，节约空间；
 // 具体可以看evacuate函数分析；
   if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
      //  hashGrow函数主要是设置hmap.flags为扩容状态，申请新的内存空间用来扩容，同时设置hmap.oldbuckets为原来的hmap.buckets
      hashGrow(t, h)
      goto again // Growing the table invalidates everything, so try again
   }
// inserti == nil表示没有插入的槽位，需要申请溢出bucket
   if inserti == nil {
      // The current bucket and all the overflow buckets connected to it are full, allocate a new one.
      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)
      *(*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:
// 设置flag并写入value
   if h.flags&hashWriting == 0 {
      throw("concurrent map writes")
   }
   h.flags &^= hashWriting
   if t.indirectelem() {
      elem = *((*unsafe.Pointer)(elem))
   }
   return elem
}

// 装载因子超过 6.5​
func overLoadFactor(count int, B uint8) bool {​
  return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)​
}​
​
// overflow buckets 太多​
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {​
  if B > 15 {​
    B = 15​
  }​
  return noverflow >= uint16(1)<<(B&15)​
}

第 1 点：我们知道，每个 bucket 有 8 个空位，在没有溢出，且所有的桶都装满了的情况下，装载因子算出来的结果是 8。因此当装载因子超过 6.5 时，表明很多 bucket 都快要装满了，查找效率和插入效率都变低了。在这个时候进行扩容是有必要的。​
第 2 点：是对第 1 点的补充。就是说在装载因子比较小的情况下，这时候 map 的查找和插入效率也很低，而第 1 点识别不出来这种情况。表面现象就是计算装载因子的分子比较小，即 map 里元素总数少，但是 bucket 数量多（真实分配的 bucket 数量多，包括大量的 overflow bucket）。​
不难想像造成这种情况的原因：不停地插入、删除元素。先插入很多元素，导致创建了很多 bucket，但是装载因子达不到第 1 点的临界值，未触发扩容来缓解这种情况。之后，删除元素降低元素总数量，再插入很多元素，导致创建很多的 overflow bucket，但就是不会触犯第 1 点的规定，你能拿我怎么办？overflow bucket 数量太多，导致 key 会很分散，查找插入效率低得吓人，因此出台第 2 点规定。这就像是一座空城，房子很多，但是住户很少，都分散了，找起人来很困难。​
对于命中条件 1，2 的限制，都会发生扩容。但是扩容的策略并不相同，毕竟两种条件应对的场景不同。​
对于条件 1，元素太多，而 bucket 数量太少，很简单：将 B 加 1，bucket 最大数量(2^B)直接变成原来 bucket 数量的 2 倍。于是，就有新老 bucket 了。注意，这时候元素都在老 bucket 里，还没迁移到新的 bucket 来。新 bucket 只是最大数量变为原来最大数量的 2 倍(2^B*2) 。​
对于条件 2，其实元素没那么多，但是 overflow bucket 数特别多，说明很多 bucket 都没装满。解决办法就是开辟一个新 bucket 空间，将老 bucket 中的元素移动到新 bucket，使得同一个 bucket 中的 key 排列地更紧密。这样，原来，在 overflow bucket 中的 key 可以移动到 bucket 中来。结果是节省空间，提高 bucket 利用率，map 的查找和插入效率自然就会提升。​
由于 map 扩容需要将原有的 key/value 重新搬迁到新的内存地址，如果有大量的 key/value 需要搬迁，会非常影响性能。因此 Go map 的扩容采取了一种称为“渐进式”的方式，原有的 key 并不会一次性搬迁完毕，每次最多只会搬迁 2 个 bucket。

函数整体流程：​

• map优先检查是否有相同的key，如果有，则表示是更新操作；​
• 如果没有相同的key，则表示是插入操作；如果有空位，则在第一个空位处插入；如果没有空位，则增加一个溢出bucket，在溢出bucket中插入；插入操作可能会触发扩容操作；​
• map不是一次性完成扩容的，而是逐步完成扩容的；当在一个bucket中执行插入操作的时候，如果发现需要扩容，则会把这个bucket（包含溢出bucket）全部迁移到新申请的buckets空间中，同时多扩容一个bucket（个人理解是加速扩容速度，否则因为个别bucket一直没有使用，导致map一直维护新旧两个buckets）；​
• map库容分为等量迁移和加倍扩容：等量迁移是为了让稀疏的数据分布更加紧凑（由于删除操作，map可能会很稀疏），加倍扩容是由于插入数据过多，申请一个加倍的空间来存储kv，同时加倍扩容也会删除空的槽位，让数据分布紧凑；

再来看看真正执行搬迁工作的 growWork() 函数

func growWork(t *maptype, h *hmap, bucket uintptr) {
  // 搬迁正在使用的旧 bucket
  evacuate(t, h, bucket&h.oldbucketmask())
  // 再搬迁一个 bucket，以加快搬迁进程if h.growing() {
    evacuate(t, h, h.nevacuate)
  }
}

func (h *hmap) growing() bool {
  return h.oldbuckets != nil
}

搬迁过程evacuate源码：

type evacDst struct {
  b *bmap          // 表示bucket 移动的目标地址
  i int            // 指向 x,y 中 key/val 的 index
  k unsafe.Pointer // 指向 x，y 中的 key
  v unsafe.Pointer // 指向 x，y 中的 value
}

func evacuate(t *maptype, h *hmap, oldbucket uintptr) {
  // 定位老的 bucket 地址
  b := (*bmap)(add(h.oldbuckets, oldbucket*uintptr(t.bucketsize)))
  // 计算容量 结果是 2^B，如 B = 5，结果为32
  newbit := h.noldbuckets()
  // 如果 b 没有被搬迁过
  if !evacuated(b) {
    // 默认是等 size 扩容，前后 bucket 序号不变
    var xy [2]evacDst
    // 使用 x 来进行搬迁
    x := &xy[0]
    x.b = (*bmap)(add(h.buckets, oldbucket*uintptr(t.bucketsize)))
    x.k = add(unsafe.Pointer(x.b), dataOffset)
    x.v = add(x.k, bucketCnt*uintptr(t.keysize))

    // 如果不是等 size 扩容，前后 bucket 序号有变
    if !h.sameSizeGrow() {
      // 使用 y 来进行搬迁
      y := &xy[1]
      // y 代表的 bucket 序号增加了 2^B
      y.b = (*bmap)(add(h.buckets, (oldbucket+newbit)*uintptr(t.bucketsize)))
      y.k = add(unsafe.Pointer(y.b), dataOffset)
      y.v = add(y.k, bucketCnt*uintptr(t.keysize))
    }
    // 遍历所有的 bucket，包括 overflow buckets b 是老的 bucket 地址
    for ; b != nil; b = b.overflow(t) {
      k := add(unsafe.Pointer(b), dataOffset)
      v := add(k, bucketCnt*uintptr(t.keysize))
      // 遍历 bucket 中的所有 cell
      for i := 0; i < bucketCnt; i, k, v = i+1, add(k, uintptr(t.keysize)), add(v, uintptr(t.valuesize)) {
        // 当前 cell 的 top hash 值
        top := b.tophash[i]
        // 如果 cell 为空，即没有 key
        if top == empty {
          // 那就标志它被"搬迁"过
          b.tophash[i] = evacuatedEmpty
          continue
        }
        // 正常不会出现这种情况
        // 未被搬迁的 cell 只可能是 empty 或是
        // 正常的 top hash（大于 minTopHash）
        if top < minTopHash {
          throw("bad map state")
        }
        // 如果 key 是指针，则解引用
        k2 := k
        if t.indirectkey {
          k2 = *((*unsafe.Pointer)(k2))
        }
        var useY uint8
        // 如果不是等量扩容
        if !h.sameSizeGrow() {
          // 计算 hash 值，和 key 第一次写入时一样
          hash := t.key.alg.hash(k2, uintptr(h.hash0))
          // 如果有协程正在遍历 map 如果出现 相同的 key 值，算出来的 hash 值不同
          if h.flags&iterator != 0 && !t.reflexivekey && !t.key.alg.equal(k2, k2) {
            // useY =1 使用位置Y
            useY = top & 1
            top = tophash(hash)
          } else {
            // 第 B 位置 不是 0
            if hash&newbit != 0 {
              //使用位置Y
              useY = 1
            }
          }
        }

        if evacuatedX+1 != evacuatedY {
          throw("bad evacuatedN")
        }
        //决定key是裂变到 X 还是 Y
        b.tophash[i] = evacuatedX + useY // evacuatedX + 1 == evacuatedY
        dst := &xy[useY]                 // evacuation destination
        // 如果 xi 等于 8，说明要溢出了
        if dst.i == bucketCnt {
          // 新建一个 bucket
          dst.b = h.newoverflow(t, dst.b)
          // xi 从 0 开始计数
          dst.i = 0
          //key移动的位置
          dst.k = add(unsafe.Pointer(dst.b), dataOffset)
          //value 移动的位置
          dst.v = add(dst.k, bucketCnt*uintptr(t.keysize))
        }
        // 设置 top hash 值
        dst.b.tophash[dst.i&(bucketCnt-1)] = top // mask dst.i as an optimization, to avoid a bounds check
        // key 是指针
        if t.indirectkey {
          // 将原 key（是指针）复制到新位置
          *(*unsafe.Pointer)(dst.k) = k2 // copy pointer
        } else {
          // 将原 key（是值）复制到新位置
          typedmemmove(t.key, dst.k, k) // copy value
        }
        //value同上
        if t.indirectvalue {
          *(*unsafe.Pointer)(dst.v) = *(*unsafe.Pointer)(v)
        } else {
          typedmemmove(t.elem, dst.v, v)
        }
        // 定位到下一个 cell
        dst.i++
        dst.k = add(dst.k, uintptr(t.keysize))
        dst.v = add(dst.v, uintptr(t.valuesize))
      }
    }
    // Unlink the overflow buckets & clear key/value to help GC.

    // bucket搬迁完毕 如果没有协程在使用老的 buckets，就把老 buckets 清除掉，帮助gc
    if h.flags&oldIterator == 0 && t.bucket.kind&kindNoPointers == 0 {
      b := add(h.oldbuckets, oldbucket*uintptr(t.bucketsize))
      ptr := add(b, dataOffset)
      n := uintptr(t.bucketsize) - dataOffset
      memclrHasPointers(ptr, n)
    }
  }
  // 更新搬迁进度
  if oldbucket == h.nevacuate {
    advanceEvacuationMark(h, t, newbit)
  }
}

扩容后，B 增加了 1，意味着 buckets 总数是原来的 2 倍，原来 1 号的桶“裂变”到两个桶，某个 key 在搬迁前后 bucket 序号可能和原来相等，也可能是相比原来加上 2^B（原来的 B 值），取决于 hash 值 第 6 bit 位是 0 还是 1。原理看下图：

遍历操作：

1.只获取key
     for key := range m {
    fmt.Println(key)
  }

2.只获取value
    for _, value := range m {
    fmt.Println(value)
  }

3.有序遍历map，获取kv
    keys := []string{}
  for k, _ := range m {
    keys = append(keys, k)
  }
  // 排序
  sort.Strings(keys)
  // 有序遍历
  for _, k := range keys {
    fmt.Println(k, m[k])
  }

为什么map是无序的？​
遍历的过程，就是按顺序遍历 bucket，同时按顺序遍历 bucket 中的 key。搬迁后，key 的位置发生了重大的变化，有些 key 飞上高枝，有些 key 则原地不动。这样，遍历 map 的结果就不可能按原来的顺序了。当然，如果我就一个 hard code 的 map，我也不会向 map 进行插入删除的操作，按理说每次遍历这样的 map 都会返回一个固定顺序的 key/value 序列吧。的确是这样，但是 Go 杜绝了这种做法，因为这样会带来误解，以为这是一定会发生的事情，在某些情况下，可能会酿成大错。​
当然，Go 做得更绝，当我们在遍历 map 时，并不是固定地从 0 号 bucket 开始遍历，每次都是从一个随机值序号的 bucket 开始遍历，并且是从这个 bucket 的一个随机序号的 cell 开始遍历。这样，即使你是一个写死的 map，仅仅只是遍历它，也不太可能会返回一个固定序列的 key/value 对了。

//runtime.mapiterinit 遍历时选用初始桶的函数
func mapiterinit(t *maptype, h *hmap, it *hiter) {
  ...
  it.t = t
  it.h = h
  it.B = h.B
  it.buckets = h.buckets
  if t.bucket.kind&kindNoPointers != 0 {
    h.createOverflow()
    it.overflow = h.extra.overflow
    it.oldoverflow = h.extra.oldoverflow
  }

  r := uintptr(fastrand())
  if h.B > 31-bucketCntBits {
    r += uintptr(fastrand()) << 31
  }
  it.startBucket = r & bucketMask(h.B)//找到随机开始的 bucketIndex
  it.offset = uint8(r >> h.B & (bucketCnt - 1))// 找到随机开始的 bucket 的 topHash 的索引
  it.bucket = it.startBucket
    ...

  mapiternext(it)
}

重点是fastrand 的部分，是一个生成随机数的方法：它生成了随机数。用于决定从哪里开始循环迭代。更具体的话就是根据随机数，选择一个桶位置作为起始点进行遍历迭代因此每次重新 for range map，你见到的结果都是不一样的。那是因为它的起始位置根本就不固定！

delete(m, "name")

- func mapdelete(mapType *byte, hmap map[any]any, key *any)
- func mapdelete_fast32(mapType *byte, hmap map[any]any, key any)
- func mapdelete_fast64(mapType *byte, hmap map[any]any, key any)
- func mapdelete_faststr(mapType *byte, hmap map[any]any, key any)
- func mapclear(mapType *byte, hmap map[any]any) // 这个是通过编译器优化所以执行的

首先会检查 h.flags 标志，如果发现写标位是 1，直接 panic，因为这表明有其他协程同时在进行写操作。计算 key 的哈希，找到落入的 bucket。检查此 map 如果正在扩容的过程中，直接触发一次搬迁操作。删除操作同样是两层循环，核心还是找到 key 的具体位置。寻找过程都是类似的，在 bucket 中挨个 cell 寻找。找到对应位置后，对 key 或者 value 进行“清零”操作，将 count 值减 1，将对应位置的 tophash 值置成 Empty。

func mapdelete(t *maptype, h *hmap, key unsafe.Pointer) {
    ...
    if h == nil || h.count == 0 { //如果 hmap 没有初始化，则直接返回
        if t.hashMightPanic() {
            t.hasher(key, 0) // see issue 23734
        }
        return
    }
    if h.flags&hashWriting != 0 { //如果正在进行写入，则 throw
        throw("concurrent map writes")
    }

    hash := t.hasher(key, uintptr(h.hash0)) //算出当前key 的hash

    h.flags ^= hashWriting //将“写入位”置1

    bucket := hash & bucketMask(h.B) //算出对应的 bucketIndex
  
    // 这里上文有源码分析，就不细说了
    if h.growing() { 
        growWork(t, h, bucket)
    }
  
    b := (*bmap)(add(h.buckets, bucket*uintptr(t.bucketsize))) //寻找到对应的 bucket
    bOrig := b
    top := tophash(hash) //找到对应的 top
search:
    for ; b != nil; b = b.overflow(t) { // 遍历当前的 bucket 以及 overflow
        for i := uintptr(0); i < bucketCnt; i++ {
            if b.tophash[i] != top {
                if b.tophash[i] == emptyRest {//如果是 emptyReset，说明之后都不存在了，直接break
                    break search
                }
                continue
            }
            //找到了对应的位置 
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            k2 := k
            if t.indirectkey() {
                k2 = *((*unsafe.Pointer)(k2))
            }
            if !t.key.equal(key, k2) { // hash 冲突了
                continue
            }
            // 这里清理空间 key 的空间
            if t.indirectkey() {
                *(*unsafe.Pointer)(k) = nil
            } else if t.key.ptrdata != 0 { 
                memclrHasPointers(k, t.key.size) 
            }
            //  elem 与上面 key 同理
            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)
            }
            b.tophash[i] = emptyOne // emptyOne表示曾经有过，然后被清空了
        
            // ----这里判断当前位置之后是否还有数据存储过----
            if i == bucketCnt-1 {
                if b.overflow(t) != nil && b.overflow(t).tophash[0] != emptyRest {
                    goto notLast
                }
            } else {
                if b.tophash[i+1] != emptyRest {
                    goto notLast
                }
            }
            // ----------
        
            // 到这里就说明当前的 bucket 的 topIndex 以及之后索引包括 overflow 都没有数据过，准备从后向前进行一波整理
            for { 
                b.tophash[i] = emptyRest //则将当前的 top 设置为 emptyRest
                if i == 0 {//由于是i==0 ，则要寻找到上一个bucket
                    if b == bOrig {
                        break // beginning of initial bucket, we're done.
                    }
                    c := b
                    for b = bOrig; b.overflow(t) != c; b = b.overflow(t) {//找到当前 bucket 的上一个 bucket
                    }
                    i = bucketCnt - 1
                } else {//寻找上一个top
                    i--
                }
                if b.tophash[i] != emptyOne {
                    break
                }
            }
        notLast:
            h.count--
            break search
        }
    }

    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting //将“写入位”置0
}

func mapclear(t *maptype, h *hmap) {
    ...

    if h == nil || h.count == 0 {
        return
    }

    if h.flags&hashWriting != 0 {
        throw("concurrent map writes")
    }

    h.flags ^= hashWriting // "写入位"置1

    h.flags &^= sameSizeGrow //将 sameSizeGrow 清0
    h.oldbuckets = nil
    h.nevacuate = 0
    h.noverflow = 0
    h.count = 0// Keep the mapextra allocation but clear any extra information.if h.extra != nil { // 这里直接数据清空
        *h.extra = mapextra{}
    }

    _, nextOverflow := makeBucketArray(t, h.B, h.buckets)//将其中buckets数据清空，并拿到nextOverFlowif nextOverflow != nil {
        h.extra.nextOverflow = nextOverflow //重新更新 h.extra.nextOverflow
    }

    if h.flags&hashWriting == 0 {
        throw("concurrent map writes")
    }
    h.flags &^= hashWriting //将“写入位”置0
}

• 解决方法1：读写锁 sync.RWMutex

type TestMap struct {
  M    map[int]string
  Lock sync.RWMutex
}

func main() {
  testMap := TestMap{}
  testMap.M = map[int]string{1: "lili"}
  go func() {
    i := 0
    for i < 10000 {
      testMap.Lock.RLock()
      fmt.Println(i, testMap.M[1])
      testMap.Lock.RUnlock()
      i++
    }
  }()

  go func() {
    i := 0
    for i < 10000 {
      testMap.Lock.Lock()
      testMap.M[1] = "lily"
      testMap.Lock.Unlock()
      i++
    }
  }()

    for {
    runtime.GC()
  }
}

• 解决方法2：使用golang提供的 sync.Map

func main() {
  m := sync.Map{}
  m.Store(1, 1)
  i := 0
  go func() {
    for i < 1000 {
      m.Store(1, 1)
      i++
    }
  }()

  go func() {
    for i < 1000 {
      m.Store(2, 2)
      i++
    }
  }()

  go func() {
    for i < 1000 {
      fmt.Println(m.Load(1))
      i++
    }
  }()

  for {
    runtime.GC()
  }
}

数组+链表的结构，数组（Entry[] table）的长度为capacity，Entry的数目被称为HashMap的大小(size);

• 根据Key的hashCode，可以直接定位到存储这个Entry的桶所在的位置，这个时间的复杂度为O(1)；​
• 在桶中查找对应的Entry对象节点，需要遍历这个桶的Entry链表，时间复杂度为O(n);

我们知道，HashMap的桶数目，即Entry[] table数组的长度，由于数组是内存中连续的存储单元，它的空间代价是很大的，但是它的随机存取的速度是Java集合中最快的。我们增大桶的数量，而减少Entry链表的长度，来提高从HashMap中读取数据的速度。这是典型的拿空间换时间的策略。​
但是我们不能刚开始就给HashMap分配过多的桶(即Entry[] table 数组起始不能太大)，这是因为数组是连续的内存空间，它的创建代价很大，况且我们不能确定给HashMap分配这么大的空间，它实际到底能够用多少，为了解决这一个问题，HashMap采用了根据实际的情况，动态地分配桶的数量。

HashMap的权衡策略：
如果HashMap的大小（size）> HashMap的capacity*加载因子（经验值0.75）
HashMap中的Entry[] table 的容量（经验值为16）扩充为当前的一倍；然后重新将以前桶中的Entry链表重新分配到各个桶中

Put方法整体流程：

• 获取这个Key的hashcode值，根据此值确定应该将这一对键值对存放在哪一个桶中，即确定要存放桶的索引；
• 遍历所在桶中的Entry链表，查找其中是否已经有了以Key值为Key存储的Entry对象，
• 若已存在，定位到对应的Entry,其中的Value值更新为新的Value值；返回旧值；
• 若不存在，则根据键值对 创建一个新的Entry对象，然后添加到这个桶的Entry链表的头部。
• 当前的HashMap的大小(即Entry节点的数目)是否超过了阀值，若超过了阀值(threshold)，则增大HashMap的容量(即Entry[] table 的大小)，并且重新组织内部各个Entry排列。

    
    public V put(K key, V value) {
        
            //1.如果key为null，那么将此value放置到table[0],即第一个桶中
            if (key == null)
            return putForNullKey(value);
            //2.重新计算hashcode值，
        int hash = hash(key.hashCode());
        //3.计算当前hashcode值应当被分配到哪一个桶中，获取桶的索引
        int i = indexFor(hash, table.length);
        //4.循环遍历该桶中的Entry列表
        for (Entry e = table[i]; e != null; e = e.next) {
            Object k;
            //5. 查找Entry链表中是否已经有了以Key值为Key存储的Entry对象,
            //已经存在,则将Value值覆盖到对应的Entry对象节点上
            if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {//请读者注意这个判定条件，非常重要！！！
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        //6不存在，则根据键值对 创建一个新的Entry对象，然后添加到这个桶的Entry链表的头部。
        addEntry(hash, key, value, i);
        return null;
    }
 
    
    private V putForNullKey(V value) {
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

    static int hash(int h) {
        // This function ensures that hashCodes that differ only by
        // constant multiples at each bit position have a bounded
        // number of collisions (approximately 8 at default load factor).
        h ^= (h >>> 20) ^ (h >>> 12);
        return h ^ (h >>> 7) ^ (h >>> 4);
    }
 
    
    static int indexFor(int h, int length) {
        return h & (length-1);
    }

当HashMap的大小大于阈值时，HashMap的扩充算法:
当当前的HashMap的大小大于阀值时，HashMap会对此HashMap的容量进行扩充，即对内部的Entry[] table 数组进行扩充。
HashMap对容量（Entry[] table数组长度） 有两点要求：

• 容量的大小应当是 2的N次幂；
• 当容量大小超过阀值时，容量扩充为当前的一倍；

这里第2点很重要,如果当前的HashMap的容量为16，需要扩充时，容量就要变成162 = 32,接着就是322=64、642=128、1282=256…可以看出，容量扩充的大小是呈指数级的级别递增的。
这里容量扩充的操作可以分为以下几个步骤:

• 申请一个新的、大小为当前容量两倍的数组；
• 将旧数组的Entry[] table中的链表重新计算hash值，然后重新均匀地放置到新的扩充数组中；
• 释放旧的数组；

由上述的容量扩充的步骤来看，一次容量扩充的代价非常大，所以在容量扩充时，扩充的比例为当前的一倍，这样做是尽量减少容量扩充的次数。

为了提高HashMap的性能：

• 在使用HashMap的过程中，你比较明确它要容纳多少Entry，你应该在创建HashMap的时候直接指定它的容量；
• 如果你确定HashMap的使用的过程中，大小会非常大，那么你应该控制好加载因子的大小，尽量将它设置得大些。避免Entry[] table过大，而利用率觉很低。

    
    void resize(int newCapacity) {
        Entry[] oldTable = table;
        int oldCapacity = oldTable.length;
        if (oldCapacity == MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return;
        }
 
        Entry[] newTable = new Entry[newCapacity];
        transfer(newTable);
        table = newTable;
        threshold = (int)(newCapacity * loadFactor);
    }
    
    
    void transfer(Entry[] newTable) {
        Entry[] src = table;
        int newCapacity = newTable.length;
        for (int j = 0; j < src.length; j++) {
            Entry e = src[j];
            if (e != null) {
                src[j] = null;
                do {
                    Entry next = e.next;
                    int i = indexFor(e.hash, newCapacity);
                    e.next = newTable[i];
                    newTable[i] = e;
                    e = next;
                } while (e != null);
            }
        }
    }

Get方法整体流程：​

• 获取这个Key的hashcode值，根据此hashcode值决定应该从哪一个桶中查找；​
• 遍历所在桶中的Entry链表，查找其中是否已经有了以Key值为Key存储的Entry对象，​
• 若已存在，定位到对应的Entry,返回value​。若不存在，返回null；

    
    public V get(Object key) {
        if (key == null)
            return getForNullKey();
        int hash = hash(key.hashCode());
        //遍历列表
        for (Entry e = table[indexFor(hash, table.length)];
             e != null;
             e = e.next) {
            Object k;
            if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
                return e.value;
        }
        return null;
    }

HashMap允许Key以null的形式存取，Hashmap会将Key为null组成的Entry放置到table[0],即第一个桶中，在put()和get()操作时，会先对Key 为null的值特殊处理：

    
    private V getForNullKey() {
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null)
                return e.value;
        }
        return null;
    }

    
    private V putForNullKey(V value) {
        for (Entry e = table[0]; e != null; e = e.next) {
            if (e.key == null) {
                V oldValue = e.value;
                e.value = value;
                e.recordAccess(this);
                return oldValue;
            }
        }
        modCount++;
        addEntry(0, null, value, 0);
        return null;
    }

根据key值移除键值对的操作也比较简单，内部关键的流程分为两个：​

• 根据Key的hashcode 值和Key定位到Entry 对象在HashMap中的位置；​
• 由于Entry是一个链表元素，之后便是链表删除节点的操作了;

    
    public V remove(Object key) {
        Entry e = removeEntryForKey(key);
        return (e == null ? null : e.value);
    }
 
    
    final Entry removeEntryForKey(Object key) {
        int hash = (key == null) ? 0 : hash(key.hashCode());
        int i = indexFor(hash, table.length);
        Entry prev = table[i];
        Entry e = prev;
 
        while (e != null) {
            Entry next = e.next;
            Object k;
            if (e.hash == hash &&
                ((k = e.key) == key || (key != null && key.equals(k)))) {
                modCount++;
                size--;
                if (prev == e)
                    table[i] = next;
                else
                    prev.next = next;
                e.recordRemoval(this);
                return e;
            }
            prev = e;
            e = next;
        }
 
        return e;
    }

• HashMap是线程不安全的，如果想使用线程安全的,可以使用Hashtable；它提供的功能和Hashmap基本一致。HashMap实际上是一个Hashtable的轻量级实现；
• 允许以Key为null的形式存储键值对；
• HashMap的查找效率非常高，因为它使用Hash表对进行查找，可直接定位到Key值所在的桶中；
• 使用HashMap时，要注意HashMap容量和加载因子的关系，这将直接影响到HashMap的性能问题。加载因子过小，会提高HashMap的查找效率，但同时也消耗了大量的内存空间，加载因子过大，节省了空间，但是会导致HashMap的查找效率降低。

• golang map 从源码分析实现原理(go 1.14) - 掘金
• 【Golang源码系列】一：Map实现原理分析
• golang map源码分析
• 理解 Golang 哈希表 Map 的原理
• Go 语言 map 解析之 key 的定位核心流程-51CTO.COM
• [Java基础要义] HashMap的设计原理和实现分析_亦山的博客-CSDN博客