likes
comments
collection
share

3. golang 切片详解（面试看这一篇就够了）

作者站长头像
站长
· 阅读数 49

前言

1.数据结构

slice 实际上是一个结构体，包含三个字段：长度、容量、底层数组。

  • array 是指向底层数组的指针；
  • len: 是切片的长度，即切片中当前元素的个数；
  • cap: 是底层数组的长度，也是切片的最大容量，cap 值永远大于等于 len 值。
// runtime/slice.go
type slice struct {
    array unsafe.Pointer // 元素指针
    len   int // 长度 
    cap   int // 容量
}

// 例子
var nums = make([]int, 3, 6)
nums[0], nums[1], nums[2] = 1, 2, 3

slice 的数据结构如下：

3. golang 切片详解（面试看这一篇就够了）

由于底层数组是一片连续的内存空间，所以我们可以将切片理解成一片连续的内存空间加上长度与容量的标识。

切片是对数组的封装，提供了对数组中部分连续片段的引用，在运行期间可以修改它的长度和范围，当底层数组长度不能满足当前切片容量时，切片就会更换指向的底层数组，而对于上层来说无感知。 注意：底层数组是可以被多个 slice 同时指向的，因此对一个 slice 的元素进行操作是有可能影响到其他 slice 的。

2.初始化

Go 编译器会自动为每个新创建的切片，建立一个底层数组，默认底层数组的长度与切片初始元素个数相同。我们可以用以下几种方法创建切片，并指定它底层数组的长度。

2.1 使用下标创建 slice

采用 array[low : high : max] 语法基于一个已存在的数组或切片创建新切片。

// 声明一个数组 [10]int 并赋值
arr := [10]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
// 使用数组创建切片
sl := arr[3:7:9]
// 使用切片创建切片
sl2 := sl[0:2:3]
fmt.Println(sl) // [4 5 6 7]
fmt.Println(sl2) // [4 5]

3. golang 切片详解（面试看这一篇就够了）

基于数组创建的切片，它的起始元素从 low 所标识的下标值开始，切片的长度（len）是 high - low = 7 -3 = 4，它的容量是 max - low = 9 - 3 = 6。

同理基于切片创建的切片，起始元素从 sl 的 0 开始，长度 = 2，容量 = 3，由于 sl 的容量为 6，因此 max 下标最大为 6，超过 6 则会运行报错：panic: runtime error: slice bounds out of range [::7] with capacity 6。

使用下标初始化切片不会拷贝原数组或者原切片中的数据，它只会创建一个指向原数组的切片结构体，所以修改新切片的数据也会修改原切片。由于切片 sl2 的底层数组也是数组 arr，对切片 sl2 中元素的修改将直接影响数组 arr 和 切片 s1 变量。

// 修改切片 sl2 的值
sl2[0] = 100
fmt.Println(sl2) // [100 5]
fmt.Println(sl) // [100 5 6 7]
fmt.Println(arr) // [1 2 3 100 5 6 7 8 9 10]

当然，我们还可以省略 array[low : high : max] 中的 max，则 max 值默认为数组的长度或切片的容量。

// 声明一个数组 [10]int 并赋值
arr := [10]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
// 使用数组创建切片
sl := arr[3:7]
fmt.Println(len(sl), cap(sl)) // 4 7
// 使用切片创建切片
sl2 := sl[0:2]
fmt.Println(len(sl2), cap(sl2)) // 2 7

省略 max 后，还可以继续省略 low 或 high，或者全部省略都是可以的。

  • [:] 表示截取全部的数组或切片作为新切片 [0:max)
  • [:high] 截取 [0,high) 的数组或切片作为新切片
  • [low:] 截取 [low,max) 的数组或切片作为新切片

2.2 使用字面量直接创建切片

Go 支持使用字面量直接创建新的切片，此时 Go 在编译期间会根据切片中元素数量创建一个底层数组，将元素存储到数组中，然后使用 [:] 创建切片，这就又回到了 2.1 小节的创建方式。

sl3 := []int{1, 2, 3, 4, 5, 6, 7}

2.3 使用关键字 make 创建 slice

