|
这篇文章主要介绍“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
// 只关心扩容规则的简化版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数量会减少，即节省了空间又会提高访问效率。
（编辑：聊城站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
