淺談Golang 切片（slice）擴容機制的原理

更新時間：2021年06月09日 09:07:12 作者：Linux猿

我們知道 Golang 切片在容量不足的情況下會進行擴容，擴容的原理是怎樣的呢，具有一定的參考價值，感興趣的小伙伴們可以參考一下

我們知道 Golang 切片（slice）在容量不足的情況下會進行擴容，擴容的原理是怎樣的呢？是不是每次擴一倍？下面我們結(jié)合源碼來告訴你答案。

一、源碼

Version : go1.15.6 src/runtime/slice.go

//go1.15.6 源碼 src/runtime/slice.go
func growslice(et *_type, old slice, cap int) slice {
 //省略部分判斷代碼
    //計算擴容部分
    //其中，cap : 所需容量，newcap : 最終申請容量
 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. 如果當前所需容量（cap）大于原先容量的兩倍（doublecap），則最終申請容量（newcap）為當前所需容量（cap）；

2. 如果<條件1>不滿足，表示當前所需容量（cap）不大于原容量的兩倍（doublecap），則進行如下判斷；

3. 如果原切片長度（old.len）小于1024，則最終申請容量（newcap）等于原容量的兩倍（doublecap）；

4. 否則，最終申請容量（newcap，初始值等于 old.cap）每次增加 newcap/4，直到大于所需容量（cap）為止，然后，判斷最終申請容量（newcap）是否溢出，如果溢出，最終申請容量（newcap）等于所需容量（cap）；

這樣說大家可能不太明白，來幾個例子：

2.1 實例1

驗證條件1：

package main
 
import "fmt"
 
func main() {
 //第1條中的例子：
 var slice = []int{1, 2, 3}
 var slice1 = []int{4, 5, 6, 7, 8, 9, 10, 11, 12}
 fmt.Printf("slice %v len = %v cap = %v\n", slice, len(slice), cap(slice))
 fmt.Printf("slice1 %v len = %v cap = %v\n", slice1, len(slice1), cap(slice1))
 slice = append(slice, slice1...)
 fmt.Printf("slice %v len = %v cap = %v\n", slice, len(slice), cap(slice))
}

輸出：

[root@localhost test]# go run main.go
slice [1 2 3] len = 3 cap = 3
slice1 [4 5 6 7 8 9 10 11 12] len = 9 cap = 9
slice [1 2 3 4 5 6 7 8 9 10 11 12] len = 12 cap = 12
[root@localhost test]#

在實例1中，所需容量 cap = 9+3 = 12，原容量的兩倍 doublecap = 2 * 3 = 6，滿足 <條件1> 即：所需容量大于原容量的兩倍，所以最終申請容量 newcap = cap = 12。

2.2 實例2

驗證條件2,3：

package main
import "fmt"
 
func main() {
 //第2、3條中的例子：
 var slice = []int{1, 2, 3, 4, 5, 6, 7}
 var slice1 = []int{8, 9}
 fmt.Printf("slice %v len = %v cap = %v\n", slice, len(slice), cap(slice))
 fmt.Printf("slice1 %v len = %v cap = %v\n", slice1, len(slice1), cap(slice1))
 slice = append(slice, slice1...)
 fmt.Printf("slice %v len = %v cap = %v\n", slice, len(slice), cap(slice))
}

輸出：

[root@localhost test]# go run main.go
slice [1 2 3 4 5 6 7] len = 7 cap = 7
slice1 [8 9] len = 2 cap = 2
slice [1 2 3 4 5 6 7 8 9] len = 9 cap = 14
[root@localhost test]#

在實例2中，所需容量 cap = 7+2 = 9，原容量的兩倍 doublecap = 2*7 = 14，原切片長度 old.len = 7，滿足 <條件2,3>，即：所需容量小于原容量的兩倍，并且原切片長度 old.len 小于1024，所以，最終申請容量 newcap = doublecap = 14。

2.3 實例3

驗證條件4：

package main
import "fmt"
 
func main() {
 //第2條中的例子：
 var slice []int
 for i := 0; i < 1024; i++ {
  slice = append(slice, i)
 }
 var slice1 = []int{1024, 1025}
 fmt.Printf("slice %v len = %v cap = %v\n", slice, len(slice), cap(slice))
 fmt.Printf("slice1 %v len = %v cap = %v\n", slice1, len(slice1), cap(slice1))
 slice = append(slice, slice1...)
 fmt.Printf("slice %v len = %v cap = %v\n", slice, len(slice), cap(slice))
}

輸出：

[root@localhost test]# go run main.go
slice [0 1 2 3 4 5 6……1017 1018 1019 1020 1021 1022 1023] len = 1024 cap = 1024
slice1 [1024 1025] len = 2 cap = 2
slice [0 1 2 3 4 5 6……1017 1018 1019 1020 1021 1022 1023 1024 1025] len = 1026 cap = 1280
[root@localhost test]#

在實例3中，所需容量 cap = 1024+2 = 1026，doublecap = 2048, old.len = 1024，滿足 <條件4> ，所以，newcap = 1024 + 1024/4 = 1280。

到此這篇關于淺談Golang 切片（slice）擴容機制的原理的文章就介紹到這了,更多相關Golang 切片擴容機制內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: