2. 数组上: 深入理解 slice

注：本文已发布超过一年，请注意您所使用工具的相关版本是否适用

序

  • Go 数据结构与算法系列文章，本系列文章主要会包括常见的数据结构与算法实现，同时会包括 Go 标准库代码的分析理解，讲到对应章节的时候优先学习分析 Go 的源码实现，例如 slice、list、sort 等，然后可能会有一些常见的案例实现，同时这也是 极客时间-数据结构与算法之美 的课程笔记
  • 本文代码仓库: https://github.com/mohuishou/go-algorithm 🌟🌟🌟🌟🌟
  • **RoadMap: **持续更新中，预计一周更新 1 ~ 2 篇文章，预计到 202101 月底前更新完成
  • 获取更新: Github、知乎、RSS、开发者头条
  • 上一个系列刚刚完成了 Go 设计模式，如果感兴趣也可以进行查看

上期答案

Q: 通过 Element 节点中的 List 结构来判断节点是否属于当前链表的方式，在某些情况下会出现  bug

1
2
3
4
5
6
l := list.List{}
e := l.PushBack(10)

l = list.List{}
l.Remove(e)
fmt.Println("list len: ", l.Len())

接着看下面之前，先想一想，你觉得这段代码会输出什么？
这个问题来自: https://github.com/golang/go/issues/39014
这段代码会输出 -1，但是我们期望的不应该是输出 0 么？
我们来看看发生了什么？
01_链表.drawio.svg

  • 当我们执行完 l.PushBack(10)  这段代码直接，就如左图所示了，节点 e 指向了链表 l，链表 l 的值的长度是 1
  • 但是当我们执行完 l = list.List{}  我们重置了链表 l 的值，并没有修改他的地址，所以 e 还是指向的链表 l，当执行 Remove  方法的时候，e 的链表和当前执行的 l 的地址判断是可以对应的上的，但是实际上链表的值已经发生了变化，链表的长度已经不为 1 的，并且新的链表的根节点也没有指向 e
  • 所以最后得到的长度才是 -1
  • 最后细心的同学应该已经发现，这里其实还可能存在内存泄漏的问题，元素 e -> root(0x2) 其实已经没有用到了

什么是数组？

  • 数组大家应该都非常属性我们来简单的回顾一下
  • 数组是一个具有连续的内存空间和相同类型的数据的数据结构
  • 我们随机访问任意一个下标的数据的时间复杂度都是 O(1)
  • 但是正是由于这种特性，导致它插入和删除元素的效率比较低，是 O(n)

01_array.drawio.svg

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
func main() {
	// 初始化数组
	var arr = [3]int{1, 2, 3}
	// 查找元素
	fmt.Printf("arr[1]: %d\n", arr[1])
	// 删除元素
	remove(&arr, 2)
	// remove(&arr, 3) // will panic
	fmt.Println(arr)
}

// 删除数组 arr 的某个元素
// index 为需要删除的索引
// 从需要删除的元素开始，依次将后面的元素往前移动一位即可
// 然后将最后一位修改为该类型的默认值
func remove(arr *[3]int, index int) {
	if index >= len(arr) {
		log.Panicf("%d remove out range arr", index)
	}
	for i := index; i < len(arr)-1; i++ {
		arr[i] = arr[i+1]
	}
	arr[len(arr)-1] = 0
}

Q: 为什么我们在 remove 函数当中的参数使用的是指针

这是因为在 go 中参数的传递都是值传递，如果不用指针的话，那么就会复制一份数据到函数中，这样就无法做到删除的作用

1
2
3
4
5
6
7
8
9
10
11
12
// 在函数 main 中
fmt.Printf("main: %p --> %+v\n", &arr, arr)
p(arr)
p2(&arr)

func p(arr [3]int) {
	fmt.Printf("p: %p --> %+v\n", &arr, arr)
}

func p2(arr *[3]int) {
	fmt.Printf("p2: %p --> %+v\n", arr, arr)
}

输出:

1
2
3
main: 0xc0000c2000 --> [1 2 0]
p: 0xc0000c2080 --> [1 2 0]
p2: 0xc0000c2000 --> &[1 2 0]

