Golang是如何实现动态数组功能的?Slice切片原理解析

Hi 亲爱的朋友们，我是 k 哥。今天，咱们聊一聊Golang 切片。

当我们需要使用数组，但是又不能提前定义数组大小时，可以使用golang的动态数组结构，slice切片。在 Go 语言的众多特性里，slice 是我们经常用到的数据结构。但您有没有想过，它在背后是怎么工作的呢？接下来，咱们就一起仔仔细细地研究研究 slice 的底层到底是咋回事。比如它的底层数据结构是咋样的，又是怎么和数组配合实现动态数组功能的。把这些弄明白了，咱们写代码不光能更高效，还能躲开不少容易出错的地方。

原理

数据结构

我们每定义一个slice变量，golang底层都会构建一个slice结构的对象。slice结构体由3个成员变量构成：

• array表示数组指针，数组用于存储数据。

• len表示切片长度，也就是数组index从0到len-1已存储数据。

• cap表示切片容量，当切片长度超过最大容量时，需要扩容申请更大长度的数组。

type slice struct {array unsafe.Pointer // 数组指针len   int // 切片长度cap   int // 切片容量
}

切片扩容

当我们往切片中append时，如果新添加数据会导致切片的len>cap，则会触发扩容。申请容量更大的新数组，并将旧数组数据复制到新数组。

当切片扩容时，新申请的数组长度要满足3个需求：

1. 数组要能承载本次数据append进去，这是基本要求。

2. 除了1中的基本要求，可以额外多申请一部分空间，防止后续append频繁扩容，引起性能问题。

3. 额外申请的空间不能过大，防止内存浪费。

为了满足上述的3个要求，golang底层的扩容策略是如果需要的容量比旧容量大很多，则不申请额外的空间；如果需要的容量比旧容量并没有大很多，则可以多申请一些额外的内存空间。具体策略如下：

1. 如果本次append之后，需要的容量大于旧切片容量*2，则新切片容量等于需要的容量。

2. 如果旧切片容量<256，则新切片容量为旧切片容量*2。

3. 否则，以公式newcap += (newcap + 3*threshold) / 4迭代，直到newcap大于需要的容量为止，将newcap作为新切片容量。

// growslice handles slice growth during append.
// It is passed the slice element type, the old slice, and the desired new minimum capacity,
// and it returns a new slice with at least that capacity, with the old data
// copied into it.
// The new slice's length is set to the old slice's length,
// NOT to the new requested capacity.
// This is for codegen convenience. The old slice's length is used immediately
// to calculate where to write new values during an append.
// 参数cap表示本次append之后需要的切片容量
func growslice(et *_type, old slice, cap int) slice {// 扩容策略，决定扩容后切片容量newcap，也就是需要申请的新数组长度。newcap := old.capdoublecap := newcap + newcapif cap > doublecap {newcap = cap} else {const threshold = 256if old.cap < threshold {newcap = doublecap} else {// Check 0 < newcap to detect overflow// and prevent an infinite loop.for 0 < newcap && newcap < cap {// Transition from growing 2x for small slices// to growing 1.25x for large slices. This formula// gives a smooth-ish transition between the two.newcap += (newcap + 3*threshold) / 4}// Set newcap to the requested cap when// the newcap calculation overflowed.if newcap <= 0 {newcap = cap}}}// 计算新切片的容量、长度var overflow boolvar lenmem, newlenmem, capmem uintptrlenmem = uintptr(old.len) * et.sizenewlenmem = uintptr(cap) * et.sizecapmem, overflow = math.MulUintptr(et.size, uintptr(newcap))capmem = roundupsize(capmem)newcap = int(capmem / et.size)// 数组内存申请var p unsafe.Pointerif et.ptrdata == 0 {p = mallocgc(capmem, nil, false)} else {p = mallocgc(capmem, et, true)}// 数据复制memmove(p, old.array, lenmem)// 构建新的切片返回return slice{p, old.len, newcap}
}

for 循环的坑

在for和for range循环中，对于循环迭代变量，它的作用域是整个循环。在循环时，会创建一个变量，每次迭代都会把值赋给同一个地址的变量。如果我们的代码有引用这个变量，可能会出现不符合预期的结果。

比如下面对for循环迭代变量i的使用，会输出不符合预期的结果。

func main() {var out []*intfor i := 0; i < 3; i++ {out = append(out, &i)}fmt.Println("Values:", *out[0], *out[1], *out[2]) // 输出 Values: 3 3 3fmt.Println("Addresses:", out[0], out[1], out[2]) // 输出 Addresses: 0x40e020 0x40e020 0x40e020
}

原因是在每次迭代中，我们将变量 i 的地址附加到 out 切片，但由于它是同一个变量，因此我们附加相同的地址，该地址最终包含分配给 i 的最后一个值。解决方案之一是将循环变量复制到新变量中：

 for i := 0; i < 3; i++ {
+   i := i // Copy i into a new variable.out = append(out, &i)}

改正之后输出符合预期的结果：

Values: 0 1 2
Addresses: 0x40e024 0x40e028 0x40e032

又比如下面for range循环，对迭代变量v的使用，也会输出不符合预期的结果。

package mainimport "fmt"type User struct {Name stringAge  int
}func main() {userMap := make(map[string]*User)users := []User{{Name: "a", Age: 22},{Name: "b", Age: 23},{Name: "c", Age: 21},}for _, v := range users {userMap[v.Name] = &v}for name, user := range userMap {fmt.Println(name, "=>", user.Age, ",Addresses:", &user) // 输出一下user的地址}
}

上面的代码输出不符合预期的结果，三个人的年龄和数据地址变成了相同值:

a => 21 ,Addresses: 0xc000012028
b => 21 ,Addresses: 0xc000012028
c => 21 ,Addresses: 0xc000012028

原因跟for循环一样，在循环时，创建了变量v，后续每次迭代都把值拷贝给变量v，导致循环结束后，拷贝的是最后一个，因此输出的age都是21。解决方案之一也是将循环变量复制到新变量中：

for _, v := range users {
+       temp := vuserMap[v.Name] = &temp
}

注意：为了防止循环迭代变量误用导致bug，在Go 1.22中，循环迭代变量的作用域，不再是循环作用域，而是迭代作用域，每次迭代都会申请一个新变量。Fixing For Loops in Go 1.22

实践经验

1. 切片容量预分配。如果提前能预估切片容量，最好提前在make时就分配好容量，避免后续go底层的再次扩容，在一定程度上能提升代码执行效率。

2. 注意对slice的循环，看是否需要将循环迭代变量赋值到一个临时变量使用，防止bug。

高频面试题

1. 数组和切片的区别 （基本必问）

2. 切片的扩容策略是怎样的？

3. for range 的时候它的地址会发生变化么？for 循环遍历 slice 有什么问题？

4. 拷贝大切片一定比小切片代价大吗？

对于浅拷贝，比如下面的切片赋值，拷贝大切片和小切片代价一样。原因是浅拷贝a和b共用底层数组，不需要重新申请数组空间，做数组数据迁移，而只需要将a的slice数据结构array、len、cap原样赋值给b的slice。

a:=[]int{1,2}
b:=a

对于深拷贝，比如调用copy函数拷贝，拷贝大切片比小切片代价大。原因是深拷贝a和b底层数组不共用，需要重新申请数组空间，并将a中数组元素复制到b，大切片的数据量大，因此数组申请和数据复制的代价也高一些。

a:=[]int{1,2}
b:=make([]int,0)
copy(b,a)

原文链接：<<Golang是如何实现动态数组功能的?Slice切片原理解析>>