数组array和切片slice是 Go 语言的两种基本数据结构，也是我们需要深入了解的基础概念。在本篇文章中，我们将深入探讨 Go 语言的数组和切片实现原理，帮助大家更好地理解它们的使用方法和优劣势。
本文源码基于 Go 1.20
数组
数据结构
数组是计算机科学中的一种数据结构，它具有以下几个特点：
- 元素类型相同，存储宽度一致
- 存储在一段连续的内存空间
- 空间大小固定，不能修改（会出现数据溢出问题）
- 可以通过元素索引计算出元素的存储地址
几乎所有的计算机语言，对于数组的实现都是相似的，都拥有上述特性，Go语言也一样。
不同于 C 语言或其他语言，Go 语言数组是值类型，定义的时候就需要指定大小，数组大小是它类型的一部分，不同大小的数组相当于不同的类型，赋值和函数传参都会复制整个数组，相当于是原数组的拷贝。
初始化
数组有两种初始化的方式，一种是显示声明数组的长度，一种是使用[...]T声明数组。
arr1 := [3]int{0, 1, 2}
arr2 := [...]int{0, 1, 2}
第二种初始化的方式属于 Go 语言提供的语法糖，在编译期间就会推导出数组的长度，最终转换成第一种，所以上述两种声明方式在运行期间得到的结果是相同的。
在编译期间，Go 会根据数组的元素数量，做出如下的优化：
- 当元素小于等于4个时，会直接将数组的元素在栈上面初始化；
- 当元素大于4个时，会将数组在静态区初始化然后复制到栈上面。
缺点
数组大小是固定的，但是很多场景中我们无法直接给出数组的确定长度。
数组是值类型，传递一个很大的数组给函数会消耗很多内存。
切片
由于数组的固定长度和值传递不够灵活，所以 Go 语言中，拥有不定长度的引用类型切片（slice）更加常用。
切片是对数组一个连续片段的引用，这些片段可以是整个数组，或者是由其实和终止索引表示的一些项的子集。
数据结构
切片的数据结构在源码包中定义
// src/runtime/slice.go
type slice struct {
array unsafe.Pointer // 元素指针
len int // 长度
cap int // 容量
}
其中，array表示指向相关数组的指针，len表示切片长度，cap表示当前切片的容量，即底层数组的大小。其中底层数组是可以被多个 slice 同时指向的，所以对一个 slice 中的元素进行操作，可能也会影响到其他slice.
由于切片结构体中直接存储了切片的长度和容量，所以内置函数len()和cap()操作的时间复杂度均为O(1).
切片在运行时的表示:
// src/reflect/value.go
// Deprecated: Use unsafe.Slice or unsafe.SliceData instead.
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
// go 1.20 src/unsafe/unsafe.go
// SliceData returns a pointer to the underlying array of the argument
// slice.
// - If cap(slice) > 0, SliceData returns &slice[:1][0].
// - If slice == nil, SliceData returns nil.
// - Otherwise, SliceData returns a non-nil pointer to an
// unspecified memory address.
func SliceData(slice []ArbitraryType) *ArbitraryType
初始化
- 变量声明
var s []int
使用这种方式创建出来的 slice 是变量零值，即 nil。它的长度和容量都是 0 ，和nil相等。nil切片可以通过append函数来完成内存申请和元素追加。
- 字面量
s1 := []int{} // 空切片
s2 := []int{1, 2} // 长度为3的切片
s3 := []int{0, 1, 2, 3, 8: 100} // 使用索引号直接复制，将索引为 8 位置的元素赋值为 100
其中，空切片指的是切片长度为 0 ，但是值并不是nil，声明长度为 0 的切片时，尽量使用nil切片，这样就不需要进行内存分配。
- make 函数
s1 := make([]int, 10) // 指定长度，此时容量默认和长度相等
s2 := make([]int, 10, 30) //指定长度和容量
创建时，底层会分配一个数组，数组的长度就是切片的容量。
创建切片时的运行运行时函数如下：
// src/runtime/slice.go
func makeslice(et *_type, len, cap int) unsafe.Pointer {
// 内存空间 = 元素大小 * 切片容量
mem, overflow := math.MulUintptr(et.size, uintptr(cap))
// panic 条件
// 1.内存空间溢出
// 2.申请的内存空间大于最大可分配的内存
// 3.长度小于 0 或大于容量
if overflow || mem > maxAlloc || len < 0 || len > cap {
mem, overflow := math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}
// 内存申请：小对象在 P 结构中初始化，大于 32KB 在堆中初始化
return mallocgc(mem, et, true)
}
- 通过下标从数组或切片中切取
s1 := array[1:5]
s2 := sourceSlice[1:5]
使用下标初始化不会复制原数组或者原切片中的数据，只会创建一个指向原数组的结构体，数组后面的内容都作为切片的预留内存。
同时，slice 将和原数组共用一部分内存，对数组或slice元素的修改，都会影响到彼此。如果因为执行append操作使得新的 slice 底层数组扩容，移动到了新的位置，那么两者就不会互相影响了。
追加和扩容
追加
使用 append函数可以向切片中追加元素：
func append(slice []Type, elems ...Type) []Type
append函数的参数长度可变，所以可以追加多个值到 slice 中，还可以用 ...传入 slice，直接追加一个切片。
s1 = append(s1, 1, 2, 3)
s1 = append(s1, s2...)
append函数返回值是一个新的 slice，可以选择覆盖原 slice，也可以选择定义赋值给新的 slice，但是 Go 编译器不允许调用了 append函数后不使用返回值。
扩容
使用append向 slice 中追加元素，实际上是向底层数组添加元素，如果 slice 底层数组空间不足，就会触发 slice 扩容。
扩容就是为切片分配新的内存空间并复制原切片中元素的过程。新的底层数组长度大于原有的 slice 底层数组，这样就可以进行append操作，具体的扩容策略如下：
// src/runtime/slice.go
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
...
// 扩容策略
newcap := oldCap
doublecap := newcap + newcap
if newLen > doublecap {
// 期望大小大于当前容量的两倍，使用期望大小
newcap = newLen
} else {
// 期望大小小于当前容量的两倍
const threshold = 256
if oldCap < threshold {
// 原容量小于 256 ，容量翻倍
newcap = doublecap
} else {
// 原容量大于256
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
// 保证 newcap > newLen
for 0 < newcap && newcap < newLen {
// Transition from growing 2x for small slices
// to growing 1.25x for large slices. This formula
// gives a smooth-ish transition between the two.
// 每次增加 25% + 192，比 Go1.18 之前更加平滑
newcap += (newcap + 3*threshold) / 4
}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
// 溢出情况处理
if newcap <= 0 {
newcap = newLen
}
}
}
...
}
在运行时，根据新长度的大小，选择了不同的策略进行扩容：
- 如果期望大小大于当前容量的两倍，新容量就会使用期望大小
- 否则判断，如果旧切片的容量小于 256，新容量就会是旧容量的两倍
- 否则判断，如果旧切片的容量大于256，新容量就会使用从旧容量开始循环增加，每次增加
25% + 192，直到新容量大于等于新长度。 - 如果新容量计算溢出了，就使用新长度作为新容量。
这个扩容策略是在 Go 1.18 开始执行的，相比 Go 1.18 之前使用 1024 作为扩容基准值，这个策略则更加平滑。
经过上述策略，得到的新容量只能说是一个大致容量，最终的容量和内存大小，还需要根据切片中的元素大小进行内存对齐。具体内存对齐代码如下所示：
// src/runtime/slice.go
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
...
// 新长度及容量大小计算，根据切片中元素大小进行内存对齐
var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.size.
// For 1 we don't need any division/multiplication.
// For goarch.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
switch {
case et.size == 1:
lenmem = uintptr(oldLen)
newlenmem = uintptr(newLen)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
case et.size == goarch.PtrSize:
lenmem = uintptr(oldLen) * goarch.PtrSize
newlenmem = uintptr(newLen) * goarch.PtrSize
capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
newcap = int(capmem / goarch.PtrSize)
case isPowerOfTwo(et.size):
var shift uintptr
if goarch.PtrSize == 8 {
// Mask shift for better code generation.
shift = uintptr(sys.TrailingZeros64(uint64(et.size))) & 63
} else {
shift = uintptr(sys.TrailingZeros32(uint32(et.size))) & 31
}
lenmem = uintptr(oldLen) << shift
newlenmem = uintptr(newLen) << shift
capmem = roundupsize(uintptr(newcap) << shift)
overflow = uintptr(newcap) > (maxAlloc >> shift)
newcap = int(capmem >> shift)
capmem = uintptr(newcap) << shift
default:
lenmem = uintptr(oldLen) * et.size
newlenmem = uintptr(newLen) * et.size
capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
capmem = roundupsize(capmem)
newcap = int(capmem / et.size)
capmem = uintptr(newcap) * et.size
}
...
}
// src/runtime/msize.go
func roundupsize(size uintptr) uintptr {
if size < _MaxSmallSize {
if size <= smallSizeMax-8 {
return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
} else {
return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
}
}
if size+_PageSize < size {
return size
}
return alignUp(size, _PageSize)
}
// src/runtime/sizeclass.go
const (
_MaxSmallSize = 32768
smallSizeDiv = 8
smallSizeMax = 1024
largeSizeDiv = 128
_NumSizeClasses = 68
_PageShift = 13
)
// 这是 Go 源码中有关内存分配的 slice。
// class_to_size 通过 spanClass获取 span划分的 object大小。
// 而 size_to_class8 size_to_class128 表示通过 size 获取它的 spanClass
var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 32, 48, 64, 80, 96, 112, 128, 144, 160, 176, 192, 208, 224, 240, 256, 288, 320, 352, 384, 416, 448, 480, 512, 576, 640, 704, 768, 896, 1024, 1152, 1280, 1408, 1536, 1792, 2048, 2304, 2688, 3072, 3200, 3456, 4096, 4864, 5376, 6144, 6528, 6784, 6912, 8192, 9472, 9728, 10240, 10880, 12288, 13568, 14336, 16384, 18432, 19072, 20480, 21760, 24576, 27264, 28672, 32768}
var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16, 17, 17, 18, 18, 19, 19, 19, 19, 20, 20, 20, 20, 21, 21, 21, 21, 22, 22, 22, 22, 23, 23, 23, 23, 24, 24, 24, 24, 25, 25, 25, 25, 26, 26, 26, 26, 27, 27, 27, 27, 27, 27, 27, 27, 28, 28, 28, 28, 28, 28, 28, 28, 29, 29, 29, 29, 29, 29, 29, 29, 30, 30, 30, 30, 30, 30, 30, 30, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32}
var size_to_class128 = [(_MaxSmallSize-smallSizeMax)/largeSizeDiv + 1]uint8{32, 33, 34, 35, 36, 37, 37, 38, 38, 39, 39, 40, 40, 40, 41, 41, 41, 42, 43, 43, 44, 44, 44, 44, 44, 45, 45, 45, 45, 45, 45, 46, 46, 46, 46, 47, 47, 47, 47, 47, 47, 48, 48, 48, 49, 49, 50, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 53, 53, 54, 54, 54, 54, 55, 55, 55, 55, 55, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 58, 58, 58, 58, 58, 58, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 61, 61, 61, 61, 61, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67}
// src/runtime/stubs.go
func divRoundUp(n, a uintptr) uintptr {
// a is generally a power of two. This will get inlined and
// the compiler will optimize the division.
return (n + a - 1) / a
}
rounddupsize函数会将待申请的内存向上取整，取整时会使用class_to_size数组，提高了内存分配效率并减少碎片。
接下来，就是进行内存分配，复制数据，append元素到新的底层数组。
// src/runtime/slice.go
func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
...
// 计算内存溢出
if overflow || capmem > maxAlloc {
panic(errorString("growslice: len out of range"))
}
var p unsafe.Pointer
if et.ptrdata == 0 {
// 切片中的元素不是指针类型
// 分配内存
p = mallocgc(capmem, nil, false)
// 清除不会覆盖的部分
memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
} else {
// 切片中的元素是指针类型
// 分配内存
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// 内存屏障
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(oldPtr), lenmem-et.size+et.ptrdata)
}
}
// 复制原数组内存中的内容到新申请的内存中
memmove(p, oldPtr, lenmem)
return slice{p, newLen, newcap}
}
此外，nil切片和空切片都是可以通过调用append函数来获得底层数组的扩容，最终都是通过mallocgc来进行内存申请，再赋值给原来的nil切片或空切片，所以nil切片是可以调动append函数的。
我们用一个常见的例子总结一下扩容的过程
func main() {
s := []int{1, 2}
s = append(s, 3, 4, 5)
fmt.Printf("len=%d, cap=%d",len(s), cap(s))
}
程序运行结果为：
len = 5, cap = 6
在上述代码执行的过程中，我们先初始化了一个长度和容量均为 2 的切片 s ，然后向 s 中追加三个元素，此时就会触发扩容，期望大小为 5，5 大于当前容量的两倍，所以初步计算的 newcap 为 5，在 64
位机器上一个指针的大小为 8 字节，所以期望分配的内存大小为 40 字节。然后要进行内存对齐计算，调用roundupsize进行向上取整，计算结果如下所示：
// capmem 计算公式 class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]]
divRoundUp(40, 8) = 5
size_to_class8[5] = 5
capmem = class_to_size[5] = 48
// newcap 计算
newcap = int(capmem / goarch.PtrSize) = 48/8 = 6
所以，最终新的 slice 容量为 6.
拷贝
使用copy函数可以进行切片的拷贝操作，具体实现如下所示：
// src/runtime/slice.go
// 元素类型为string 或者 无指针 元素切片copy
func slicecopy(toPtr unsafe.Pointer, toLen int, fromPtr unsafe.Pointer, fromLen int, width uintptr) int {
// 如果长度为0，不需要 copy
if fromLen == 0 || toLen == 0 {
return 0
}
// 记录源切片或者目标切片中较短的长度
n := fromLen
if toLen < n {
n = toLen
}
// 元素类型宽度为0，也不需要执行 copy 操作，直接返回短切片的长度
if width == 0 {
return n
}
// 计算大小
size := uintptr(n) * width
...
if size == 1 { // common case worth about 2x to do here
// TODO: is this still worth it with new memmove impl?
// 如果 size 大小为1，那么指针直接转换即可
*(*byte)(toPtr) = *(*byte)(fromPtr) // known to be a byte pointer
} else {
// 使用 memmove 将 size 大小的内存复制到目标区域
memmove(toPtr, fromPtr, size)
}
return n
}
// src/runtime/mbarrier.go
// 指针类型的元素切片 copy
func typedslicecopy(typ *_type, dstPtr unsafe.Pointer, dstLen int, srcPtr unsafe.Pointer, srcLen int) int {
// copy 长度计算
n := dstLen
if n > srcLen {
n = srcLen
}
if n == 0 {
return 0
}
...
if writeBarrier.cgo {
cgoCheckSliceCopy(typ, dstPtr, srcPtr, n)
}
// 指针相等，不需要copy了
if dstPtr == srcPtr {
return n
}
// 内存大小计算
size := uintptr(n) * typ.size
if writeBarrier.needed {
pwsize := size - typ.size + typ.ptrdata
bulkBarrierPreWrite(uintptr(dstPtr), uintptr(srcPtr), pwsize)
}
// 内存 copy
memmove(dstPtr, srcPtr, size)
return n
}
上述代码分别是 string 及 元素无指针类型 切片以及指针类型元素切片的拷贝，其实现方法是类似的，即
- 拷贝长度为两个切片长度的最小值
- 拷贝内容为源切片中对应拷贝长度的整块内存的内容
- 返回值为被拷贝的元素的个数
由此也可以得出，在拷贝的过程中，不会发生扩容。
此外，在 range遍历的过程中，获得的 value 其实是切片中的值拷贝，并且每次都是拷贝到同一个地址，所以在遍历中拿到的 value 的地址是不变的，如下所示：
func main() {
slice := []int{10, 20, 30, 40}
for index, value := range slice {
fmt.Printf("value = %d , value-addr = %x , slice-addr = %x\n", value, &value, &slice[index])
}
}
输出结果：
value = 10, value-addr = 14000126008, slice-addr = 1400012e000
value = 20, value-addr = 14000126008, slice-addr = 1400012e008
value = 30, value-addr = 14000126008 , slice-addr = 1400012e010
value = 40 , value-addr = 14000126008, slice-addr = 1400012e018
参数传递
首先，我们必须明确一点，Go 语言中的函数参数传递，只有值传递，没有引用传递。
下面我们举几个例子来看看 slice 在函数参数传递中的一些细节。
slice 和 slice 指针
代码示例：
func Append(s []int) {
s = append(s, 100)
fmt.Printf("param s: %v \n ", s)
}
func AppendPtr(s *[]int) {
*s = append(*s, 200)
fmt.Printf("param *s: %v \n ", *s)
}
func main() {
s1 := []int{1, 1, 1}
Append(s1)
fmt.Printf("main s1: %v \n ", s1)
s2 := []int{1, 2, 3}
AppendPtr(&s2)
fmt.Printf("main *s2: %v \n ", s2)
}
程序运行结果为：
param s: [1 1 1 100]
main s1: [1 1 1]
param *s: [1 2 3 200]
main *s2: [1 2 3 200]
可以看出，在Append函数中，参数为 slice 值，所以对参数的变更，并不会影响到外层的 s.
但是，将 s 指针传入AppendPtr，在函数中对参数做出的改变，是会影响到外层的 s.
slice append 操作
代码示例：
func SliceRise(s []int) {
s = append(s, 0)
for i := range s {
s[i]++
}
}
func main() {
s1 := []int{1, 2}
s2 := s1
s2 = append(s2, 3)
SliceRise(s1)
SliceRise(s2)
fmt.Println(s1, s2)
}
程序运行结果为：
[1 2] [2 3 4]
首先，SliceRise()函数中 slice 作为参数，是一个值传递，函数调用时，会拷贝原 slice 的值，对于值的修改不会影响外层的 slice。
对于 s1 来说，底层数组本身的长度和容量均为2，传递进函数后，进行了 append 操作，这个 append 操作会引发切片的扩容，扩容后会产生一个新的底层数组，这个数组继续赋值给了变量 s。
此时，s1 和 s 指向的底层数组就不一样了，所以 s1 本身和它指向的底层数组，都没有发生任何变化，打印 s1 的结果仍然是 1 2.
对于 s2 来说，最初 s2 和 s1 指向同一个底层数组，进行 append 操作之后，发生了扩容，并且将 append 之后的新切片赋值给了 s2， 到这里，s1 和 s2 就指向不同的底层数组了。
s2 传递进函数后，进行了 append 操作，这个 append 操作不会引发切片的扩容，这个数组继续赋值给了变量 s。
此时，s2 和 s 依旧共享底层数组，但是s 的长度 len 变成 4 了，而由于函数参数值传递的特点，s2 的长度 len 并不会被改变，所以在进行遍历对元素进行操作之后，
虽然对于 s 和底层数组来说，值变成了2 3 4 1，但是对于 s2 来说，它的长度是 3，所以打印 s2 的结果会是2 3 4.
总结
- 数组存储的是一组元素类型相同，存储宽度一致的元素，它们存储在一段连续的内存空间，Go 中的数组是值类型，并且数组大小是固定的。
- 切片是对底层数组的一个抽象，表述的是对数组一个连续片段的引用。
- 切片结构体中包含了长度，容量以及底层数组地址，多个切片可以共享同一个底层数组。
append函数可以向切片中追加元素，并生成一个新的切片。当切片容量不足的情况下，append函数会先调用growslice进行扩容，然后再进行元素的追加。- 切片扩容后容量的计算分为按照策略计算和内存对齐两部分。扩容后的容量 >= 原容量的两倍 或 1.25倍。
- 切片作为函数参数时是值传递，在函数中操作切片时，可能改变切边中的元素，但是不会改变切片本身。