golang slice 最后一个元素_Go 常见的数据结构 Slice

<figure style="text-align:center;"></figure>

Slice 又称动态数组，依托数组实现，可以方便的进行扩容，传递等，实际使用中比数组更灵活。

因为灵活，所以要了解其内部实现机制，不然会遇到各种莫名的异常现象。所以，今天来了解下 Slice 的实现原理。

<h2><span style="font-weight:bold;"/>1、热身</h2> <h3><span style="font-weight:bold;"/>1.1、题目一<span style="font-weight:bold;"/></h3>

下面程序输出什么？

<pre class="has"><code>func main()  {
 var array [10]int

 var slice = array[5:6]

 fmt.Println("length of slice:", len(slice))
 fmt.Println("cap of slice:", cap(slice))
 fmt.Println(&slice[0] == &array[5])
}
</code></pre>

输出结果：

<pre class="has"><code>len of slice: 1
cap of slice: 5
true
</code></pre>

程序解释：mian 函数中定义了一个长度为 10 的整型数组 array，然后定义了一个切片 slice，切取数组的第 6 个元素，最后打印 slice 的长度和容量，判断切片的第一个元素和数组的第 6 个元素地址是否相等。

答案解析：slice 根据数组 array 创建，与数组共享存储空间，slice 起始位置是 array[5],长度为 1，容量为 5，slice[0]和 array[5]地址相同。

<h3><span style="font-weight:bold;"/>1.2、题目二<span style="font-weight:bold;"/></h3>

下面程序输出什么？

<pre class="has"><code>func AddElement(slice []int, num int) []int {
 return append(slice, num)
}