// 其中 14 为 cap 值，即底层数组长度，7 为切片的初始长度
sl4 := make([]byte, 7, 14) 
fmt.Println(sl4) // [0 0 0 0 0 0 0]
// 不指定 cap 值时，cap = len = 7
sl5 := make([]byte, 7) 
fmt.Println(len(sl5), cap(sl5)) // 7 7

使用 make 创建 slice make([]Type, len, cap)

  • 可以省略 cap，默认等于 len；
  • cap >= len >= 0 的条件必须成立；
  • len > 0 时，slice 填充类型的零值。

3.常用方法

  • len：返回 slice 中元素的数量。
arr := [5]int{1,2,3,4,5}
// 省略 max
sl := arr[2:4]
fmt.Println(len(sl)) // 2
  • cap：返回 slice 的容量。
fmt.Println(cap(sl)) // 3
  • append：向 slice 中追加一个或多个元素，然后返回新的 slice。
    • append 函数的参数长度可变，因此可以追加多个值到 slice 中，还可以用 ... 传入 slice，直接追加一个切片。
    • append 函数返回值是一个新的 slice，并且对传入的 slice 不影响。Go编译器不允许调用了 append 函数后不使用返回值，会触发编译错误。
    • 使用 append 可以向 slice 追加元素，实际上是往底层数组添加元素，因此会影响底层数组。
    • 当切片达到容量上限，再次 append 元素时，会触发切片的动态扩容机制，返回的 slice 会指向新的底层数组，与原底层数组解绑，此时不再影响原底层数组，这里需要额外注意。
// append 函数
func append(slice []Type, elems ...Type) []Type

slice = append(slice, elem1, elem2)
slice = append(slice, anotherSlice...)
append(slice, elem1, elem2) // 会引发编译错误

// 感兴趣的，可以自己分析一下输出结果
s := []int{5}
s = append(s, 7)
s = append(s, 9)
x := append(s, 11)
y := append(s, 12)
fmt.Println(s, x, y)

// 输出结果：[5 7 9] [5 7 9 12] [5 7 9 12]
  • copy：从源 slice（src） 中复制元素到目标 slice（dist），并且返回复制的元素的个数。拷贝为深拷贝 src 改变不会影响 dist。
arr := [4]int{1, 2, 3, 4}
sl := arr[:]
sl2 := make([]int, len(sl))
copy(sl2, sl)
fmt.Println(sl2) // [1 2 3 4]
sl[0] = 100
fmt.Println(sl) // [100 2 3 4]
fmt.Println(sl2) // [1 2 3 4]
  • sort：支持切片排序
sl := make([]int, 0, 10)
for i := 0; i < 10; i++ {
    n := rand.Intn(100)
    sl = append(sl, n)
}
fmt.Println("排序前：", sl)
// 内置的排序算法
sort.Ints(sl)
fmt.Println("排序后：", sl)
// 降序，第二个参数传排序规则
sort.Slice(sl, func(i, j int) bool {
    return sl[i] > sl[j]
})
fmt.Println("反排序：", sl)

// 结果
排序前： [81 87 47 59 81 18 25 40 56 0]
排序后： [0 18 25 40 47 56 59 81 81 87]
反排序： [87 81 81 59 56 47 40 25 18 0]

4.动态扩容

4.1 append 触发扩容

在切片达到容量上限时，继续 append 操作会导致切片扩容。如代码所示，当切片 sl 的 len = cap = 8 时，继续 append 102 元素导致 sl 扩容，sl 与原底层数组 arr 解绑，因此 append 102 元素没有影响到原底层数组 arr，后续对 sl 元素更改也不会影响 arr。

arr := [10]int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
sl := arr[0:6:8]
fmt.Println(len(sl), cap(sl)) // 6 8
fmt.Println(sl)               // [1 2 3 4 5 6]

// 切片 append 会影响原底层数组内容
sl = append(sl, 100)
fmt.Println(len(sl), cap(sl)) // 7 8
fmt.Println(sl)               // [1 2 3 4 5 6 100]
fmt.Println(arr)              // [1 2 3 4 5 6 100 8 9 10]

// 切片 append 会影响原底层数组内容
sl = append(sl, 101)
fmt.Println(len(sl), cap(sl)) // 8 8
fmt.Println(sl)               // [1 2 3 4 5 6 100 101]
fmt.Println(arr)              // [1 2 3 4 5 6 100 101 9 10]

