golang map的底层实现

golang map的底层实现

粗略的讲,Go语言中map采用的是哈希查找表,由一个key通过哈希函数得到哈希值,64位系统中就生成一个64bit的哈希值,由这个哈希值将key对应到不同的桶(bucket)中,当有多个哈希映射到相同的的桶中时,使用链表解决哈希冲突。

hash函数

首先要知道的就是map中哈希函数的作用,go中map使用hash作查找,就是将key作哈希运算,得到一个哈希值,根据哈希值确定key-value落在哪个bucket的哪个cell。golang使用的hash算法和CPU有关,如果cpu支持aes,那么使用aes hash,否则使用memhash。

数据结构

hmap可以理解为 header of map的缩写,即map数据结构的入口。

type hmap struct {
 // map 中的元素个数,必须放在 struct 的第一个位置,因为 内置的 len 函数会从这里读取
 count int 
 // map状态标识,比如是否在被写或者迁移等,因为map不是线程安全的所以操作时需要判断flags
 flags uint8
 // log_2 of buckets (最多可以放 loadFactor * 2^B 个元素即6.5*2^B,再多就要 hashGrow 了)
 B uint8 
 // overflow 的 bucket 的近似数
 noverflow uint16 
 // hash seed,随机哈希种子可以防止哈希碰撞攻击
 hash0 uint32
 
 // 存储数据的buckets数组的指针, 大小2^B,如果 count == 0 的话,可能是 nil
 buckets unsafe.Pointer
 // 一半大小的之前的 bucket 数组,只有在 growing 过程中是非 nil
 oldbuckets unsafe.Pointer
 // 扩容进度标志,小于此地址的buckets已迁移完成。
 nevacuate uintptr
 // 可以减少GC扫描,当 key 和 value 都可以 inline 的时候,就会用这个字段
 extra *mapextra // optional fields
}

用mapextra来存储key和value都不是指针类型的map,并且大小都小于128字节,这样可以避免GC扫描整个map。

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
}

bmap可以理解为buckets of map的缩写,它就是map中bucket的本体,即存key和value数据的"桶"。

type bmap struct {
 // tophash 是 hash 值的高 8 位
 tophash [bucketCnt]uint8
 // 以下字段没有显示定义在bmap,但是编译时编译器会自动添加
 // keys // 每个桶最多可以装8个key
 // values // 8个key分别有8个value一一对应
 // overflow pointer // 发生哈希碰撞之后创建的overflow bucket
}

根据哈希函数将key生成一个哈希值,其中低位哈希用来判断桶位置,高位哈希用来确定在桶中哪个cell。低位哈希就是哈希值的低B位,hmap结构体中的B,比如B为5,2^5=32,即该map有32个桶,只需要取哈希值的低5位就可以确定当前key-value落在哪个桶(bucket)中;高位哈希即tophash,是指哈希值的高8bits,根据tophash来确定key在桶中的位置。每个桶可以存储8对key-value,存储结构不是key/value/key/value...,而是key/key..value/value,这样可以避免字节对齐时的padding,节省内存空间。

当不同的key根据哈希得到的tophash和低位hash都一样,发生哈希碰撞,这个时候就体现overflow pointer字段的作用了。桶溢出时,就需要把key-value对存储在overflow bucket(溢出桶),overflow pointer就是指向overflow bucket的指针。如果overflow bucket也溢出了呢?那就再给overflow bucket新建一个overflow bucket,用指针串起来就形成了链式结构,map本身有2^B个bucket,只有当发生哈希碰撞后才会在bucket后链式增加overflow bucket。

map内存布局

扩容

1. 装填因子是否大于6.5
   装填因子 = 元素个数/桶个数,大于6.5时,说明桶快要装满,需要扩容

2. overflow bucket是否太多
   ​当bucket的数量 < 2^15,但overflow bucket的数量大于桶数量
   ​当bucket的数量 >= 2^15,但overflow bucket的数量大于2^15

双倍扩容:装载因子多大,直接翻倍,B+1;扩容也不是申请一块内存,立马开始拷贝,每一次访问旧的buckets时,就迁移一部分,直到完成,旧bucket被GC回收。

等量扩容:重新排列,极端情况下,重新排列也解决不了,map成了链表,性能大大降低,此时哈希种子hash0的设置,可以降低此类极端场景的发生。

查找

1. 根据key计算出哈希值
2. 根据哈希值低位确定所在bucket
3. 根据哈希值高8位确定在bucket中的存储位置
4. 当前bucket未找到则查找对应的overflow bucket。
5. 对应位置有数据则对比完整的哈希值,确定是否是要查找的数据
6. 如果当前处于map进行了扩容,处于数据搬移状态,则优先从oldbuckets查找。

插入

1. 根据key计算出哈希值
2. 根据哈希值低位确定所在bucket
3. 根据哈希值高8位确定在bucket中的存储位置
4. 查找该key是否存在,已存在则更新,不存在则插入

map无序

map的本质是散列表,而map的增长扩容会导致重新进行散列,这就可能使map的遍历结果在扩容前后变得不可靠,Go设计者为了让大家不依赖遍历的顺序,故意在实现map遍历时加入了随机数,让每次遍历的起点--即起始bucket的位置不一样,即不让遍历都从bucket0开始,所以即使未扩容时我们遍历出来的map也总是无序的。

参考资料

[1] Golang map底层实现
[2] Go语言之map:map的用法到map底层实现分析
[3] Go语言map底层浅析
[4] 哈希表

本文来自:简书

感谢作者:昔召阆梦

查看原文:golang map的底层实现

• 编辑
• 预览