func main() {
 var slice []int

 slice = append(slice, 1, 2, 3)

 newSlice := AddElement(slice, 4)

 fmt.Println(&slice[0] == &newSlice[0])
</code></pre>

输出结果：

<pre class="has"><code>true
</code></pre>

程序解释：函数 AddElement() 接受一个切片和一个元素，把元素 append 进切片中，并返回切片。mian() 函数中定义一个切片，并向切片中 append 3 个元素，接着调用 AddElement() 继续向切片 append 进第 4 个元素同时定义一个新的切片 newSlice。最后判断新切片 newSlice 与旧切片 slice 是否共用一块内存空间。

答案解析：append 函数执行时会判断切片容量是否能够存放新元素，如果不能，则会重新申请存储空间，新存储空间将是原来的 2 倍或者 1.25 倍(取决于扩展原空间大小)，本例中实际执行了两次 append 操作，第一次空间增长到 4，所以第二次 append 不会在扩容，所以新旧两个切片将共用一块存储空间。程序会输出"true"。

<h3><span style="font-weight:bold;"/>1.3、题目三<span style="font-weight:bold;"/></h3>

下面程序输出什么？

<pre class="has"><code>func main() {
 orderLen := 5
 order := make([]uint16, 2 * orderLen)

 pollOrder := order[:orderLen: orderLen]

 lockOrder := order[orderLen:][:orderLen:orderLen]

 fmt.Println("len(pollOrder) = ", len(pollOrder))
 fmt.Println("cap(pollOrder) = ", cap(pollOrder))

 fmt.Println("len(lockOrder) = ", len(lockOrder))
 fmt.Println("cap(lockOrder) = ", cap(lockOrder))
}
</code></pre>

输出结果：

<pre class="has"><code>len(pollOrder) =  5
cap(pollOrder) =  5
len(lockOrder) =  5
cap(lockOrder) =  5
</code></pre>

程序解释：程序中定义一个长度为 10 的切片 order，pollOrder 和 lockOrder 分别是对 order 切片做了 order[low:hign:max]操作生成的切片，最后程序分别打印 pollOrder 和 lockOrder 的容量和长度。

答案解析：order[low:hign:max]操作的意思是对 order 进行切片，新切片范围是[low, hign]，新切片容量是 max。order 长度为 orderLen 的 2 倍，pollOrder 切片指的是 order 的前半部分切片，lockOrder 指的是 order 的后半部分切片，即原 order 分成了两段，所以，pollOrder 和 lockOrder 的长度和容量都是 orderLen,即 5。

<h2><span style="font-weight:bold;"/>2、Slice 实现原理</h2>

Slice 依托数组实现，底层数组对用户屏蔽，在底层数组容量不足时可以实现自动重分配并生成新的 Slice。

<h3><span style="font-weight:bold;"/>2.1 Slice 数据结构<span style="font-weight:bold;"/></h3> <pre class="has"><code>type slice struct {
 array unsafe.Pointer
 len   int
 cap   int
}
</code></pre>

从数据结构看 Slice 很清楚，array 指针指向底层数组，len 表示切片长度，cap 表示底层数组容量。

<h3><span style="font-weight:bold;"/>2.2、使用 make 创建 Slice<span style="font-weight:bold;"/></h3>

使用 make 创建 Slice 时，可以同时指定长度和容量，创建时底层会分配一个数组，数组的长度即容量。

例如：

<pre class="has"><code>slice := make([]int, 5, 10)
</code></pre>

该 Slice 长度为 5，即可以使用下标 slice[0] ~ slice[4]来操作里面的元素，capacity 为 10，表示后续向 Slice 添加新的元素时可以不必重新分配内存，直接使用预留内存即可。

<h3><span style="font-weight:bold;"/>2.3、 使用数组创建 Slice<span style="font-weight:bold;"/></h3>

使用数组来创建 Slice 时，Slice 将与原数组共用同一部分内存。

<pre class="has"><code>func main() {
 var array [10]int

 slice := array[5:7]
}
</code></pre>

切片从数组 array[5]开始，到数组 array[7]结束(不含有 array[7]),即切片长度为 2，数组后面的内容都作为切片的预留内存，即 capacity 为 5。

<h3><span style="font-weight:bold;"/>2.4、Slice 扩容<span style="font-weight:bold;"/></h3>

使用 append 向 Slice 追加元素时，如果 Slice 空间不足，将会触发 Slice 扩容，扩容实际上重新分配一块大的内存，将原来 Slice 数据拷贝进新的 Slice，然后返回新的 Slice，扩容后再将数据追加进去。

例如，当向一个 cap 为 5，且 len 也为 5 的 Slice 再次追加 1 个元素时，就会发生扩容。

扩容操作只关心容量，会把原 Slice 数据拷贝到新 Slice，追加数据由 append 在扩容结束后完成。看上面的例子，扩容后新的 Slice 长度仍然是 5，但容量由 5 提升到了 10，原 Slice 的数据也都拷贝到了新 Slice 指向的数组中。

扩容容量的选择遵循以下规则：

<ul><li>如果原 Slice 容量小于 1024，则新 Slice 容量将扩大为原来的 2 倍。</li><li>如果原 Slice 容量大于等于 1024，则新 Slice 容量将扩大为原来的 1.25 倍。</li></ul>

使用 append() 向 Slice 添加一个元素的实现步骤：

<ul><li>假如 Slice 容量够用，则将新元素追加进去，Slice.len ，返回原 Slice。</li><li>原 Slice 容量不够，则将 Slice 先扩容，扩容后得到新 Slice。</li><li>将新元素追加进新 Slice，Slice.len ，返回新的 Slice。</li></ul><h3><span style="font-weight:bold;"/>2.5、Slice 复制<span style="font-weight:bold;"/></h3>

使用 copy()内置函数拷贝两个切片时，会将原切片的数据逐个拷贝到目的切片指向的数组中，拷贝数量取两个切片长度的最小值。

例如，长度为 10 的切片拷贝到长度为 5 的切片时，将会拷贝 5 个元素。也就是说，copy 过程不会发生扩容。

<h3><span style="font-weight:bold;"/>2.6、特殊切片<span style="font-weight:bold;"/></h3>

根据数组或者切片生成新的切片一般使用 slice := array[start:end] 方式，这种新生成的切片并没有指定切片的容量，实际上新切片的容量是从 start 开始直至 array 结束。

比如下面两个切片，长度和容量都是一致的，使用共同的内存地址：

<pre class="has"><code>sliceA := make([]int, 5, 10)
sliceB := sliceA[0:5]
</code></pre>

根据数组或者切片生成切片还有另一种写法，即切片同时也指定容量，slice[start:end:cap]，其中 cap 即为新切片的容量，当然容量不能超过原切片实际值，如下所示：

<pre class="has"><code>sliceA := make([]int, 5, 10) // len = 5; cap = 10
sliceB := sliceA[0:5]        // len = 5; cap = 10
sliceC := sliceA[0:5:5]      // len = 5; cap = 5
</code></pre>

这些切片方法不常见，在 Golang 源码里能够见到，不过非常利于切片的理解。

<h2><span style="font-weight:bold;"/>3、Slice 编程技巧</h2> <ul><li>创建切片时可根据实际需要预分配容量，尽量避免追加过程中扩容操作，有利于提升性能。</li><li>切片拷贝时需要判断实际拷贝的元素个数。</li><li>谨慎使用多个切片操作同一个数组，以防读写冲突。</li></ul><h2><span style="font-weight:bold;"/>4、Slice 总结</h2> <ul><li>每个切片都指向一个底层数组。</li><li>每个切片都保存了当前切片的长度、底层数组可用容量。</li><li>使用 len() 计算切片长度时间复杂度为 O(1)，不需要遍历切片。</li><li>使用 cap() 计算切片容量时间复杂度为 O(1)，不需要遍历切片。</li><li>通过函数传递切片时，不会拷贝整个切片，因为切片本身只是个结构体。</li><li>使用 append() 向切片追加元素时有可能触发扩容，扩容后将会生成新的切片。</li></ul>