slice 实现原理
slice 中文多译为切片,是 Go 语言在数组之上的一个重要抽象数据类型。切片是一个引用类型,它的内部结构包含地址、大小和容量。 对于大多数使用数组的场合,切片都可以实现了完美替代。
什么是切片
在此之前,先简单了解一下 Go 语言中的数组。Go 语言中的数组是一个容纳同构类型元素的序列。数组的长度是固定的,不能动态增长。
Go 数组是值语义,这意味着一个数组变量表示的是整个数组。而在 Go 语言中传递数组是纯粹的值拷贝。如果要在函数中传递数组,可以传递数组的指针。 但这是 C 语言的惯用法,在 Go 语言中,更地道的方式是使用切片。
切片之于数组就像是文件描述符之于文件。我们可以称切片是数组的“描述符”
切片在 Go 运行时(runtime)层面的内部表示:
type slice struct {
array unsafe.Pointer
len int
cap int
}
切片的内部结构包含了指向底层数组的指针、切片的长度和切片的容量。切片的容量是从切片的开始位置到底层数组的结束位置的数量。
当切片作为函数参数传递给函数时,实际传递的是切片的内部表示,而不是切片的副本。因此在函数中对切片的修改,将会影响到函数外部的切片。 另外,切片作为参数传递带来的性能损耗也是微乎其微的。所以在函数中多使用切片而不是数组。另外一个原因是切片可以提供比指针更为强大的功能, 比如下标访问,边界溢出校验,动态扩容等等。
动态扩容
切片的容量是从切片的开始位置到底层数组的结束位置的数量。切片的长度是切片开始位置到结束位置的数量。切片的长度和容量可以通过内置的 len()
和 cap()
函数获取。
另外,切片类型是满足零值可用的,即便没有初始化,也可以使用。此时切片的长度为 0,容量也为 0,底层数组指针为 nil。
为了方便查看切片是如何动态扩容的,我们每次打印 append
操作后的切片的长度和容量。
var s []int
s = append(s, 1)
println(len(s), cap(s)) // 1 1
s = append(s, 2)
println(len(s), cap(s)) // 2 2
s = append(s, 3)
println(len(s), cap(s)) // 3 4
s = append(s, 4)
println(len(s), cap(s)) // 4 4
s = append(s, 5)
println(len(s), cap(s)) // 5 8
我们可以看到 append
会根据切片的需要,在当前底层数组容量不够的情况下,动态分配新的数组,新数组长度会按照一定的算法扩展(参见$GOROOT/src/runtime/slice.go
中的growslice
函数)。
新数组建立后,将原有的元素和新元素一起拷贝到新数组中,之后新数组便成为切片的底层数组。旧数组后续会被垃圾回收掉。
如果我们通过语法 u[low: high]
形式进行数组切片化而创建的切片,那么新切片的容量是 u
的容量减去 low
之后的长度。如果切片容量触碰到数组的上界,再对切片进行 append
操作,切片就会和原数组进行解除绑定。
尽量使用 cap
在使用 make
函数创建切片时,可以通过指定 cap
参数来指定切片的容量。如果我们知道切片的容量,那么在切片进行动态扩容时,就可以避免多次扩容带来的性能损耗。
s := make([]T, len, cap)