go语言切片扩容
切片的容量
切片是基于数组实现的一个特殊的数据结构，有三个属性，指向底层数组的指针、长度（len）和容量（cap）。
长度指的就是切片里元素实际的个数，容量是指针指向数组的长度。
初始化时切片的长度与容量
// 默认len=cap，均为4
arr := make([]int, 4)
// 分别制定len和cap，len为1，cap为4
arr2 := make([]int, 1, 4)
切片扩容时的容量
// The append built-in function appends elements to the end of a slice. If
// it has sufficient capacity, the destination is resliced to accommodate the
// new elements. If it does not, a new underlying array will be allocated.
// Append returns the updated slice. It is therefore necessary to store the
// result of append, often in the variable holding the slice itself:
// slice = append(slice, elem1, elem2)
// slice = append(slice, anotherSlice...)
// As a special case, it is legal to append a string to a byte slice, like this:
// slice = append([]byte("hello "), "world"...)
func append(slice []Type, elems ...Type) []Type
看到注释的介绍，可以大概知道，如果追加元素后切片容量是足够的，那么就会直接在当前的基础数组中添加新的元素。但是如果超过了切片的容量，就会分配一个新的数组
func main() {
arr := []int{1,2,3}
arrBack := arr
// len为3，cap为3
fmt.Println(len(arr), cap(arr))
// len为4，cap为6
arr = append(arr, 4)
fmt.Println(len(arr), cap(arr))
arr[0] = 0
// 输出结果为1
fmt.Println(arrBack[0])
}
上面一个简单的例子，在len=cap的情况下，append一个元素的时候，长度增加了1，容量变为原来的2倍。通过对切片元素进行修改，可以确认是分配了一块儿新的内存，并不是在原数组内存后继续追加。
在append过程中还会遇到很多其他的情况，比如append的元素导致新的长度超过原先cap的两倍等。了解各种情况最简单的办法就是看append方法的具体实现（src/runtime/slice.go的growslice方法），了解切片扩容的内存分配的核心代码如下
func growslice(et *_type, old slice, cap int) slice {
// ... 省略部分逻辑
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
newcap = cap
} else {
if old.len < 1024 {
newcap = doublecap
} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {
newcap += newcap / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {
newcap = cap
}
}
}
// ...省略部分逻辑
}
通过阅读代码，主要分为三种情况
-
如果所需容量大于原先容量的两倍，那么就会直接申请需要的容量。
由于后续的处理，如果最终的容量是奇数，最终的容量是所需容量+1
// len为8，cap为8
arr := []int{1, 2, 3}
newArr := []int{4, 5, 6, 7, 8}
arr = append(arr, newArr...)
fmt.Println(len(arr), cap(arr))
// len为9，cap为10
arr := []int{1, 2, 3}
newArr := []int{4, 5, 6, 7, 8, 9}
arr = append(arr, newArr...)
fmt.Println(len(arr), cap(arr))
- 当前所需容量小于或等于原容量的两倍，而且原切片长度小于1024时，最终申请的容量为原容量的两倍
// len为5，cap为6
arr := []int{1, 2, 3}
newArr := []int{4, 5}
arr = append(arr, newArr...)
fmt.Println(len(arr), cap(arr))
-
当前所需容量小于或等于原容量的两倍，而且原切片长度大于1024时。申请容量会从原容量开始，每次增加1/4，直到大于或等于所需容量为止
因为容量时int类型，当切片长度巨大的时候，增加1/4会出现溢出的情况（正常很难出现），如果溢出，直接使用所需容量
在未溢出的情况下，由于后续的处理，最终结果并非严格等于5/4的累乘结果。
// len为2500，cap为2560
arr := make([]int, 2000)
newArr := make([]int, 500)
arr = append(arr, newArr...)
fmt.Println(len(arr), cap(arr))
// len为2520，3408
arr := make([]int, 2000)
newArr := make([]int, 520)
arr = append(arr, newArr...)
fmt.Println(len(arr), cap(arr))