前言
关于map的使用与map的陷阱,请点击这篇博文浅谈Golang map使用与陷阱
名词理解
负载因子
存储的键值对的数目与桶的数目的比值陈为负载因子。
渐进式扩容
如果哈希表存储的键值对较多,一次性迁移所有桶花费的时间就比较久,所以通常在哈希表扩容时,先分配足够多的新桶,然后用一个字段记录旧桶的位置,一个字段记录旧桶迁移的进度,在哈希表每次读写操作时,如果检测到当前处于扩容阶段,就完成一部分键值对迁移任务,直接所有旧桶迁移完成,旧桶不再使用,才算真正完成一次哈希表的扩容,像这样把键值对迁移的时间分摊到多次哈希表操作中的方式,就是渐进式扩容,可以避免一次性扩容带来的性能瞬时抖动。
hmap
Go语言中map类型的底层实现就是哈希表,map类型的变量本质是是一个指针,指向hmap结构体。
- cout记录键值对的数目
- B记录桶的数目是2的多少次幂
- noverflow记录使用的溢出桶的数量
- buckets记录桶在哪
- oldbuckets用于扩容阶段记录旧桶在哪
- nevacuate记录渐进式扩容阶段下一个要要迁移的旧桶编号
bmap
map使用的桶就是bmap,一个桶里可以放8个键值对,但是为了让内存排列更加紧凑,8个key放一起,8个value放一起,8个key的前面则是8个tophash,每个tophash都是对应哈希值的高8位。最后这里是一个bmap型指针,指向一个溢出桶overflow,溢出桶的内存布局与常规桶相同,是为了减少扩容次数而引入的,当一个桶存满了,还有空用的溢出桶时,就会在桶后面链一个溢出桶,继续往这里面存。
实际上如果哈希表要分配的桶的数目大于2的4次(16)就认为使用到溢出桶的几率较大,就会预分配2的(B-4)个溢出桶备用,这些溢出桶与常规同在内存中是连续的,只是前面2的B次个用做常规桶, 后面的用做溢出桶。
hmap结构体最后有一个extra字段,指向一个mapextra结构体,里面记录的都是溢出桶相关的信息
- overflow是一个slice,记录目前已经使用的溢出桶的地址
- oldoverfolw也是一个slice,用于在扩容阶段存储旧桶用到的那些溢出桶的地址
- nextoverflow指向下一个空闲溢出桶
扩容规则
翻倍扩容
变量a本质上是一个hmap的指针,目前存储了一个键值对,只有一个桶,也没有预分配的溢出桶。下面把唯一的这个桶展开来看一下,目前这个map就长这样。
如果我们把这个桶存满,接下来再继续存储新的键值对时,这个哈希表是会创建溢出桶,还是谁发生扩容呢?
这就要看map的扩容规则了,Go语言中map的默认负载因子是6.5,超过这个数就会触发翻倍扩容。
buckets指向新分配的两个桶,oldbuckets指向旧桶,nevacuate=0,表示接下来要迁移编号为0的旧桶
每个旧桶的键值对都会分流到两个新桶中,例如如果旧桶数量为4,新桶就是8.如果一个哈希值选择0号旧桶,那么哈希值的二进制低两位一定为0,所以选择新桶的结果只有两种,取决于哈希值的第三位是0还是1,如果第三位是0,则选择编号为0的新桶,如果是1,则会选择编号为4的新桶。
因为桶的数量一定是2的整数次幂,所以无论容量是多少,翻倍扩容后,每个旧桶都会按照这样的规律分流到两个新桶中。
等量扩容
如果负载因子没有超标,但是使用的溢出桶很多,也会触发扩容。不过这一次是等量扩容。如果常规桶数目不大于215,那么使用溢出桶数目超过常规同就算是多了。如果常规桶数目大于215,那么使用溢出桶数目一旦超过2^15就算是多了。
所谓等量扩容,就是创建和旧桶数目一样多的新桶,然后把原来的键值对迁移到新桶中,但是既然等量,迁移来迁移去有什么用?那我们就要想想什么情况下,桶的负载因子没有超过上限值,却偏偏使用了很多溢出桶呢?自然是由很多键值对被删除的情况, 就像这里编号为0的情况。
如果此时满足等量扩容的触发条件,就会分配等量的新桶,编号为0的旧桶依然会迁移到同样编号的新桶中,同样数目的键值对迁移到新桶中,能够排列的更加紧凑,从而减少溢出桶的使用,这就是等量扩容的意义所在。