Go map底层结构实现原理

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

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

一. map数据结构[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
}

二. bucket数据结构[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
}

整体结构图

图中可以看出，hash函数生成一个64位整数，低B位用于索引bucket的位置，高8位用于索引tophash的key，进而取得value，如果tophash中没找到且overflow非空，则会沿着overflow继续查找，直至遍历所有bucket。

//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
}

1 hash函数生成的是一个整数
2 tophash最多存8个
3 bmap中灰色标识的信息为隐式定义。
4 拉链法解决hash冲突
5 for range 是无序的，很多场景需要顺序输出，需要注意
6 O(1)时间复杂度返回map的元素个数
7 tophash存储高八位是为了快速验证key是否存在
8 插入时，落在当前bucket时，查找位置插入，冲突时，利用overflow指针链接
9 低B（B为hmap数据结构中的成员）位用来定位bucket，高8位用来定位tophash 中的key
10 keys, values分开存储，而不是key=>val，目的是内存对齐