Go map底层结构实现原理

map结构是一种比较常用的数据结构，存储k/v映射关系集合，根据key能够快速的查找对应的v。

go的map是基于hashtable实现，冲突解决采用拉链法
map 底层实现结构包含hmap和bmap两个，下面详细说一下（注go.1.17.1版本）

[hmap]

// A header for a Go map.
type hmap struct {
	count     int 			  //元素个数
	flags     uint8			  //状态标记
	B         uint8 		  //可存储(loadFactor * 2^B)个元素
	noverflow uint16 		  //溢出buckets的个数
	hash0     uint32 		  //hash种子
	buckets    unsafe.Pointer //count为0时，值为nil，否则是Buckets的开始地址
	oldbuckets unsafe.Pointer //旧桶的地址，扩容使用
	nevacuate  uintptr        //扩容进度，小于nevacuate的，已迁移完成
	extra *mapextra 		  //overflow
}

// mapextra holds fields that are not present on all maps.
type mapextra struct {
	// overflow and oldoverflow are only used if key and elem do not contain pointers.
	// overflow contains overflow buckets for hmap.buckets.
	// oldoverflow contains overflow buckets for hmap.oldbuckets.
	overflow    *[]*bmap
	oldoverflow *[]*bmap
	// nextOverflow holds a pointer to a free overflow bucket.
	nextOverflow *bmap
}

[bmap]

// A bucket for a Go map.
type bmap struct {
	//每个元素的高八位，存储在tophash中
	// 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
	//keys 隐式定义
	//values 隐式定义
	//overflow unsafe.Pointer 隐式定义
}

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

低B位高8位

//key定位公式
k := add(unsafe.Pointer(b), dataOffset+i*uintptr(t.keysize))
//value定位公式
e := add(unsafe.Pointer(b), dataOffset+bucketCnt*uintptr(t.keysize)+i*uintptr(t.elemsize))

// tophash calculates the tophash value for hash.
func tophash(hash uintptr) uint8 {
	top := uint8(hash >> (sys.PtrSize*8 - 8))
	if top < minTopHash {
		top += minTopHash
	}
	return top
}

BB为hmap数据结构中的成员8