本文主要是介绍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缩容的实现的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!