切片定义
slice源代码定义：
1
2
3
4
5
|
type slice struct {
array unsafe.Pointer //指向底层数组的指针
len int //切片长度
cap int //切片容量
}
|
如果仅仅是提供通过下标值来操作元素的类数组操作接口，那么切片也不会在 Go 中占据重要的位置。Go 切片还支持一个重要的高级特性：动态扩容。我们提到过切片类型是部分满足零值可用理念的，即零值切片也可以通过 append 预定义函数进行元素赋值操作：
1
2
|
var s []byte // s被赋予零值nil
s = append(s, 1)
|
由于初值为零值，s 这个描述符并没有绑定对应的底层数组。而经过 append 操作后，s 显然已经绑定了属于它的底层数组。
切片扩容案例
为了方便查看切片是如何动态扩容的，我们打印出每次 append 操作后切片 s 的 len 和 cap 值：
1
2
3
4
5
6
7
8
9
10
11
|
var s [] int //s 被赋予零值 nil
s = append (s, 11)
fmt.Println (len (s), cap (s)) //1 1
s = append (s, 12)
fmt.Println (len (s), cap (s)) //2 2
s = append (s, 13)
fmt.Println (len (s), cap (s)) //3 4
s = append (s, 14)
fmt.Println (len (s), cap (s)) //4 4
s = append (s, 15)
fmt.Println (len (s), cap (s)) //5 8
|
我们看到切片 s 的 len 值是线性增长的，但 cap 值却呈现出不规则的变化。通过下图，我们更容易看清楚多次 append 操作究竟是如何让切片进行动态扩容的。
我们看到 append 会根据切片对底层数组容量的需求对底层数组进行动态调整。
1）最初 s 初值为零值（nil），此时 s 没有绑定底层数组。
2）通过 append 操作向切片 s 添加一个元素 11，此时 append 会首先分配底层数组 u1（数组长度 1），然后将 s 内部表示中的 array 指向 u1，并设置 len = 1，cap =1。
3）通过 append 操作向切片 s 再添加一个元素 12，此时 len (s) = 1，cap (s) = 1，append 判断底层数组剩余空间不满足添加新元素的要求，于是创建了一个新的底层数组 u2，长度为 2（u1 数组长度的 2 倍），并将 u1 中的元素复制到 u2 中，最后将 s 内部表示中的 array 指向 u2，并设置 len = 2，cap = 2。
4）通过 append 操作向切片 s 再添加一个元素 13，此时 len (s) = 2，cap (s) = 2，append 判断底层数组剩余空间不满足添加新元素的要求，于是创建了一个新的底层数组 u3，长度为 4（u2 数组长度的 2 倍），并将 u2 中的元素复制到 u3 中，最后将 s 内部表示中的 array 指向 u3，并设置 len = 3，cap 为 u3 数组长度，即 4。
5）通过 append 操作向切片 s 再添加一个元素 14，此时 len (s) = 3，cap (s) = 4，append 判断底层数组剩余空间满足添加新元素的要求，于是将 14 放在下一个元素的位置（数组 u3 末尾），并将 s 内部表示中的 len 加 1，变为 4。
6）通过 append 操作向切片 s 添加最后一个元素 15，此时 len (s) = 4，cap (s) = 4，append 判断底层数组剩余空间不满足添加新元素的要求，于是创建了一个新的底层数组 u4，长度为 8（u3 数组长度的 2 倍），并将 u3 中的元素复制到 u4 中，最后将 s 内部表示中的 array 指向 u4，并设置 len = 5，cap 为 u4 数组长度，即 8。
我们看到 append 会根据切片的需要，在当前底层数组容量无法满足的情况下，动态分配新的数组，新数组长度会按一定算法扩展（参见 $GOROOT/src/runtime/slice.go 中的 growslice 函数）。新数组建立后，append 会把旧数组中的数据复制到新数组中，之后新数组便成为切片的底层数组，旧数组后续会被垃圾回收掉。这样的 append 操作有时会给 Gopher 带来一些困惑，比如通过语法 u [low: high] 形式进行数组切片化而创建的切片，一旦切片 cap 触碰到数组的上界，再对切片进行 append 操作，切片就会和原数组解除绑定：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
func main () {
u := [] int {11, 12, 13, 14, 15}
fmt.Println ("array:", u) // [11, 12, 13, 14, 15]
s := u [1:3]
fmt.Printf ("slice (len=% d, cap=% d): % v\n", len (s), cap (s), s) // [12, 13]
s = append (s, 24)
fmt.Println ("after append 24, array:", u)
fmt.Printf ("after append 24, slice (len=% d, cap=% d): % v\n", len (s), cap (s), s)
s = append (s, 25)
fmt.Println ("after append 25, array:", u)
fmt.Printf ("after append 25, slice (len=% d, cap=% d): % v\n", len (s), cap (s), s)
s = append (s, 26)
fmt.Println ("after append 26, array:", u)
fmt.Printf ("after append 26, slice (len=% d, cap=% d): % v\n", len (s), cap (s), s)
s [0] = 22
fmt.Println ("after reassign 1st elem of slice, array:", u)
fmt.Printf ("after reassign 1st elem of slice, slice (len=% d, cap=% d): % v\n", len (s), cap (s), s)
}
|
运行这段代码，得到如下结果：
1
2
3
4
5
6
7
8
9
10
11
|
$go run slice_unbind_orig_array.go
array: [11 12 13 14 15]
slice (len=2, cap=4): [12 13]
after append 24, array: [11 12 13 24 15]
after append 24, slice (len=3, cap=4): [12 13 24]
after append 25, array: [11 12 13 24 25]
after append 25, slice (len=4, cap=4): [12 13 24 25]
after append 26, array: [11 12 13 24 25]
after append 26, slice (len=5, cap=8): [12 13 24 25 26]
after reassign 1st elem of slice, array: [11 12 13 24 25]
after reassign 1st elem of slice, slice (len=5, cap=8): [22 13 24 25 26]
|
我们看到在添加元素 25 之后，切片的元素已经触碰到底层数组 u 的边界；此后再添加元素 26，append 发现底层数组已经无法满足添加新元素的要求，于是新创建了一个底层数组（数组长度为 cap (s) 的 2 倍，即 8），并将原切片的元素复制到新数组中。在这之后，即便再修改切片中的元素值，原数组 u 的元素也没有发生任何改变，因为此时切片 s 与数组 u 已经解除了绑定关系，s 已经不再是数组 u 的描述符了。
扩容源代码
growslice函数部分源代码：
（此为1.18版本之后）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
// 前面代码省略...
newcap := old.cap
doublecap := newcap + newcap //双倍扩容（原容量的两倍）
if cap > doublecap { //如果所需容量大于 两倍扩容，则直接扩容到所需容量
newcap = cap
} else {
const threshold = 256 //这里设置了一个 阈值 -- 256
if old.cap < threshold { //如果旧容量 小于 256，则两倍扩容
newcap = doublecap
} else {
// 检查 0 < newcap 以检测溢出并防止无限循环。
for 0 < newcap && newcap < cap { //如果新容量 > 0 并且 原容量 小于 所需容量
// 从小片的增长2x过渡到大片的增长1.25x。这个公式给出了两者之间的平滑过渡。(这里的系数会随着容量的大小发生变化，从2.0到无线接近1.25)
newcap += (newcap + 3*threshold) / 4
//当newcap计算溢出时，将newcap设置为请求的上限。
if newcap <= 0 { // 如果发生了溢出，将新容量设置为请求的容量大小
newcap = cap
}
}
}
// 后面代码省略...
return slice{p, newLen, newcap}
}
}
|
扩容规则如下：
- 如果请求容量 大于 两倍现有容量 ，则新容量 直接为请求容量。
- 否则（请求容量 小于等于 两倍现有容量）
- 如果 现有容量 小于 256 ，则新容量是原来的两倍；
- 否则：新容量 = 1.25 原容量 + 3/4 阈值 “这个公式给出了从1.25倍增长 过渡到2 倍增长，两者之间的平滑过渡。” 在此情况下，如果发生了溢出，将新容量设置为请求的容量大小。
参考
《Go语言精进之路：从新手到高手的编程思想、方法和技巧 1》13.2 切片的高级特性：动态扩容
golang slice (切片) 扩容机制详解（1.18版本后）