// 触发扩容，与原数组解绑
sl = append(sl, 102)
fmt.Println(len(sl), cap(sl)) // 9 16
fmt.Println(sl)               // [1 2 3 4 5 6 100 101 102]
fmt.Println(arr)              // [1 2 3 4 5 6 100 101 9 10]

// 后续更改也不会影响原底层数组内容
sl[0] = -1
fmt.Println(len(sl), cap(sl)) // 9 16
fmt.Println(sl)               // [-1 2 3 4 5 6 100 101 102]
fmt.Println(arr)              // [1 2 3 4 5 6 100 101 9 10]

slice 扩容后会迁移到新的内存位置，新底层数组的长度也会增加，这样就可以放置新增的元素。 同时，为了应对未来可能再次发生的 append 操作，新的底层数组的长度，也就是新 slice 的容量是留了一定的 buffer 的。否则，每次添加元素的时候，都会发生迁移，成本太高。

4.2 扩容规律

golang 版本 1.18

// go 1.18 src/runtime/slice.go:178
    func growslice(et *_type, old slice, cap int) slice {
      // ……
      newcap := old.cap
    	doublecap := newcap + newcap
    	if cap > doublecap {
    		newcap = cap
    	} else {
    		const threshold = 256
    		if old.cap < threshold {
    			newcap = doublecap
    		} else {
    			for 0 < newcap && newcap < cap {
            // Transition from growing 2x for small slices
    				// to growing 1.25x for large slices. This formula
    				// gives a smooth-ish transition between the two.
    				newcap += (newcap + 3*threshold) / 4
    			}
    			if newcap <= 0 {
    				newcap = cap
    			}
    		}
    	}
    	// ……
        
    	capmem = roundupsize(uintptr(newcap) * ptrSize)
    	newcap = int(capmem / ptrSize)

      // ……
    }

slice 扩容代码详解：

  • 计算新 slice 容量 newcap
    • 当原 slice 容量 (oldcap) 小于 256 的时候，新 slice(newcap) 容量为原来的2倍；
    • 原 slice 容量超过 256，新 slice 容量 newcap = oldcap+(oldcap+3*256)/4
  • 之后对 newcap 做了一个内存对齐，这个和内存分配策略相关（可以提高内存的分配效率并减少碎片，拓展内容有分析，有兴趣可以阅读）。进行内存对齐之后，新 slice 的容量是要 >= 按照前半部分生成的 newcap。
  • 之后，向 Go 内存管理器申请内存，将老 slice 中的数据复制过去，并且将 append 的元素添加到新的底层数组中。
  • 最后，向 growslice 函数调用者返回一个新的 slice，这个 slice 的长度并没有变化，而容量却增大了。

5.切片作为参数

Go 语言的函数参数传递，只有值传递，没有引用传递，切片作为参数当然也是如此。

5.1 形参通过改变底层数组影响实参

前面我们说到，slice 其实是一个结构体，包含了三个成员：len, cap, array。分别表示切片长度，容量，底层数据的地址。

当 slice 作为函数参数时，就是一个普通的结构体。 其实很好理解：若直接传 slice，在调用者看来，实参 slice 并不会被函数中的操作改变；若传的是 slice 的指针，在调用者看来，是会被改变原 slice 的。

值得注意的是，不管传的是 slice 还是 slice 指针，如果改变了 slice 底层数组的数据，会反应到实参 slice 的底层数据。

package main

func main() {
    sl := []int{6, 6, 6}
    f(sl)
    fmt.Println(sl)
}

func f(sl []int) {
    for i := range sl {
        sl[i] += 1
    }
}

// 输出 [7 7 7]

为什么能改变底层数组的数据？很好理解：底层数据在 slice 结构体里是一个指针，尽管 slice 结构体自身不会被改变，也就是说底层数据地址不会被改变。 但是通过指向底层数据的指针，可以改变切片的底层数据，这也是为什么网上常把 slice 称作引用类型的原因。

5.2 通过指针传递影响实参

