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的栈与队列实现代码解析》栈是常见的线性数据结构,栈的特点是以先进后出的形式,后进先出,先进后出,分为栈底和栈顶,栈应用于内存的分配,表达式求值,存储临时的数据和方法的调用等,本文给大家介绍J... 目录栈的概念(Stack)栈的实现代码队列(Queue)模拟实现队列(双链表实现)循环队列(循环数组

C++如何通过Qt反射机制实现数据类序列化

《C++如何通过Qt反射机制实现数据类序列化》在C++工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作,所以本文就来聊聊C++如何通过Qt反射机制实现数据类序列化吧... 目录设计预期设计思路代码实现使用方法在 C++ 工程中经常需要使用数据类,并对数据类进行存储、打印、调试等操作。由于数据类

Python实现图片分割的多种方法总结

《Python实现图片分割的多种方法总结》图片分割是图像处理中的一个重要任务,它的目标是将图像划分为多个区域或者对象,本文为大家整理了一些常用的分割方法,大家可以根据需求自行选择... 目录1. 基于传统图像处理的分割方法(1) 使用固定阈值分割图片(2) 自适应阈值分割(3) 使用图像边缘检测分割(4)

Android实现在线预览office文档的示例详解

《Android实现在线预览office文档的示例详解》在移动端展示在线Office文档(如Word、Excel、PPT)是一项常见需求,这篇文章为大家重点介绍了两种方案的实现方法,希望对大家有一定的... 目录一、项目概述二、相关技术知识三、实现思路3.1 方案一:WebView + Office Onl

C# foreach 循环中获取索引的实现方式

《C#foreach循环中获取索引的实现方式》:本文主要介绍C#foreach循环中获取索引的实现方式,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录一、手动维护索引变量二、LINQ Select + 元组解构三、扩展方法封装索引四、使用 for 循环替代

Spring Security+JWT如何实现前后端分离权限控制

《SpringSecurity+JWT如何实现前后端分离权限控制》本篇将手把手教你用SpringSecurity+JWT搭建一套完整的登录认证与权限控制体系,具有很好的参考价值,希望对大家... 目录Spring Security+JWT实现前后端分离权限控制实战一、为什么要用 JWT?二、JWT 基本结构

Java实现优雅日期处理的方案详解

《Java实现优雅日期处理的方案详解》在我们的日常工作中,需要经常处理各种格式,各种类似的的日期或者时间,下面我们就来看看如何使用java处理这样的日期问题吧,感兴趣的小伙伴可以跟随小编一起学习一下... 目录前言一、日期的坑1.1 日期格式化陷阱1.2 时区转换二、优雅方案的进阶之路2.1 线程安全重构2

Android实现两台手机屏幕共享和远程控制功能

《Android实现两台手机屏幕共享和远程控制功能》在远程协助、在线教学、技术支持等多种场景下,实时获得另一部移动设备的屏幕画面,并对其进行操作,具有极高的应用价值,本项目旨在实现两台Android手... 目录一、项目概述二、相关知识2.1 MediaProjection API2.2 Socket 网络

使用Python实现图像LBP特征提取的操作方法

《使用Python实现图像LBP特征提取的操作方法》LBP特征叫做局部二值模式,常用于纹理特征提取,并在纹理分类中具有较强的区分能力,本文给大家介绍了如何使用Python实现图像LBP特征提取的操作方... 目录一、LBP特征介绍二、LBP特征描述三、一些改进版本的LBP1.圆形LBP算子2.旋转不变的LB

Redis消息队列实现异步秒杀功能

《Redis消息队列实现异步秒杀功能》在高并发场景下,为了提高秒杀业务的性能,可将部分工作交给Redis处理,并通过异步方式执行,Redis提供了多种数据结构来实现消息队列,总结三种,本文详细介绍Re... 目录1 Redis消息队列1.1 List 结构1.2 Pub/Sub 模式1.3 Stream 结