首页问答社区其他问答正文

go语言扩容方法有哪些

2023-02-08 22:45:06 4 0

go语言扩容方法有哪些

这篇文章主要介绍“go语言扩容方法有哪些”，在日常操作中，相信很多人在go语言扩容方法有哪些问题上存在疑惑，小编查阅了各式资料，整理出简单好用的操作方法，希望对大家解答”go语言扩容方法有哪些”的疑惑有所帮助！接下来，请跟着小编一起来学习吧！

go语言扩容方法有：1、Slice扩容，在使用append向Slice追加元素时，如果Slice空间不足，将会触发Slice扩容；2、Map扩容。触发Map扩容的条件有二个：1、负载因子大于6.5时，也即平均每个bucket存储的键值对达到6.5个；2、overflow数量大于2^15时，也即overflow数量超过32768时。

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

// 只关心扩容规则的简化版growslicefunc 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数量增多，但负载因子又不高，从而无法执行增量搬迁的情况，如下图所示：