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 运行时的数据结构是 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]