形参是一个 slice 的副本，在函数中，形参只是实参的一个拷贝。因此，在函数内部，对形参的作用并不会改变外层的实参的，举个简单的例子。

package main

func main() {
    sl := []int{6, 6, 6}
    f(sl)
    fmt.Println(sl) // [6 6 6]
}

func f(sl []int) {
	for i := 0; i < 3; i++ {
		sl = append(sl, i)
	}
	fmt.Println(sl) // [6 6 6 0 1 2]
}

要想真的改变外层 slice，只有将返回的新的 slice 赋值到原始 slice，或者向函数传递一个指向 slice 的指针。我们再来看一个例子：

package main

import "fmt"

func myAppend(s []int) []int {
    // 这里 sl 虽然改变了，但并不会影响外层函数的 sl
    sl = append(sl, 100)
    return sl
}

func myAppendPtr(sl *[]int) {
    // 会改变外层 s 本身
    *sl = append(*sl, 100)
    return
}

func main() {
    sl := []int{1, 1, 1}
	sl2 := myAppend(sl)

	fmt.Println(sl) // [1 1 1]
	fmt.Println(sl2) // [1 1 1 100]

	sl = sl2
	myAppendPtr(&sl)
	fmt.Println(sl) // [1 1 1 100 100]
}

6.拓展内容

6.1 拓展 1

先看一个特殊的切片扩容案例：

package main

import "fmt"

func main() {
    sl := []int{1,2}
    sl = append(s,3,4,5)
    fmt.Printf("len=%d, cap=%d",len(sl),cap(sl))
}

// 运行结果 len=5, cap=6

当 cap 很小时，按双倍扩容理论来说，结果应该是 len=5, cap=8；但事实却是 len=5, cap=6。

原因简略分析：内存对齐导致的。

我们来逐行捋一下源代码，当我们执行上述代码时，会触发 runtime.growslice 函数扩容 sl 切片，并传入期望的新容量 newcap = 5，这时期望分配的内存大小为 40（5 * 8） 字节，因此 roundupsize 的参数 size = 40。

// ptrSize = 8 ptrSize 是指一个指针的大小，在 64 位机上是 8
// newcap = 5 
capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)

// src/runtime/msize.go:13
func roundupsize(size uintptr) uintptr {
	if size < _MaxSmallSize {
		if size <= smallSizeMax-8 {
			return uintptr(class_to_size[size_to_class8[divRoundUp(size, smallSizeDiv)]])
		} else {
			return uintptr(class_to_size[size_to_class128[divRoundUp(size-smallSizeMax, largeSizeDiv)]])
		}
	}
	if size+_PageSize < size {
		return size
	}
	return alignUp(size, _PageSize)
}

const _MaxSmallSize = 32768
const smallSizeMax = 1024
const smallSizeDiv = 8

执行 roundupsize 最终走的分支如下：

// 把常量替换后
return uintptr(class_to_size[size_to_class8[divRoundUp(40, 8)]])

// divRoundUp returns ceil(n / a).
func divRoundUp(n, a uintptr) uintptr {
	// a is generally a power of two. This will get inlined and
	// the compiler will optimize the division.
	return (n + a - 1) / a
}

// 调用 divRoundUp 计算得到 47/8 = 5
// 取 size_to_class8 数组的 5 索引的值为 5
var size_to_class8 = [smallSizeMax/smallSizeDiv + 1]uint8{0, 1, 2, 3, 4, 5, 5, 6, 6, ...}
// 取 class_to_size 数组的 5 索引的值为 48
var class_to_size = [_NumSizeClasses]uint16{0, 8, 16, 24, 32, 48, 64, 80, 96, ...}

调用 runtime.roundupsize 向上取整内存的大小到 48 字节，所以新切片的容量为 newcap = int(capmem / ptrSize) = 48 / 8 = 6。

6.2 拓展 2

如果向一个 nil 的 slice 添加元素会发生什么？为什么？

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

初值为零值 nil 的切片类型变量，可以借助内置的 append 的函数进行操作，这种在 Go 语言中被称为“零值可用”。

以上就是本文的全部内容，如果觉得还不错的话欢迎点赞，转发和关注，感谢支持。

转载自:https://juejin.cn/post/7290470513117675520
评论
请登录