map底层详解 – golang

Go语言的map使用Hash表作为底层实现，一个Hash表中可以有多个bucket, 而每个bucket保存了map中的一组或多组键值对。

Hash函数

选择hash函数，主要考察的是两点: 性能、碰撞概率。golang会根据硬件选择hash算法，如果cpu支持aes，则使用aes hash, 否则使用memhash。

哈希函数会将传入的key值进行哈希运算，得到一个唯一的值。go语言把生成的哈希值一分为二，比如一个key经过哈希函数，生成的哈希值为：8423452987653321，go语言会这它拆分为84234529，和87653321。那么，前半部分就叫做高位哈希值，后半部分就叫做低位哈希值。

底层数据结构

map的底层数据结构

type hmap struct {
	count     int // 当前保存的元素个数
	flags     uint8 // map状态标识
	B         uint8  // bucket数组的大小，2^B=len(buckets)。可以最多容纳 6.5 * 2 ^ B 个元素，6.5为装载因子即:map长度=6.5*2^B
	noverflow uint16 // 溢出桶里bmap大致的数量，B<16时为精确值，否则为近似值；
	hash0     uint32 // hash 种子
	buckets    unsafe.Pointer // 指向一个数组(连续内存空间)，数组的类型为[]bmap，这个字段我们可以称之为正常桶
	oldbuckets unsafe.Pointer // 老bucket数组，用于扩容
	nevacuate  uintptr        // 搬迁进度，小于nevacuate的已经搬迁

	extra *mapextra // 溢出桶结构，正常桶里面某个bmap存满了，会使用这里面的内存空间存放键值对
}

bucket的底层数据结构

type bmap struct {
	tophash [bucketCnt]uint8 // bucketCnt = 8
}

bucket的底层数据结构(逻辑底层)

type bmap struct {
	tophash [bucketCnt]uint8 // bucketCnt = 8
        data []byte // key value 数据 key0/key1/key2/.../value1/value2/value3...
        overflow *bmap // 溢出bucket的地址
}

每个bucket可以存储8个键值对

• tophash是一个长度为8的整型数组，Hash值相同的键(准确的说是Hash值低位相同的键)存入当前bucket时，会将Hash值的高位存储在该数组中，便于后续查找匹配
• data区存放的是key-value数据，存放顺序是: key0/key1/key2/…/value1/value2/value3…，如此存放，是为了节省字节对齐带来的空间浪费。(如图所示，蓝色为高位，红色为低位)

• overflow指针指向下一个bmap，将所有有冲突的键链接起来(由于每个bmap可以存放8个键值对，当超过是，就会申请一个新的bmap（overflow bucket）挂在这个bmap的后面形成链表)