Go 数组与切片


十一月其一，学习 Go 的数组与切片。

本文不是扫盲文，不解答“什么是数组”，也不解答“Go 的语法是什么”。

数组

数组是所有编程语言必备的数据结构：一组相同类型的值，按照顺序存储在一起。我看到一种巧妙的形容：数组是一种同构的数据类型。（但似乎有些语言不要求相同类型？）

以下语句在 Go 中都是合法的：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
// 声明
var arr [10]int
var arr [10]string
var arr [10]*int
var arr [10]Person // 自定义结构体
var arr [10]interface{}
var arr [10][10]int

// 声明+初始化
arr := [10]int{}
arr := [10]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
arr := [10]int{1, 2, 3, 4, 5}
arr := [...]int{1, 2, 3, 4, 5}
arr := [...]string{2: "hello", 3: "pz"}

Go 的数组长度是固定的，非但如此，数组长度还是数组的一部分，[5]int 和 [10]int 是不同的类型。

Go 的数组长度必须是一个常量值，而不能是变量。

1
2
3
4
5
6
// 正确
arr := [5]int{}

// 错误
length := 5
arr := [length]int{}

Go 的数组变量，不是指向首地址的指针，而是代表整个数组。Go 的数组是一种值类型，跟 int、bool 等值类型一样。

Go’s arrays are values. An array variable denotes the entire array; it is not a pointer to the first array element (as would be the case in C). （节自《Go Slices: usage and internals》）

怎么理解 Go 的数组是值类型呢？Go 的数组是一个整体，拷贝数组/传递数组，会复制全部数据。

比如在函数调用时将数组作为参数传递，Java 传递一个指向数组地址的变量，而 Go 将拷贝出一个全新的数组（元素完全相同）。

1
2
3
4
5
6
7
8
9
10
11
// 这里是 Java
private void foo() {
    int[] arr = new int[5]{1, 2, 3, 4, 5};
    bar(arr);
    System.out.println(Arrays.toString(arr)); // 打印 [10, 2, 3, 4, 5]
}

private void bar(int[] arr) {
    // 此时 arr 和函数调用方的 arr 是同一个数组，传入的是指针
    arr[0] = 10;
}
1
2
3
4
5
6
7
8
9
10
11
12
// 这里是 Go
func foo () {
    arr := [5]int{1, 2, 3, 4, 5}
    bar(arr)
    fmt.Printf("%v", arr) // 打印 [1, 2, 3, 4, 5]
}

func bar(arr [5]int) {
    // 此时的 arr 不同于函数调用方的 arr
    // 函数调用方拷贝了一个数组，元素完全相同，传了进来
    arr[0] = 10
}

也就是说，Go 的数组是一个整体，拷贝数组/传递数组，会复制全部数据。


你也可以使用指针，这样传递数组时就无需拷贝整体。（但多数场景下没人这样做，大家都使用后文要写的切片）

Go 对指针做了优化，数组的指针也可以访问数组下标。

1
2
3
4
5
6
arr := [10]int{}
p := &arr

// 下面两行代码都是合法的
arr[0] = 1
p[0] = 1

切片

开发 Go 的代码时，几乎没有人使用数组，因为它用起来很不灵活，大家都使用切片（Slice）。

日常写代码时，数组和切片的区别是有没有指定长度，如果指定了长度就是数组（含 […]int 这种隐式指定），如果没有就是切片：

1
2
arr := [10]int{1, 2, 3} // 数组
slice := []int{1, 2, 3} // 切片

切片类似于 Java 中的 ArrayList，它的底层依旧是数组，但是它的长度可变，并且（粗略）是一个指针。

切片在 Go 运行时的数据结构是 reflect.SliceHeader，它由三部分组成 ：数组指针、长度、容量。

1
2
3
4
5
type SliceHeader struct {
   Data uintptr // 数组指针
   Len  int     // 长度（已经使用的数组长度）
   Cap  int     // 容量（数组的最大可用长度）
}

切片有很多初始化方式：

1
2
3
4
5
6
7
8
9
arr := [3]int{1, 2, 3}
slice := arr[1:2] // slice: [2]
slice := arr[1:]  // slice: [2 3]
slice := arr[:2]  // slice: [1 2]
slice := arr[:]   // slice: [1 2 3]

slice := []int{1, 2, 3}
slice := make([]int, 10)     // len == cap == 10
slice := make([]int, 10, 20) // len == 10, cap == 20

不同的初始化方式底层实现不一样，详细可参考博文《Go 语言切片的实现原理》。


切片使用 append() 方法扩增，例如 slice = append(slice, 1) 尾增加元素 1。

如果追加元素时，切片的长度不够用，切片会自动调用 runtime.growslice 方法扩容：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func growslice(et *_type, old slice, cap int) slice {
   // ...

   newcap := old.cap
   doublecap := newcap + newcap
   if cap > doublecap {
      newcap = cap
   } else {
      if old.cap < 1024 {
         newcap = doublecap
      } else {
         for 0 < newcap && newcap < cap {
            newcap += newcap / 4
         }
         if newcap <= 0 {
            newcap = cap
         }
      }
   }

   // ...
}

切片的扩容规则如下：

  1. 如果期望容量大于当前容量的两倍就会使用期望容量
  2. 如果当前切片的长度小于 1024 就会将容量翻倍
  3. 如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量

（这只是确认大致容量，除此之外还会根据元素大小对齐内存）


Go 还提供了拷贝切片的能力（虽然用不太上）：

1
2
3
4
5
6
7
slice1 := []int{1, 1, 1}
slice2 := []int{2, 2, 2, 2, 2}
copy(slice1, slice2) // slice1: [2 2 2], slice2: [2 2 2 2 2]

slice3 := []int{3, 3, 3}
slice4 := []int{4, 4, 4, 4, 4}
copy(slice4, slice3) // slice3: [3 3 3], slice4: [3 3 3 4 4]