通过上面的例子我们就可以发现，在函数 p 中我们直接传递的数组，最后打印的变量地址是和 main 中不同的，就印证了我们之前的说法
在实际使用过程中，我们其实是很少使用到固定长度的数组的，而是使用可以自动扩容的 slice，接下来我们就深入的看一下 slice 当中的一些细节

深入理解 Slice

使用

基础使用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 初始化
s1 := make([]int, 2)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [0 0], len: 2, cap: 2

// 赋值
s1[0] = 1
s1[1] = 2
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
//	s1(0xc00000c080): [1 2], len: 2, cap: 2

// 扩容
s1 = append(s1, 3)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 2 3], len: 3, cap: 4

// 删除元素
s1 = append(s1[:1], s1[2:]...)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 3], len: 2, cap: 4
  • 可以发现，通过 append 之后 s1 的容量和长度都发生了变化，说明完成了自动扩容
  • 删除元素之后我们的长度发生了变化，但是容量还是原本不变

常见坑

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 复制一个 slice
s2 := s1[:2]
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", &s2, s2, len(s2), cap(s2))
// s2(0xc00000c120): [1 3], len: 2, cap: 4

s1[0] = 10 // 这里可以发现，s1[0] s2[0] 都被修改为了 10
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [10 3], len: 2, cap: 4
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", &s2, s2, len(s2), cap(s2))
// s2(0xc00000c120): [10 3], len: 2, cap: 4

s1 = append(s1, 5, 6, 7, 8)
s1[0] = 11 // 这里可以发现，s1[0] 被修改为了 11, s2[0] 还是10
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", &s1, s1, len(s1), cap(s1))
// s1(0xc00011c020): [11 3 5 6 7 8], len: 6, cap: 8
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", &s2, s2, len(s2), cap(s2))
// s2(0xc00011c0c0): [10 3], len: 2, cap: 4
  • 这是一个常见的例子，我们从 s1 复制了一个 s2
  • 修改 s1 的第一个元素之后，s2 的一个元素也被修改了
  • 但是我们触发了 s1 的自动扩容之后，s2 的第一个元素就不会随着 s1 的修改而变化了
  • 这也是当函数的参数是 slice 时我们不允许直接修改，如果需要修改需要返回这个 slice 的原因，因为函数的参数也是值的复制
1
2
3
4
func sliceChange(s []int) {
	// 不允许直接这么操作
	s[0] = 1
}

结构

大家如果使用过一段时间 golang 应该知道 slice 的底层结构其实是一个 struct
https://github.com/golang/go/blob/go1.15/src/runtime/slice.go

1
2
3
4
5
type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

02_slice_struct.drawio.svg

  • 如图所示我们可以发现，slice 的底层结构是一个结构体
    • 它包含了一个指向一个数组的指针，数据实际上存储在这个指针指向的数组上
    • len 表示当前 slice 使用到的长度
    • cap 表示当前 slice 的容量，同时也是底层数组 array 的长度
  • 这也就回答了我们上面的发现的现象，在复制 slice 的时候，slice 中数组的指针也被复制了，在出发扩容逻辑之前，两个 slice 指向的是相同的数组，出发扩容逻辑之后指向的就是不同的数组了
  • 同时因为结构体中 array 是一个指针所以在 slice 作为参数传递的时候，这个指针也会被复制一份，所以也会有相同的问题

创建

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 创建一个 slice
// et: 数据的类型
// len: slice 长度
// cap: slice 容量
// 返回一个指针
func makeslice(et *_type, len, cap int) unsafe.Pointer {
    // 通过 cap 计算当前类型的 slice 需要的内存容量以及是否超出最大容量
	mem, overflow := math.MulUintptr(et.size, uintptr(cap))
    // 异常情况判断
	if overflow || mem > maxAlloc || len < 0 || len > cap {
		// 通过 len 计算当前类型的 slice 需要的内存容量以及是否超出最大容量
        // 如果是 len 超过限制则抛出 len 的相关异常，否则抛出 cap 异常
		mem, overflow := math.MulUintptr(et.size, uintptr(len))
		if overflow || mem > maxAlloc || len < 0 {
			panicmakeslicelen()
		}
		panicmakeslicecap()
	}

	return mallocgc(mem, et, true)
}

