数组与切片

数组与切片有什么异同

切片的底层数据就是数组，是对数组的封装，描述一个数组的片段

相同点在于两者都是对顺序数据结构的一种表达，可以通过下标来访问元素

数组

数组是定长的，在初始化之后就无法改变

Go语言中只有存储元素类型和数组大小都相同才认为是同一类型

切片

切片可以理解为是动态数组，切片的类型与长度无关

数组就是一片连续的内存，切片实际上是一个结构体，包含三个字段：长度、容量、底层数组指针

1
2
3
4
5
6
7
8
9
// runtime/slice.go
type slice struct {
    // 底层数组的指针
	array unsafe.Pointer
    // 长度
	len   int
    // 容量
	cap   int
}

slice结构示意图

1711180039754

底层数组是可以被多个slice同时引用的，因此，对一个slice的元素进行操作可能影响其他slice

代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package main

import "fmt"

func main() {
	slice := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
	s1 := slice[2:5]
	s2 := s1[2:6:7]

	s2 = append(s2, 100)
	s2 = append(s2, 200)

	s1[2] = 20

	fmt.Println(s1)
	fmt.Println(s2)
	fmt.Println(slice)
}

以上代码的输出结果

1
2
3
[2 3 20]
[4 5 6 7 100 200]
[0 1 2 3 20 5 6 7 100 9]

特殊切片

根据数组或切片生成新的切片一般使用以下方式

1
slice := array[start:end]

这种生成方式没有指定切片的容量，那么这个切片容量就是从start开始一直到array结束

代码示例

1
2
3
4
5
6
7
8
9
package main

import "fmt"

func main() {
    arr := [5]int{0, 1, 2, 3, 4}
    s1 := arr[2:4]
    fmt.Printf("s1: %v, len(s1): %d, cap(s1): %d\n", s1, len(s1), cap(s1))
}

以上代码运行结果

运行结果
1
s1: [2 3], len(s1): 2, cap(s1): 3

根据数组或切片生成切片还有另一种写法，即切片的同时也指定容量

1
slice := array[start:end:max]

切片长度和容量的计算公式如下

len(slice)==end-start

cap(slice)==max-start

三个参数之间满足以下关系

start<=end<=max<=len(arr)-1

max的值必须大于等于end且不能大于底层数组的索引最大值

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package main

import "fmt"

func main() {
    arr := [5]int{0, 1, 2, 3, 4}
    s1 := arr[2:4:5]
    // 6大于数组的索引最大值，这里编译期就会报错
    // s2 := arr[2:4:6]
    fmt.Printf("s1: %v, len(s1): %d, cap(s1): %d\n", s1, len(s1), cap(s1))

    s1 = make([]int, 0, 10)
    s1 = append(s1, 0, 1, 2, 3, 4)
    // s1底层数组长度，即cap为10，所以8没有问题
    s2 := s1[2:4:8]
    fmt.Printf("s2: %v, len(s2): %d, cap(s2): %d\n", s2, len(s2), cap(s2))
}

运行结果
1
2
s1: [2 3], len(s1): 2, cap(s1): 3
s2: [2 3], len(s2): 2, cap(s2): 6

切片扩容

1.17及之前的版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// runtime/slice.go
// growslice handles slice growth during append.
// It is passed the slice element type, the old slice, and the desired new minimum capacity,
// and it returns a new slice with at least that capacity, with the old data
// copied into it.
// ...
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 {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newcap && newcap < cap {
				newcap += newcap / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
				newcap = cap
			}
		}
	}
    
    // ...
}
函数参数解析

cap：期望扩容到的最小容量

1
2
s1 := []int{1}
s1 = s1.append(s1, 2, 3, 4)

比如这里s1需要追加3个元素，容量不足需要触发扩容，新切片的最小容量就是1+3=4，故对应cap参数为4

预估容量
  • 如果期望容量（cap）大于当前容量的两倍（doublecap）就会使用期望容量
  • 如果当前切片的容量（old.cap）小于1024就会将容量翻倍
  • 如果当前切片的容量（old.cap）大于1024就会每次增加25%的容量，直到新容量大于期望容量（并不是扩容1/4哦 ）

上述扩容逻辑只是确定了切片的大致容量（仅仅是扩容逻辑的上半部分），接下来还需要根据切片中的元素大小对齐内存，根据切片中元素所占字节大小走不同的分支逻辑进行内存对齐

内存对齐

上半部分确定了一个基准的扩容容量，接下来下半部分需要计算内存大小并且判断是否需要内存对齐来确定最终扩容后的容量大小

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
func growslice(et *_type, old slice, cap int) slice {
    // ...
    // 到这已经得到newcap（大致容量）大小，接下来的代码需要根据内存对齐的情况来确定最终的cap大小来创建新的底层数组
    var overflow bool
	var lenmem, newlenmem, capmem uintptr
	// Specialize for common values of et.size.
	// For 1 we don't need any division/multiplication.
	// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
	// For powers of 2, use a variable shift.
	switch {
	case et.size == 1:
		lenmem = uintptr(old.len)
		newlenmem = uintptr(cap)
		capmem = roundupsize(uintptr(newcap))
		overflow = uintptr(newcap) > maxAlloc
		newcap = int(capmem)
	case et.size == sys.PtrSize:
		lenmem = uintptr(old.len) * sys.PtrSize
		newlenmem = uintptr(cap) * sys.PtrSize
		capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
		overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
		newcap = int(capmem / sys.PtrSize)
	case isPowerOfTwo(et.size):
		var shift uintptr
		if sys.PtrSize == 8 {
			// Mask shift for better code generation.
			shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
		} else {
			shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
		}
		lenmem = uintptr(old.len) << shift
		newlenmem = uintptr(cap) << shift
		capmem = roundupsize(uintptr(newcap) << shift)
		overflow = uintptr(newcap) > (maxAlloc >> shift)
		newcap = int(capmem >> shift)
	default:
		lenmem = uintptr(old.len) * et.size
		newlenmem = uintptr(cap) * et.size
		capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
		capmem = roundupsize(capmem)
		newcap = int(capmem / et.size)
	}

	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: cap out of range"))
	}

	var p unsafe.Pointer
	if et.ptrdata == 0 {
		p = mallocgc(capmem, nil, false)
		
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		p = mallocgc(capmem, et, true)
		if lenmem > 0 && writeBarrier.enabled {
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
		}
	}
	memmove(p, old.array, lenmem)

	return slice{p, old.len, newcap}
}

