Golang-常见数据结构Slice_golang slice结构体

Slice

slice 翻译成中文就是切片，它和数组（array）很类似，可以用下标的方式进行访问，如果越界，就会产生 panic。但是它比数组更灵活，可以自动地进行扩容。

了解 slice 的本质, 最简单的方法就是看它的源码:

// runtime/slice.go
type slice struct {
    array unsafe.Pointer // 元素指针
    len   int // 长度 
    cap   int // 容量
}

1
2
3
4
5
6
7

slice 共有三个属性:

1. 指针 指向底层数组
2. 长度 表示切片可用元素的个数，也就是说使用下标对 slice 的元素进行访问时，下标不能超过 slice 的长度
3. 容量 底层数组的元素个数，容量 >= 长度。在底层数组不进行扩容的情况下，容量也是 slice 可以扩张的最大限度。

注意: 底层数组是可以被多个 slice 同时指向的，因此对一个 slice 的元素进行操作是有可能影响到其他 slice 的。

slice 创建

直接声明

第一种创建出来的 slice 其实是一个 nil slice。它的长度和容量都为0。和nil比较的结果为true。

这里比较混淆的是empty slice，它的长度和容量也都为0，但是所有的空切片的数据指针都指向同一个地址 0xc42003bda0。空切片和 nil 比较的结果为false。

nil 切片和空切片很相似，长度和容量都是0，官方建议尽量使用 nil 切片。

关于nil slice和empty slice的探索可以参考 - 深度解析 Go 语言中「切片」的三种特殊状态

字面量

比较简单，直接用初始化表达式创建。

package main

import "fmt"

func main() {
    s1 := []int{0, 1, 2, 3, 8: 100}
    fmt.Println(s1, len(s1), cap(s1))
}
1
2
3
4
5
6
7
8

运行结果：
[0 1 2 3 0 0 0 0 100] 9 9

唯一值得注意的是上面的代码例子中使用了索引号，直接赋值，这样，其他未注明的元素则默认 0 值

make

make 函数需要传入三个参数：切片类型，长度，容量。当然，容量可以不传，默认和长度相等。

使用 make 关键字创建 slice:

packge main
import "fmt"

func main(){
    // 长度为 5, 容量为 10
    slice := make(int[], 5, 10)
    // 索引为 2 的元素赋值为 2
    slice[2] = 2 
    fmt.Println(slice)
}

1
2
3
4
5
6
7
8
9
10
11

截取

截取也是比较常见的一种创建 slice 的方法，可以从数组或者 slice 直接截取，当然需要指定起止索引位置。

基于已有 slice 创建新 slice 对象，被称为 reslice。新 slice 和老 slice 共用底层数组，新老 slice 对底层数组的更改都会影响到彼此。

基于数组创建的新 slice 对象也是同样的效果：对数组或 slice 元素作的更改都会影响到彼此。

值得注意的是，新老 slice 或者新 slice 老数组互相影响的前提是两者共用底层数组，如果因为执行 append 操作使得新 slice 底层数组扩容，移动到了新的位置，两者就不会相互影响了。所以，问题的关键在于两者是否会共用底层数组。

截取操作采用如下方式：

data := [...]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
// data[low, high, max]
slice := data[2:4:6] 
1
2
3

其他易错点

slice 和数组的区别在哪

slice 的底层数据是数组，slice 是对数组的封装，它描述一个数组的片段。两者都可以通过下标来访问单个元素。

数组是定长的，长度定义好之后，不能再更改。在 Go 中，数组是不常见的，因为其长度是类型的一部分，限制了它的表达能力，比如 [3]int 和 [4]int 就是不同的类型。

而切片则非常灵活，它可以动态地扩容。切片的类型和长度无关。

append 到底做了什么

先来看看 append 函数的原型：
func append(slice []Type, elems ...Type) []Type

append 函数的参数长度可变，因此可以追加多个值到 slice 中，还可以用 … 传入 slice，直接追加一个切片。

slice = append(slice, elem1, elem2)
slice = append(slice, anotherSlice...)
1
2

注: append函数返回值是一个新的slice，Go编译器不允许调用了 append 函数后不使用返回值。

slice 扩容

在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

大多数的文章都是这样描述的:

当原 slice 容量小于 1024 的时候，新 slice 容量变成原来的 2 倍；原 slice 容量超过 1024，新 slice 容量变成原来的1.25倍。

其实结论不太准确的

为了说明上面的规律是错误的，如下代码：

