Go语言切片和Map扩容机制详解

Go语言切片和Map扩容机制详解Go语言中的切片Slice和Map是开发中使用频率最高的数据结构之一但是很多开发者只知道如何使用却不了解它们背后的扩容机制。本文将从底层结构出发详细分析 Go Slice 和 Map 的扩容原理帮助大家理解 Go 为什么能够高效管理动态数据。一、Go切片Slice的底层结构在 Go 中切片并不是一个真正存储数据的数组而是一个数组的引用描述结构。切片底层结构定义在runtime/slice.go中type slice struct { array unsafe.Pointer // 指向底层数组 len int // 当前元素数量 cap int // 底层数组容量 }一个切片包含三个重要字段字段含义array指向底层数组的指针len当前切片长度cap底层数组容量例如packagemainimportfmtfuncmain(){nums:[]int{1,2,3}fmt.Println(len(nums))fmt.Println(cap(nums))}输出3 3说明len 3 cap 3底层结构slice ------- | ptr | ------- [1][2][3] ------- | len 3 | ------- | cap 3 | -------二、为什么切片需要扩容假设nums:[]int{1,2,3}此时len3 cap3如果继续添加numsappend(nums,4)问题来了原来的数组已经没有空间[1][2][3] ^ 满了Go无法直接添加新的元素。因此需要创建一个更大的数组将旧数组的数据复制过去修改slice指针添加新元素过程旧数组: [1][2][3] 扩容后: [1][2][3][ ][ ][ ] ↑ 新空间三、append触发扩容过程例如funcmain(){nums:[]int{}fori:0;i10;i{numsappend(nums,i)fmt.Println(len(nums),cap(nums),)}}输出类似1 1 2 2 3 4 4 4 5 8 6 8 7 8 8 8 9 16 10 16可以发现容量不断增长1 2 4 8 16这就是切片扩容。四、Go切片扩容规则Go1.18之后切片扩容主要分为两个阶段。1. 小容量切片当oldCap 256扩容策略newCap oldCap * 2例如cap4 扩容 4 × 2 82. 大容量切片当oldCap 256不会继续简单翻倍。原因如果容量已经很大100000直接200000会造成大量内存浪费。因此 Go 使用平滑增长源码newcap(newcap3*threshold)2其中threshold 256表示右移例如8 1等价于8 / 2所以x 2等价x / 4公式newcap newcap (newcap3*256)/4随着容量增加增长比例逐渐下降旧容量增长比例256附近接近2倍1024约1.6倍更大约1.25倍这样可以减少大切片扩容带来的内存浪费。五、切片扩容源码流程append执行append(slice,value)实际上会进入runtime.growslice()核心流程append | | 检查容量 | | cap不足 | | growslice() | | 计算新容量 | | mallocgc分配新数组 | | memmove复制数据 | | 返回新的slice六、扩容后为什么地址会改变代码packagemainimportfmtfuncmain(){nums:[]int{1,2,3}fmt.Printf(%p\n,nums[0])numsappend(nums,4,5,6,7)fmt.Printf(%p\n,nums[0])}输出0xc0000120c0 0xc000020180地址不同。原因扩容重新申请了新的数组旧数组: 0xc0000120c0 [1][2][3] 新数组: 0xc000020180 [1][2][3][4][5][6][7]七、Go Map底层结构Go中的map底层是hash表 bucket数组源码typehmapstruct{countintBuint8buckets unsafe.Pointer oldbuckets unsafe.Pointer}主要字段字段作用count元素数量B桶数量指数buckets当前桶oldbuckets扩容旧桶八、Map为什么需要扩容例如m:make(map[int]int)fori:0;i100;i{m[i]i}不断插入数据bucket1 bucket2 bucket3 ...如果元素越来越多查询效率下降 hash冲突增加所以需要增加bucket数量。九、Map扩容条件Go Map扩容主要有两个条件。条件1负载因子过高负载因子loadFactor 元素数量 / bucket数量Go默认loadFactor 6.5触发扩容。例如bucket数量8 最大元素: 8×6.5≈52超过52开始扩容。条件2overflow bucket过多如果大量key产生hash冲突bucket: [1][2][3][4] | overflow | [5][6]即使元素数量没有达到限制也会触发扩容。目的减少冲突提高查询效率。十、Map扩容方式渐进式扩容很多语言扩容一次性复制全部数据例如旧Hash表 100万个数据 ↓ 新Hash表 复制100万个但是 Go Map 不这样。Go采用渐进式扩容扩容时old bucket B0 B1 B2 B3 new bucket B0 B1 B2 B3 B4 B5 B6 B7不会立即复制全部数据。而是在每次map操作中迁移一部分。例如m[key]value执行检查是否扩容 ↓ 迁移旧bucket ↓ 执行插入这样避免一次扩容造成长时间停顿。十一、Map扩容大小变化假设原来B3代表2^38个bucket扩容B4变成2^416个bucket容量扩大2倍十二、Slice和Map扩容区别SliceMap底层结构数组哈希表扩容原因容量不足负载过高扩容方式重新申请数组增加bucket数据迁移一次完成渐进迁移扩容倍数约2倍→1.25倍2倍触发方式append插入数据十三、开发中的注意事项1. 提前指定Slice容量不要varnums[]intfori:0;i100000;i{numsappend(nums,i)}因为不断扩容1 2 4 8 16 ...推荐nums:make([]int,0,100000)减少内存申请数据复制2. Map提前初始化错误varmmap[string]intm[name]1会panic正确m:make(map[string]int)如果知道容量m:make(map[string]int,10000)十四、总结Go中的Slice和Map虽然使用简单但是底层隐藏了复杂的扩容机制。Slice底层是数组append超过容量触发扩容小容量翻倍增长大容量平滑增长扩容会重新分配数组Map底层是哈希表根据负载因子触发扩容bucket数量翻倍使用渐进式迁移避免阻塞理解扩容机制可以帮助我们写出更高性能Go代码减少不必要的内存分配更深入理解Go运行时原理参考资料Go Runtime源码runtime/slice.goGo Runtime源码runtime/map.goGo官方文档