go语言扩容方法有哪几种

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电脑。

Slice扩容

触发

使用append向Slice追加元素时，如果Slice空间不足，将会触发Slice扩容

原理

扩容实际上是重新分配一块更大的内存，将原Slice数据拷贝进新Slice，然后返回新Slice，扩容后再将数据追加进去。

机制

V1.8之前：

扩容容量的选择遵循以下规则：

• 如果原Slice容量小于1024，则新Slice容量将扩大为原来的2倍；
• 如果原Slice容量大于等于1024，则新Slice容量将扩大为原来的1.25倍；

// 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 }

V1.8之后：

新扩容容量的选择遵循以下规则：(拥有更平滑的扩容系数)

• 如果原Slice容量小于256，则新Slice容量将扩大为原来的2倍；
• 如果原Slice容量大于等于256，则新Slice容量将扩大为原来的 新容量 = (原容量+3*256)/4

// 只关心扩容规则的简化版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 }

Map扩容

触发扩容的条件有二个：

• 负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。增量扩容

• overflow数量 > 2^15时，也即overflow数量超过32768时。等量扩容/重排

注意：创建溢出桶不属于扩容机制

增量扩容

• 当负载因子过大时，新开辟buckets空间，bucket数量为之前的 2 倍
• 新空间被buckets引用，之前的旧空间被oldbuckets引用
• 之后逐渐将 oldbuckets中的数据 搬迁到 新开辟的 buckets空间中去

考虑到如果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数量会减少，即节省了空间又会提高访问效率。

【