由浅到深，入门Go语言Map实现原理

                  key
                   |
                   v                 
+------------------------------------+
|      key通过hash函数得到key的hash    |
+------------------+-----------------+
                   |
                   v
+------------------------------------+
|       key的hash通过取模或者位操作     |
|          得到key在数组上的索引        |
+------------------------------------+
                   |
                   v
+------------------------------------+
|         通过索引找到对应的链表         |
+------------------+-----------------+
                   |
                   v
+------------------------------------+
|       遍历链表对比key和目标key        |
+------------------+-----------------+
                   |
                   v
+------------------------------------+
|              相等则返回value         |
+------------------+-----------------+
                   |
                   v                
                 value 

备注：后面我们会解释上面为啥用的“主要”两个字。

// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.go
type hmap struct {
    count     int 
    flags     uint8
    B         uint8 
    noverflow uint16 
    hash0     uint32
    buckets    unsafe.Pointer
    oldbuckets unsafe.Pointer
    nevacuate  uintptr 
    extra *mapextra
}

// https://github.com/golang/go/blob/go1.13.8/src/cmd/compile/internal/gc/reflect.go
func bmap(t *types.Type) *types.Type {
  // 略...

  field := make([]*types.Field, 0, 5)

    field = append(field, makefield("topbits", arr))

  // 略...
  
    keys := makefield("keys", arr)
    field = append(field, keys)

  // 略...
  
    elems := makefield("elems", arr)
    field = append(field, elems)

  // 略...
  
    if int(elemtype.Align) > Widthptr || int(keytype.Align) > Widthptr {
        field = append(field, makefield("pad", types.Types[TUINTPTR]))
    }

  // 略...
  
    overflow := makefield("overflow", otyp)
    field = append(field, overflow)

  // 略...
}

// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.go
type mapextra struct {
    overflow    *[]*bmap
    oldoverflow *[]*bmap
    nextOverflow *bmap
}

// https://github.com/golang/go/blob/go1.13.8/src/runtime/map.go
func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  // 略
again:
    // 略...
    var inserti *uint8
  // 略...
bucketloop:
    for {
        for i := uintptr(0); i < bucketCnt; i++ {
      // key的hash高8位不相等
            if b.tophash[i] != top {
        // 当前位置bmap.tophash的元素为空且还没有写入的记录(inserti已经写入的标记为)
                if isEmpty(b.tophash[i]) && inserti == nil {
          // inserti赋值为当前的hash高8位 标记写入成功
                    inserti = &b.tophash[i]
                    // 略...
                }
                // 略...
                continue
            }
            // 略...
            goto done
    }
    // 正常桶的bmap遍历完了 继续遍历溢出桶的bmap 如果有的话
        ovf := b.overflow(t)
        if ovf == nil {
            break
    }
        b = ovf
    }

  // 略...

  // 没写入成功(包含正常桶的bmap、溢出桶的bmap(如果有的话))
    if inserti == nil {
    // 分配新的bmap写
    newb := h.newoverflow(t, b)
    // 略...
    }

    // 略...
}

// 继续看h.newoverflow的代码
func (h *hmap) newoverflow(t *maptype, b *bmap) *bmap {
  var ovf *bmap
  // 如果hmap的存在溢出桶 且 溢出桶还没用完
    if h.extra != nil && h.extra.nextOverflow != nil {
    // 使用溢出桶的bmap
    ovf = h.extra.nextOverflow
    // 判断桶的bmap的overflow是不是空
    // 这里很巧妙。为啥？
    // 溢出桶初始化的时候会把最后一个bmap的overflow指向正常桶，值不为nil
    // 目的判断当前这个bmap是不是溢出桶里的最后一个
        if ovf.overflow(t) == nil {
      // 是nil
      // 说明不是最后一个
            h.extra.nextOverflow = (*bmap)(add(unsafe.Pointer(ovf), uintptr(t.bucketsize)))
        } else {
      // 不是nil
      // 则重置当前bmap的overflow为空
      ovf.setoverflow(t, nil)
      // 且 标记nextOverflow为nil 说明当前溢出桶用完了
            h.extra.nextOverflow = nil
        }
    } else {
    // 没有溢出桶 或者 溢出桶用完了
    // 内存空间重新分配一个bmap
        ovf = (*bmap)(newobject(t.bucket))
  }
  // 生成溢出桶bmap的计数器计数
    h.incrnoverflow()
  // 略...
  // 这行代码就是上面问题我们要的答案:
  // 正常桶`hmap.buckets`里的`bmap`在这里关联上溢出桶`hmap.extra.overflow`的`bmap`
    b.setoverflow(t, ovf)
    return ovf
}

// setoverflow函数的源码
func (b *bmap) setoverflow(t *maptype, ovf *bmap) {
  // 这行代码的意思：通过偏移量计算找到了bmap.overflow，并把ovf这个bmap的地址赋值给了bmap.overflow
    *(**bmap)(add(unsafe.Pointer(b), uintptr(t.bucketsize)-sys.PtrSize)) = ovf
}

func mapaccess1(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
    // ...略
    
    // ①通过hash函数获取当前key的哈希
    hash := alg.hash(key, uintptr(h.hash0))
    m := bucketMask(h.B)
    // ②通过当前key的哈希获取到对应的bmap结构的b
    // 这里的b 我们称之为“正常桶的bmap”
    // “正常桶的bmap”可能会对应到溢出桶的bmap结构，我们称之为“溢出桶的bmap”
    b := (*bmap)(add(h.buckets, (hash&m)*uintptr(t.bucketsize)))
    
    // ...略
    
    // 获取当前key的哈希的高8位
    top := tophash(hash)
bucketloop:
    // 下面的for循环是个简写，完整如下。
    // for b = b; b != nil; b = b.overflow(t) {
    // 可以知道b的初始值为上面的“正常桶的bmap”，则：
    // 第一次遍历：遍历的是“正常桶的bmap”
    // 如果正常桶没找到，则
    // 绿色线条④ 继续遍历：如果当前“正常桶的bmap”中的overflow值不为nil(说明“正常桶的bmap”关联了“溢出桶的bmap”)，则遍历当前指向的“溢出桶的bmap”继续 蓝色线条的③④⑤步骤
    for ; b != nil; b = b.overflow(t) {
        // 由于b的初始值为“正常桶的bmap”，第一次先遍历“正常桶的bmap”
        for i := uintptr(0); i < bucketCnt; i++ {
            // 蓝色线条③ 对比key哈希的高8位
            // 对比哈希的高8位目的是为了加速
            if b.tophash[i] != top {
                // emptyRest 标志位：表示当前位置已经是末尾了；删除操作会设置此标志位
                if b.tophash[i] == emptyRest {
                    break bucketloop
                }
                continue
            }
            // 找到了相同的hash高8位，则：找到对应索引位置i的key
            k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
            if t.indirectkey() {
                k = *((*unsafe.Pointer)(k))
            }
            // 蓝色线条④ 对比key是不是一致
            if alg.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 e
            }
        }
    }
    // 正常桶、溢出桶都没找到则返回 “空值”
    return unsafe.Pointer(&zeroVal[0])
}

参考：
1.《Go语言设计与实现》https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-hashmap/
2. Go源码版本1.13.8 https://github.com/golang/go/tree/go1.13.8/src