package main

import "fmt"

func main() {
    s := make([]int, 0)

    oldCap := cap(s)

    for i := 0; i < 2048; i++ {
        s = append(s, i)

        newCap := cap(s)

        if newCap != oldCap {
            fmt.Printf("[%d -> %4d] cap = %-4d  |  after append %-4d  cap = %-4d\n", 0, i-1, oldCap, i, newCap)
            oldCap = newCap
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

运行结果：

[0 ->   -1] cap = 0     |  after append 0     cap = 1   
[0 ->    0] cap = 1     |  after append 1     cap = 2   
[0 ->    1] cap = 2     |  after append 2     cap = 4   
[0 ->    3] cap = 4     |  after append 4     cap = 8   
[0 ->    7] cap = 8     |  after append 8     cap = 16  
[0 ->   15] cap = 16    |  after append 16    cap = 32  
[0 ->   31] cap = 32    |  after append 32    cap = 64  
[0 ->   63] cap = 64    |  after append 64    cap = 128 
[0 ->  127] cap = 128   |  after append 128   cap = 256 
[0 ->  255] cap = 256   |  after append 256   cap = 512 
[0 ->  511] cap = 512   |  after append 512   cap = 1024
[0 -> 1023] cap = 1024  |  after append 1024  cap = 1280
[0 -> 1279] cap = 1280  |  after append 1280  cap = 1696
[0 -> 1695] cap = 1696  |  after append 1696  cap = 2304
1
2
3
4
5
6
7
8
9
10
11
12
13
14

在老 slice 容量小于1024的时候，新 slice 的容量的确是老 slice 的2倍。目前还算正确。

但是，当老 slice 容量大于等于 1024 的时候，情况就有变化了。当向 slice 中添加元素 1280 的时候，老 slice 的容量为 1280，之后变成了 1696，两者并不是 1.25 倍的关系（1696/1280=1.325）。添加完 1696 后，新的容量 2304 当然也不是 1696 的 1.25 倍。

可见，现在网上各种文章中的扩容策略并不正确。我们直接搬出源码：源码面前，了无秘密。

从前面汇编代码我们也看到了，向 slice 追加元素的时候，若容量不够，会调用 growslice 函数，所以我们直接看它的代码。

// go 1.9.5 src/runtime/slice.go:82
func growslice(et *_type, old slice, cap int) slice {
    // ……
    newcap := old.cap
    doublecap := newcap + newcap
    if cap > doublecap {
        newcap = cap
    } else {
        if old.len < 1024 {
            newcap = doublecap
        } else {
            for newcap < cap {
                newcap += newcap / 4
            }
        }
    }
    // ……

    capmem = roundupsize(uintptr(newcap) * ptrSize)
    newcap = int(capmem / ptrSize)
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

看到了吗？如果只看前半部分，现在网上各种文章里说的 newcap 的规律是对的。现实是，后半部分还对 newcap 作了一个内存对齐，这个和内存分配策略相关。进行内存对齐之后，新 slice 的容量是要 大于等于 老 slice 容量的 2倍或者1.25倍。

之后，向 Go 内存管理器申请内存，将老 slice 中的数据复制过去，并且将 append 的元素添加到新的底层数组中。

为什么 nil slice 可以直接 append

其实 nil slice 或者 empty slice 都是可以通过调用 append 函数来获得底层数组的扩容。最终都是调用 mallocgc 来向 Go 的内存管理器申请到一块内存，然后再赋给原来的nil slice 或 empty slice，然后摇身一变，成为“真正”的 slice 了。

总结

• 切片是对底层数组的一个抽象，描述了它的一个片段。
• 切片实际上是一个结构体，它有三个字段：长度，容量，底层数据的地址。
• 多个切片可能共享同一个底层数组，这种情况下，对其中一个切片或者底层数组的更改，会影响到其他切片。
• append 函数会在切片容量不够的情况下，调用 growslice 函数获取所需要的内存，这称为扩容，扩容会改变元素原来的位置。
• 扩容策略并不是简单的扩为原切片容量的 2 倍或 1.25 倍，还有内存对齐的操作。扩容后的容量 >= 原容量的 2 倍或 1.25 倍。
• 当直接用切片作为函数参数时，可以改变切片的元素，不能改变切片本身；想要改变切片本身，可以将改变后的切片返回，函数调用者接收改变后的切片或者将切片指针作为函数参数。

参考

深度解密Go语言之Slice