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
}