代码分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
package main

import "fmt"

/*
切片扩容
*/

func main() {
    s1 := []int{1, 2}
    fmt.Printf("[before] s1: %v, len(s1): %d, cap(s1): %d\n", s1, len(s1), cap(s1))
    s1 = append(s1, 3, 4, 5)
    fmt.Printf("[after] s1: %v, len(s1): %d, cap(s1): %d\n", s1, len(s1), cap(s1))
}

根据上面规则分析，先对容量进行预估

  • append之前：len(s1)==2，cap(s1)==2
  • append之后：由于切片容量已经用完，会触发扩容，扩容后len(s1)==5，cap(s1)==5

确定了预估容量为5，即newcap=5

运行结果
1
2
[before] s1: [1 2], len(s1): 2, cap(s1): 2
[after] s1: [1 2 3 4 5], len(s1): 5, cap(s1): 6

切片作为函数参数

slice本质是一个结构体，包含三个成员属性：len，cap，array

当slice作为函数参数时，就是一个普通的结构体，直接传递slice，实参是不会被函数中的操作改变的，但是如果传的是slice指针，尽管Go并没有引用传递（都是值传递），但是因为指针实际指向的数据相同，所以函数内部的操作会影响实参

什么是值传递，什么是引用传递

先说结论，Go语言中只有值传递，没有引用传递

值传递：形参都是实参的拷贝，函数内外参数的地址值是不同的

引用传递：那自然和值传递相反了，形参实参完全相同，就是一份数据

明确了值传递和引用传递后，再来看以下代码的执行结果

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
package main

import (
    "fmt"
)

/*
slice作为函数参数传递
*/

func main() {
    s := []int{1, 1, 1}
    // &s: 切片本身地址（指向切片这个结构体的指针）
    // s: 切片指向的底层数组地址
    // &s[0]: 切片指向的底层数组地址（数组是一片连续的地址空间，数组地址即为起始元素的地址）
    fmt.Printf("[function main] &s: %p, s: %p, &s[0]: %p\n", &s, s, &s[0])
    f(s)
    fmt.Println(s)
}

func f(s []int) {
    fmt.Printf("[function f] &s: %p, s: %p, &s[0]: %p\n", &s, s, &s[0])
    for i := range s {
        s[i] += 1
    }
}
运行结果
1
2
3
[function main] &s: 0xc000096060, s: 0xc0000ae078, &s[0]: 0xc0000ae078
[function f] &s: 0xc000096090, s: 0xc0000ae078, &s[0]: 0xc0000ae078
[2 2 2]

为什么函数内部的修改生效了

从函数内外对切片地址的打印结果来看，Go参数传递就是值传递

那么为什么能对函数外部的切片产生影响？

原因在于切片本身也是保存了底层数组的指针，值传递的过程本质就是一个拷贝（浅拷贝），对于引用类型的（保存指针）的参数来说它的值就是地址（只不过这个地址又是指向的另一个空间/变量）

所以这里的修改对函数外部生效

包括其他类型，如map、channel等都是同一个原理

陷阱

既然是因为底层数组的原因导致的修改生效，那么是否在函数内部触发了扩容（底层数组地址变更），修改就不生效了？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
package main

import (
    "fmt"
)

/*
slice作为函数参数传递
*/

func main() {
    s := []int{1}
    // &s: 切片本身地址（指向切片这个结构体的指针）
    // s: 切片指向的底层数组地址
    // &s[0]: 切片指向的底层数组地址（数组是一片连续的地址空间，数组地址即为起始元素的地址）
    fmt.Printf("[function main] &s: %p, s: %p, &s[0]: %p\n", &s, s, &s[0])
    f(s)
    fmt.Println(s)
}

func f(s []int) {
    fmt.Printf("[function f, before growing] &s: %p, s: %p, &s[0]: %p\n", &s, s, &s[0])
    s = append(s, 2, 3, 4)
    fmt.Printf("[function f, after growing] &s: %p, s: %p, &s[0]: %p\n", &s, s, &s[0])
}
运行结果
1
2
3
4
[function main] &s: 0xc000004078, s: 0xc000012098, &s[0]: 0xc000012098
[function f, before growing] &s: 0xc0000040a8, s: 0xc000012098, &s[0]: 0xc000012098
[function f, after growing] &s: 0xc0000040a8, s: 0xc0000101c0, &s[0]: 0xc0000101c0
[1]

并发支持

slice没有做并发控制，并发环境下是不安全的，但是多个goroutine操作可能并不会出现问题

而map则不同，运行时若检测到同一个map同时被多个goroutine引用并操作，程序会直接崩溃（如果刚好错开，则不会出现问题）

参考资料

Go 语言数组的实现原理 | Go 语言设计与实现 (draveness.me)

Go 语言切片的实现原理 | Go 语言设计与实现 (draveness.me)

切片的容量是怎样增长的 | Go 程序员面试笔试宝典 (golang.design)

slice_哔哩哔哩_bilibili