还有一个 64 位的

  • 64 位对比默认的只是进行了一下数据格式转换，但是这个转换的对比还是很有意思的
  • 如果是在 64 位的机器上，那么 int == int64 的
  • 如果是在 32 位的机器上，那么 int == int32，如果 int64(int(len64)) != len64，那么就说明这个长度超出了当前机器的内存位数，直接抛出异常错误就好了
1
2
3
4
5
6
7
8
9
10
11
12
13
func makeslice64(et *_type, len64, cap64 int64) unsafe.Pointer {
	len := int(len64)
	if int64(len) != len64 {
		panicmakeslicelen()
	}

	cap := int(cap64)
	if int64(cap) != cap64 {
		panicmakeslicecap()
	}

	return makeslice(et, len, cap)
}

扩容

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
63
64
65
66
67
68
69
70
71
72
73
74
// 当 append 需要扩容的时候会调用这个函数
// et 是当前 slice 的类型
// old 是原有的 slice
// cap 是满足扩容所需的最小容量
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 {
			// 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
			}
		}
	}

    // 下面去计算新的数组所需要的内存
    // 通过 old.len, cap, 以及 newcap 计算
	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)
	// ... 有好几个分支，看一个类似的就可以了
	}

	// 检查是不是超过内存限制
	if overflow || capmem > maxAlloc {
		panic(errorString("growslice: cap out of range"))
	}

    // 分配内存
	var p unsafe.Pointer
	if et.ptrdata == 0 {
		p = mallocgc(capmem, nil, false)
		// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
		// Only clear the part that will not be overwritten.
		memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
	} else {
		// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
		p = mallocgc(capmem, et, true)
		if lenmem > 0 && writeBarrier.enabled {
			// Only shade the pointers in old.array since we know the destination slice p
			// only contains nil pointers because it has been cleared during alloc.
			bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem-et.size+et.ptrdata)
		}
	}

    // 将原本的数组复制到新数组上
	memmove(p, old.array, lenmem)

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

我们重点看一下扩容的算法，可以发现有三种逻辑

  • 如果需要的最小容量比两倍原有容量大，那么就取需要的容量
  • 如果原有 slice 长度小于 1024 那么每次就扩容为原来的两倍
  • 如果原 slice 大于等于 1024 那么每次扩容就扩为原来的 1.25 倍
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {
    newcap = cap
} else {
    if old.len < 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
        }
    }
}

空 Slice

我们先看一下 Slice 初始化的方式

1
2
3
4
5
6
7
var s1 []int
s2 := make([]uint, 0)
s3 := []int{}
// fmt.Printf("%p: %v, len: %d, cap: %d\n", s1, s1, len(s1), cap(s1))
// 0x0: [], len: 0, cap: 0
// 0x587450: [], len: 0, cap: 0
// 0x587450: [], len: 0, cap: 0
  • tips: %p  打印 slice 会打印 slice 底层指向的数组的地址
  • 我们可以发现，第一种方式进行初始化，出现的也就是 slice 的零值，底层的数组指针是一个 nil
  • 第二种和第三种的底层指针都有一个值，不过没有实际分配内存
  • 这三种方式初始化出来的 cap、和 len 的长度都是 0

规范技巧

  1. slice 作为参数时，不要直接存储它的引用，而是通过 copy  复制一份
    1. 原因请查看上文，Slice 的结构
    2. 示例：Uber Go 规范: nil-是一个有效的-slice
  2. 要检查切片是否为空，请始终使用 len(s) == 0 。而非 nil 。
    1. 原因请查看上文，Slice 初始化
    2. 示例：Uber Go 规范: 在边界处拷贝-Slices-和-Maps

Question

  • 在讲解 slice 初始化的过程中，为什么 s2 , s3  打印的数组指针都是 0x587450 ?
  • 请查看下面一段代码，会输出什么，为什么？
    • A: 5 8 B: 8 8 C: 5 5 D: 5 6
1
2
3
4
5
6
7
8
9
10
11
package main

import (
	"fmt"
)

func main() {
	s := []int{1, 2}
	s = append(s, 3, 4, 5)
	fmt.Println(len(s), cap(s))
}

关注我获取更新

wechat
知乎
github

猜你喜欢