Go语言各种扩容机制（防止混淆）

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扩容

触发扩容的条件有二个：

1. 负载因子 > 6.5时，也即平均每个bucket存储的键值对达到6.5个。增量扩容
2. 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数量会减少，即节省了空间又会提高访问效率。