Golang中map缩容的实现

2025-03-04 17:50
文章标签 golang map 缩容 实现

本文主要是介绍Golang中map缩容的实现,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

《Golang中map缩容的实现》本文主要介绍了Go语言中map的扩缩容机制,包括grow和hashGrow方法的处理,具有一定的参考价值,感兴趣的可以了解一下...

基本分析

在 Go 底层源码 src/runtime/map.go 中,扩缩容的处理方法是 grow 为前缀的方法来处理的。

其中扩缩容涉及到的是插入元素的操作,对应 mapassign 方法:

func mapassign(t *maptype, h *hmap, key unsafe.Pointer) unsafe.Pointer {
  ...
 if !h.growing() && (overLoadFactor(h.count+1, h.B) || tooManyOverflowBuckets(h.noverflow, h.B)) {
  hashGrow(t, h)
  goto again
 }
  ...
}
func (h *hmap) growing() bool {
 return h.oldbuckets != nil
}
func overLChina编程oadFactor(count int, B uint8) bool {
 return count > bucketCnt && uintptr(count) > loadFactorNum*(bucketShift(B)/loadFactorDen)
}
func tooManyOverflowBuckets(noverflow uint16, B uint8) bool {
 if B > 15 {
  B = 15
 }
 China编程return noverflow >= uint16(1)<<(B&15)
} 

核心看到针对扩缩容的判断逻辑:

当前没有在扩容:条件为 oldbuckets 不为 nil。

是否可以进行扩容:条件为 hmap.count> hash 桶数量 (2^B)*6.5。其中 hmap.count 指的是map 的数据数目, 2^B 仅指 hash 数组的大小,不包含溢出桶。

是否可以进行缩容:条件为溢出桶(noverflowChina编程)的数量 >= 32768(China编程1<<15)。

可以关注到,无论是扩容还是缩容,其都是由 hashGrow 方法进行处理:

 func hashGrow(t *maptype, h *hmap) {
 bigger := uint8(1)
 if !overLoadFactor(h.count+1, h.B) {
  bigger = 0
  h.flags |= sameSizeGrow
 }
  ...
}

若是扩容,则 bigger 为 1,也就是 B+1。代表 hash 表容量扩大 1 倍。不满足就是缩容,也就是 hash 表容量不变。

可以得出结论:map 的扩缩容的主要区别在于 hmap.B 的容量大小改变。而缩容由于 hmap.B 压根没变,内存空间的占用也是没有变化的。

带来的隐患

这种方式其实是存在运行隐患的,也就是导致在删除元素时,并不会释放内存,使得分配的总内存不断增加。如果一个不小心,拿 map 来做大 key/value 的存储,也不注意管理,很容易就内存爆了。

也就是 Go 语言的 map 目前实现的是 “伪缩容”,仅针对溢出桶过多的情况。若是触发缩容,hash 数组的占用的内存大小不变(等量扩容)。

若要实现 ”真缩容“,Go Contributor @josharian 表示目前唯一可用的解决方法是:创建一个新的 map 并从旧的 map 中复制元素。

示例如下:

old := make(map[int]int, 9999999)
new := make(map[int]int, len(old))
for k, v := range old {
    new[k] = v
}
old = new
...

为什么不支持缩容

下述内容会主要基于如下两个 issues 和 proposal 来分析:

《runtime: shrink map as elements are deleted[1]》php
《proposal: runtime: add way to clear and reuse a map's working storage[2]》

目前 map 的缩容处理起来比较棘手,最早的 issues 是 2016 年提出的,也有人提过一些提案,但都因为种种原因被拒绝了。

简单来讲,就是没有找到一个很好的方法实现,存在明确的实现成本问题,没办法很方便的 ”告诉“ Go 运行时,我要:

  • 记得保留存储空间,我要立即重用 map。
  • 赶紧释放存储空间,map 从现在开始会小很多。

抽象来看症结是:需要保证增长结果在下一个开始之前完成,此处的增长指的是 ”从小到大,从一个大小到相同大小,从大到小“ 的复杂过程。

这属于一个多重 case,从而导致也就一直拖着,慢慢想。

到此这篇关于golang中map缩容的实现的文章就介绍到这了,更多相关Golang map缩容 内容请搜索编程China编程(www.chinasem.cn)以前的文章或继续浏览下面的相关文章希望大家以后多多支持China编程(www.chinasem.cn)!

这篇关于Golang中map缩容的实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1153637

相关文章

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

opencv图像处理之指纹验证的实现

《opencv图像处理之指纹验证的实现》本文主要介绍了opencv图像处理之指纹验证的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学... 目录一、简介二、具体案例实现1. 图像显示函数2. 指纹验证函数3. 主函数4、运行结果三、总结一、

Springboot处理跨域的实现方式(附Demo)

《Springboot处理跨域的实现方式(附Demo)》:本文主要介绍Springboot处理跨域的实现方式(附Demo),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不... 目录Springboot处理跨域的方式1. 基本知识2. @CrossOrigin3. 全局跨域设置4.

Spring Boot 3.4.3 基于 Spring WebFlux 实现 SSE 功能(代码示例)

《SpringBoot3.4.3基于SpringWebFlux实现SSE功能(代码示例)》SpringBoot3.4.3结合SpringWebFlux实现SSE功能,为实时数据推送提供... 目录1. SSE 简介1.1 什么是 SSE?1.2 SSE 的优点1.3 适用场景2. Spring WebFlu

基于SpringBoot实现文件秒传功能

《基于SpringBoot实现文件秒传功能》在开发Web应用时,文件上传是一个常见需求,然而,当用户需要上传大文件或相同文件多次时,会造成带宽浪费和服务器存储冗余,此时可以使用文件秒传技术通过识别重复... 目录前言文件秒传原理代码实现1. 创建项目基础结构2. 创建上传存储代码3. 创建Result类4.

SpringBoot日志配置SLF4J和Logback的方法实现

《SpringBoot日志配置SLF4J和Logback的方法实现》日志记录是不可或缺的一部分,本文主要介绍了SpringBoot日志配置SLF4J和Logback的方法实现,文中通过示例代码介绍的非... 目录一、前言二、案例一:初识日志三、案例二:使用Lombok输出日志四、案例三:配置Logback一

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

Python+PyQt5实现多屏幕协同播放功能

《Python+PyQt5实现多屏幕协同播放功能》在现代会议展示、数字广告、展览展示等场景中,多屏幕协同播放已成为刚需,下面我们就来看看如何利用Python和PyQt5开发一套功能强大的跨屏播控系统吧... 目录一、项目概述:突破传统播放限制二、核心技术解析2.1 多屏管理机制2.2 播放引擎设计2.3 专

Python实现无痛修改第三方库源码的方法详解

《Python实现无痛修改第三方库源码的方法详解》很多时候,我们下载的第三方库是不会有需求不满足的情况,但也有极少的情况,第三方库没有兼顾到需求,本文将介绍几个修改源码的操作,大家可以根据需求进行选择... 目录需求不符合模拟示例 1. 修改源文件2. 继承修改3. 猴子补丁4. 追踪局部变量需求不符合很

golang 日志log与logrus示例详解

《golang日志log与logrus示例详解》log是Go语言标准库中一个简单的日志库,本文给大家介绍golang日志log与logrus示例详解,感兴趣的朋友一起看看吧... 目录一、Go 标准库 log 详解1. 功能特点2. 常用函数3. 示例代码4. 优势和局限二、第三方库 logrus 详解1.