golang slice append 后 capacity 增长的算法

杨永池 ·

一道题目：

图片描述

append函数

函数定义：func append(slice []Type, elems ...Type) []Type
函数说明：内建函数append追加一个或多个elems到一个slice依赖的array的末尾，如果这个slice有足够的capacity，则reslice以容纳新增元素；如果capacity空间不够，则重新分配内存保存新的slice依赖的array，函数返回更新后的slice.(slice是引用，array保存真正的数据，slice切片理解：https://blog.haohtml.com/arch...

注意：append不会修改传参进来的slice(len和cap)，只会在不够用的时候新分配一个array，并把之前的slice依赖的array数据拷贝过来；所以对同一个slice 重复 append，只要不超过cap，都是修改的同一个array，后面的会覆盖前面

capacity如何增长?

图片里提到"Capacity grows in a way not related to the size of appending data"，那么，增长算法是什么样的呢?看源代码 src/runtime/slice.go:

    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
            }
        }
    }

先将旧的slice容量乘以2，如果乘以2后的容量仍小于新的slice容量，则取新的slice容量(append多个elems)
如果新slice小于等于旧slice容量的2倍，则取旧slice容量乘以2
如果旧的slice容量大于1024，则新slice容量取旧slice容量乘以1.25

代码后面还会对newcap进行roundup，比如在64位平台，newcap是奇数的话就会+1

回头看题

package main

import (
    "fmt"
)
func main(){
    a := []int{1,2}
    b := append(a,3)
    fmt.Printf("cap(a)=%v,cap(b)=%v\n",cap(a),cap(b))
    c := append(b,4)
    d := append(b,5)
    fmt.Printf("cap(a)=%v,cap(b)=%v\n",cap(a),cap(b))
    fmt.Println(a,b,c,d)
    fmt.Printf("%p,%p,%p,%p\n",a,b,c,d)
}

第一次append，超出了a的cap范围，分配一个新的newcap为oldcap*2的array，即4；a不变
第二次append，len(b)是3，cap(b)是4，没有超出b的cap范围，b所依赖的array在len(b)的位置追加4，c共用这个array；b不变
第三次append，由于b没有变化，b所依赖的array在len(b)的位置追加5，会覆盖上一步的4
所以：c[3]和d[3]引用的是同一块内存，都是5

另外，如果 d:= append(c,5) 则结果就是 c[3]=4,d[3]=4,d[4]=5因为这一步会新分配array,并将c的数据拷贝过来