2020-11-25：go中，map的底层数据结构是什么？

福哥答案2020-11-25：

简单回答：hmap映射头、bmap桶、mapextra溢出额外信息

中级回答：

// 映射头
type hmap struct {
    // Note: the format of the hmap is also encoded in cmd/compile/internal/gc/reflect.go.
    // Make sure this stays in sync with the compiler's definition.
    count     int // map的大小.  len()函数就取的这个值
    flags     uint8 // map状态标识
    B         uint8  // B 表示当前哈希表持有的 buckets 数量，但是因为哈希表中桶的数量都 2 的倍数，所以该字段会存储对数，也就是 len(buckets) == 2^B；
    noverflow uint16 // 溢出buckets的数量，表示我们当前有多少个 overflow buckets
    hash0     uint32 // 哈希种子

    buckets    unsafe.Pointer // 指向最大2^B个Buckets数组的指针. count==0时为nil.
    oldbuckets unsafe.Pointer // 指向扩容之前的buckets数组，并且容量是现在一半.不增长就为nil
    nevacuate  uintptr        // 搬迁进度，小于nevacuate的已经搬迁

    extra *mapextra // 可选字段，额外信息
}

// 源码的桶
type bmap struct {
    // tophash generally contains the top byte of the hash value
    // for each key in this bucket. If tophash[0] < minTopHash,
    // tophash[0] is a bucket evacuation state instead.
    tophash [bucketCnt]uint8 //hash高8位
    // Followed by bucketCnt keys and then bucketCnt elems.
    // NOTE: packing all the keys together and then all the elems together makes the
    // code a bit more complicated than alternating key/elem/key/elem/... but it allows
    // us to eliminate padding which would be needed for, e.g., map[int64]int8.
    // Followed by an overflow pointer.
}

//编译后的桶
type bmap struct {
    topbits  [8]uint8 //hash高8位
    keys     [8]keytype //键
    values   [8]valuetype //值
    pad      uintptr
    overflow uintptr // 指针，溢出桶
}

//溢出额外信息
type mapextra struct {
    // 如果 key 和 value 都不包含指针，并且可以被 inline(<=128 字节)
    // 使用 extra 来存储 overflow bucket，这样可以避免 GC 扫描整个 map
    // 然而 bmap.overflow 也是个指针。这时候我们只能把这些 overflow 的指针
    // 都放在 hmap.extra.overflow 和 hmap.extra.oldoverflow 中了
    // overflow 包含的是 hmap.buckets 的 overflow 的 bucket
    // oldoverflow 包含扩容时的 hmap.oldbuckets 的 overflow 的 bucket
    overflow       *[]*bmap
    oldoverflow    *[]*bmap

    // 指向空闲的 overflow bucket 的指针
    nextOverflow *bmap
}