go logo
Go,  技术,  编程语言

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的后面形成链表)

精品课程


guest

0 评论
内联反馈
查看所有评论