go语言扩容方法有:1、Slice扩容,在使用append向Slice追加元素时,如果Slice空间不足,将会触发Slice扩容;2、Map扩容。触发Map扩容的条件有二个:1、负载因子大于6.5时,也即平均每个bucket存储的键值对达到6.5个;2、overflow数量大于2^15时,也即overflow数量超过32768时。
本教程操作环境:windows7系统、GO 1.18版本、Dell G3电脑。
使用append向Slice追加元素时,如果Slice空间不足,将会触发Slice扩容
扩容实际上是重新分配一块更大的内存,将原Slice数据拷贝进新Slice,然后返回新Slice,扩容后再将数据追加进去。
扩容容量的选择遵循以下规则:
// 1.17及以前的版本中 // old指切片的旧容量, cap指期望的新容量 func growslice(old, cap int) int { newcap := old doublecap := newcap + newcap // 如果期望容量大于旧容量的2倍,则直接使用期望容量作为最终容量 if cap > doublecap { newcap = cap } else { // 如果旧容量小于1024,则直接翻倍 if old < 1024 { newcap = doublecap } else { // 每次增长大约1.25倍 for 0 < newcap && newcap < cap { newcap += newcap / 4 } if newcap <= 0 { newcap = cap } } } // 这里忽略了对齐操作 return newcap }
新扩容容量的选择遵循以下规则:(拥有更平滑的扩容系数)
// 只关心扩容规则的简化版growslice func growslice(old, cap int) int { newcap := old doublecap := newcap + newcap if cap > doublecap { newcap = cap } else { const threshold = 256 // 不同点1 if old < threshold { newcap = doublecap } else { for 0 < newcap && newcap < cap { newcap += (newcap + 3*threshold) / 4 // 不同点2 } if newcap <= 0 { newcap = cap } } } return newcap }
触发扩容的条件有二个:
负载因子 > 6.5时,也即平均每个bucket存储的键值对达到6.5个。增量扩容
overflow数量 > 2^15时,也即overflow数量超过32768时。等量扩容/重排
注意:创建溢出桶不属于扩容机制
考虑到如果map存储了数以亿计的key-value,一次性搬迁将会造成比较大的延时,Go采用逐步搬迁策略,即每次访问map时都会触发一次搬迁,每次搬迁2个键值对。当oldbuckets中的键值对全部搬迁完毕后,删除oldbuckets。
下图展示了包含一个bucket满载的map(为了描述方便,图中bucket省略了value区域):
当前map存储了7个键值对,只有1个bucket。此时负载因子为7 > 6.5。再次插入数据时将会触发扩容操作,扩容之后再将新插入键写入新的bucket。注意,因为负载因子的触发,不是创建溢出桶
当第8个键值对插入时,将会触发扩容,扩容后示意图如下:
后续对map的访问操作会触发迁移,将oldbuckets中的键值对逐步的搬迁过来。
搬迁完成后的示意图如下:
数据搬迁过程中原bucket中的键值对将存在于新bucket的前面,新插入的键值对将存在于新bucket的后面。
所谓等量扩容,实际上并不是扩大容量,buckets数量不变,重新做一遍类似增量扩容的搬迁动作,把松散的键值对重新排列一次,以使bucket的使用率更高,进而保证更快的存取。
在极端场景下,比如不断地增删,而键值对正好集中在一小部分的bucket,这样会造成overflow的bucket数量增多,但负载因子又不高,从而无法执行增量搬迁的情况,如下图所示:
上图可见,overflow的bucket中大部分是空的,访问效率会很差。此时进行一次等量扩容,即buckets数量不变,经过重新组织后overflow的bucket数量会减少,即节省了空间又会提高访问效率。
以上是go语言扩容方法有哪几种的详细内容。更多信息请关注PHP中文网其他相关文章!