[Go] Slice的底层自动扩容

go语言圣经中的解释：

数组和slice之间有着紧密的联系。

一个slice是一个轻量级的数据结构，提供了访问数组子序列（或者全部）元素的功能，而且slice的底层确实引用一个数组对象。

一个slice由三个部分构成：指针、长度和容量。

指针指向第一个slice元素对应的底层数组元素的地址，要注意的是slice的第一个元素并不一定就是数组的第一个元素。

长度对应slice中元素的数目；长度不能超过容量

容量一般是从slice的开始位置到底层数据的结尾位置。内置的len和cap函数分别返回slice的长度和容量。

make([]T, len, cap)    len<=cap

在底层，make创建了一个匿名的数组变量，然后返回一个slice

slice只引用了底层数组的前len个元素，但是容量将包含整个的数组。额外的元素是留给未来的增长用的

从下面这个自定义函数里可以了解扩容机制：

func appendInt(x []int, y int) []int {

var z []int

//+1个元素后新的长度

zlen := len(x) + 1

//长度小于原来的容量大小

if zlen <= cap(x) {

// 还有剩余空间，直接可以拿到给新的slice

z = x[:zlen]

} else {

// 没有足够的空间，给新的slice分配原来二倍的空间

zcap := zlen

if zcap < 2*len(x) {

zcap = 2 * len(x)

}

z = make([]int, zlen, zcap)

copy(z, x) //把旧的slice复制到新的slice

}

z[len(x)] = y

return z

}

通过在每次扩展数组时直接将长度翻倍从而避免了多次内存分配，也确保了添加单个元素操的平均时间是一个常数时间

func main() {

var x, y []int

for i := 0; i < 10; i++ {

y = appendInt(x, i)

fmt.Printf("%d cap=%d\t%v\n", i, cap(y), y)

x = y

}

}

每一次容量的变化都会导致重新分配内存和copy操作,当容量不够的时候，会有一个翻倍扩充

0 cap=1 [0]

1 cap=2 [0 1]

2 cap=4 [0 1 2]

3 cap=4 [0 1 2 3]

4 cap=8 [0 1 2 3 4]

5 cap=8 [0 1 2 3 4 5]

6 cap=8 [0 1 2 3 4 5 6]

7 cap=8 [0 1 2 3 4 5 6 7]

8 cap=16 [0 1 2 3 4 5 6 7 8]

9 cap=16 [0 1 2 3 4 5 6 7 8 9]

向切片新增一个元素时，若该切片容量已满，会首先根据切片容量进行判断，小于1024字节扩容为原有容量的2倍，大于1024字节扩容为原有容量的1.25倍

好文阅读