golang slice append 后 capacity 增长的算法

手把手教你学安卓 2019-06-30

一道题目:

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
            }
        }
    }
  1. 先将旧的slice容量乘以2,如果乘以2后的容量仍小于新的slice容量,则取新的slice容量(append多个elems)
  2. 如果新slice小于等于旧slice容量的2倍,则取旧slice容量乘以2
  3. 如果旧的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的数据拷贝过来

总结

写得比较匆忙,如有纰漏,欢迎指正。

相关推荐