Golang底层原理剖析之map

简介: Golang底层原理剖析之map

前言

关于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的旧桶依然会迁移到同样编号的新桶中,同样数目的键值对迁移到新桶中,能够排列的更加紧凑,从而减少溢出桶的使用,这就是等量扩容的意义所在。



目录
相关文章
|
12天前
|
存储 安全 测试技术
GoLang协程Goroutiney原理与GMP模型详解
本文详细介绍了Go语言中的Goroutine及其背后的GMP模型。Goroutine是Go语言中的一种轻量级线程,由Go运行时管理,支持高效的并发编程。文章讲解了Goroutine的创建、调度、上下文切换和栈管理等核心机制,并通过示例代码展示了如何使用Goroutine。GMP模型(Goroutine、Processor、Machine)是Go运行时调度Goroutine的基础,通过合理的调度策略,实现了高并发和高性能的程序执行。
75 29
|
10天前
|
负载均衡 算法 Go
GoLang协程Goroutiney原理与GMP模型详解
【11月更文挑战第4天】Goroutine 是 Go 语言中的轻量级线程,由 Go 运行时管理,创建和销毁开销小,适合高并发场景。其调度采用非抢占式和协作式多任务处理结合的方式。GMP 模型包括 G(Goroutine)、M(系统线程)和 P(逻辑处理器),通过工作窃取算法实现负载均衡,确保高效利用系统资源。
|
2月前
|
Go
Golang语言之映射(map)快速入门篇
这篇文章是关于Go语言中映射(map)的快速入门教程,涵盖了map的定义、创建方式、基本操作如增删改查、遍历、嵌套map的使用以及相关练习题。
36 5
|
3月前
|
算法 NoSQL 关系型数据库
熔断原理与实现Golang版
熔断原理与实现Golang版
|
3月前
|
存储 关系型数据库 Go
SOLID原理:用Golang的例子来解释
SOLID原理:用Golang的例子来解释
|
3月前
|
Java Serverless Go
Golang 开发函数计算问题之在 Golang 中避免 "concurrent map writes" 异常如何解决
Golang 开发函数计算问题之在 Golang 中避免 "concurrent map writes" 异常如何解决
|
3月前
|
存储 人工智能 Go
golang 反射基本原理及用法
golang 反射基本原理及用法
28 0
|
5月前
|
Go
GOLANG MAP 查找
GOLANG MAP 查找
|
5月前
|
存储 Go 索引
GOLANG MAP 底层实现
GOLANG MAP 底层实现
|
6月前
|
存储 缓存 安全
Golang深入浅出之-Go语言中的并发安全容器:sync.Map与sync.Pool
Go语言中的`sync.Map`和`sync.Pool`是并发安全的容器。`sync.Map`提供并发安全的键值对存储,适合快速读取和少写入的情况。注意不要直接遍历Map,应使用`Range`方法。`sync.Pool`是对象池,用于缓存可重用对象,减少内存分配。使用时需注意对象生命周期管理和容量控制。在多goroutine环境下,这两个容器能提高性能和稳定性,但需根据场景谨慎使用,避免不当操作导致的问题。
192 7