乐趣区

关于golang:Go-Quiz-从Go面试题看slice的底层原理和注意事项

jiezi

面试题

最近 Go 101 的作者公布了 11 道 Go 面试题，十分乏味，打算写一个系列对每道题做具体解析。欢送大家关注。

大家能够看上面这道对于 slice 的题目，通过这道题咱们能够对 slice 的个性和注意事项有一个深刻了解。

package main

import "fmt"

func main() {a := [...]int{0, 1, 2, 3}
    x := a[:1]
    y := a[2:]
    x = append(x, y...)
    x = append(x, y...)
    fmt.Println(a, x)
}
  • A: [0 1 2 3] [0 2 3 3 3]
  • B: [0 2 3 3] [0 2 3 3 3]
  • C: [0 1 2 3] [0 2 3 2 3]
  • D: [0 2 3 3] [0 2 3 2 3]

大家能够在评论区留下你们的答案。这道题有几个考点：

  1. slice的底层数据结构是什么？给 slice 赋值，到底赋了什么内容？
  2. 通过 : 操作失去的新 slice 和原 slice 是什么关系？新 slice 的长度和容量是多少？
  3. append在背地到底做了哪些事件？
  4. slice的扩容机制是什么？

解析

咱们先一一解答下面的问题。

slice 的底层数据结构

talk is cheap, show me the code. 间接上 slice 的源码：

slice定义在 src/runtime/slice.go 第 15 行，源码地址：https://github.com/golang/go/…。

Pointer定义在 src/unsafe/unsafe.go 第 184 行，源码地址：https://github.com/golang/go/…。

type slice struct {
    array unsafe.Pointer
    len   int
    cap   int
}

type Pointer *ArbitraryType

slice实际上是一个构造体类型，蕴含 3 个字段，别离是

  • array: 是指针，指向一个数组，切片的数据理论都存储在这个数组里。
  • len: 切片的长度。
  • cap: 切片的容量，示意切片以后最多能够存储多少个元素，如果超过了现有容量会主动扩容。

因而给 slice 赋值，实际上都是给 slice 里的这 3 个字段赋值 。看起来这像是一句正确的废话，然而置信我，记住这句话能够帮忙你十分清晰地了解对slice 做批改后 slice 里 3 个字段的值是怎么变的，slice 指向的底层数组的数据是怎么变的。

:宰割操作符

:宰割操作符有几个特点：

  1. :能够对数组或者 slice 做数据截取，:失去的后果是一个新slice。
  2. 新 slice 构造体里的 array 指针指向原数组或者原 slice 的底层数组，新切片的长度是 ： 左边的数值减去右边的数值，新切片的容量是原切片的容量减去 : 右边的数值。

  3. :的右边如果没有写数字，默认是 0，左边没有写数字，默认是被宰割的数组或被宰割的切片的长度。

    a := make([]int, 0, 4) // a 的长度是 0，容量是 4
b := a[:] // 等价于 b := a[0:0], b 的长度是 0，容量是 4
c := a[:1] // 等价于 c := a[0:1], b 的长度是 1，容量是 4
d := a[1:] // 编译报错 panic: runtime error: slice bounds out of range
e := a[1:4] // e 的长度 3，容量 3
  4. :宰割操作符左边的数值有下限，下限有 2 种状况
  • 如果宰割的是数组，那下限是是被宰割的数组的长度。
  • 如果宰割的是切片，那下限是被宰割的切片的容量。留神，这个和下标操作不一样，如果应用下标索引拜访切片，下标索引的最大值是(切片的长度 -1)，而不是切片的容量。

一图胜千言，咱们通过上面的示例来解说下切片宰割的机制。

下图示意 slice 构造，ptr示意 array 指针，指向底层数组，len和 cap 别离是切片的长度和容量。

step1: 咱们通过代码 s := make([]byte, 5, 5) 来创立一个切片s，长度和容量都是 5，构造示意如下：


step2: 当初对切片 s 做宰割s2 := s[2:4]，失去一个新切片s2，构造如下。

  • s2还是指向原切片 s 的底层数组，只不过指向的起始地位是下标索引为 2 的地位。
  • s2的长度 len(s2) 是 2，因为 s2 := s[2:4] 只是截取了切片 s 下标索引为 2 和 3 的 2 个元素。
  • s2的容量 cap(s2) 是 3，因为从 s2 指向的数组地位到底层数组开端，能够存 3 个元素。
  • 因为长度是 2，所以只有 s2[0] 和s2[1]是无效的下标索引拜访。然而，容量为 3，s2[0:3]是一个无效的宰割表达式。

step3: 对切片 s 做宰割s3 := s2[:cap(s2)]，失去一个新切片s3，构造如下：

  • s3指向切片 s2 的底层数组，同样也是 s 的底层数组，指向的起始地位是 s2 的起始地位，对应数组下标索引为 2 的地位。
  • s3的长度 len(s3) 是 3，因为 s3 := s2[:cap(s2)] 截取了切片s2 下标索引为 0，1，2 的 3 个元素。
  • s3的容量 cap(s3) 是 3，因为从 s3 指向的数组地位到底层数组开端，能够存 3 个元素。

因而，对数组或者切片做 : 宰割操作产生的新切片还是指向原来的底层数组，并不会把原底层数组的元素拷贝一份到新的内存空间里。

正是因为他们指向同一块内存空间，所以对原数组或者原切片的批改会影响宰割后的新切片的值，反之亦然。

append 机制

要理解 append 的机制，间接看源码阐明。

// The append built-in function appends elements to the end of a slice. If
// it has sufficient capacity, the destination is resliced to accommodate the
// new elements. If it does not, a new underlying array will be allocated.
// Append returns the updated slice. It is therefore necessary to store the
// result of append, often in the variable holding the slice itself:
//    slice = append(slice, elem1, elem2)
//    slice = append(slice, anotherSlice...)
// As a special case, it is legal to append a string to a byte slice, like this:
//    slice = append([]byte("hello"), "world"...)
func append(slice []Type, elems ...Type) []Type

  • append 函数返回的是一个切片，append 在原切片的开端增加新元素，这个开端是切片长度的开端，不是切片容量的开端。

    func test() {a := make([]int, 0, 4)
    b := append(a, 1) // b=[1], a 指向的底层数组的首元素为 1，然而 a 的长度和容量不变
    c := append(a, 2) // a 的长度还是 0，c=[2], a 指向的底层数组的首元素变为 2
    fmt.Println(a, b, c) // [] [2] [2]
}

  • 如果原切片的容量足以蕴含新减少的元素，那 append 函数返回的切片构造里 3 个字段的值是：

    • array 指针字段的值不变，和原切片的 array 指针的值雷同，也就是 append 是在原切片的底层数组返回的切片还是指向原切片的底层数组
    • len 长度字段的值做相应减少，减少了 N 个元素，长度就减少 N
    • cap 容量不变

  • 如果原切片的容量不够存储 append 新减少的元素，Go 会先调配一块容量更大的新内存，而后把原切片里的所有元素拷贝过去，最初在新的内存里增加新元素。append 函数返回的切片构造里的 3 个字段的值是：

    • array 指针字段的值变了，不再指向原切片的底层数组了，会指向一块新的内存空间
    • len 长度字段的值做相应减少，减少了 N 个元素，长度就减少 N
    • cap 容量会减少

留神：append 不会扭转原切片的值，原切片的长度和容量都不变，除非把 append 的返回值赋值给原切片。

那么问题来了，新切片的容量是依照什么规定计算得进去的呢？

slice 扩容机制

slice的扩容机制随着 Go 的版本迭代，是有变动的。目前网上大部分的说法是上面这个：

当原 slice 容量小于 1024 的时候，新 slice 容量变成原来的 2 倍；原 slice 容量超过 1024，新 slice 容量变成原来的 1.25 倍。

这里明确通知大家，这个论断是 谬误 的。

slice扩容的源码实现在 src/runtime/slice.go 里的 growslice 函数，源码地址：https://github.com/golang/go/…。

Go 1.18 的扩容实现代码如下，et 是切片里的元素类型，old 是原切片，cap 等于原切片的长度 +append 新增的元素个数。

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 {
            // Check 0 < newcap to detect overflow
            // and prevent an infinite loop.
            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
            }
            // Set newcap to the requested cap when
            // the newcap calculation overflowed.
            if newcap <= 0 {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 == goarch.PtrSize:
        lenmem = uintptr(old.len) * goarch.PtrSize
        newlenmem = uintptr(cap) * goarch.PtrSize
        capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
        overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
        newcap = int(capmem / goarch.PtrSize)
    case isPowerOfTwo(et.size):
        var shift uintptr
        if goarch.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)
    }
    // ...
    return slice{p, old.len, newcap}
}

newcap 是扩容后的容量，先依据原切片的长度、容量和要增加的元素个数确定 newcap 大小，最初再对 newcap 做内存对齐失去最初的 newcap。

答案

咱们回到本文最开始的题目，逐行解析每行代码的执行后果。

代码 切片对应后果
a := […]int{0, 1, 2, 3} a 是一个数组，长度是 4，值是[0 1 2 3]
x := a[:1] x 是一个切片，切片里的指针指向数组 a 的首元素，值是[0]，长度 1，容量 4
y := a[2:] y 是一个切片，切片里的指针指向数组 a 的第 2 个元素，值是[2 3]，长度 2，容量 2
x = append(x, y…) x 的残余容量还有 3 个，足以存储 y 里的 2 个元素，所以 x 不会扩容，x 的值是[0 2 3]，长度 3，容量 4。因为 x, a, y 都指向同一块内存空间，所以 x 的批改影响了 a 和 y。
a 的值变为[0 2 3 3]，长度 4，容量 4
y 的值变为[3 3]，长度 2，容量 2
x = append(x, y…) x 的残余容量只有 1 个，不足以存储 y 里的 2 个元素，所以要扩容。append(x, y)的后果是失去一个新切片，值是[0 2 3 3 3]，长度 5，容量 8。
append 的返回值赋值给 x，所以切片 x 会指向扩容后的新内存。
fmt.Println(a, x) a 的值还是 [0 2 3 3] 没有变动，所以打印后果是[0 2 3 3] [0 2 3 3 3 3]，答案是 B

加餐：copy 机制

Go 的内置函数 copy 能够把一个切片里的元素拷贝到另一个切片，源码定义在src/builtin/builtin.go，代码如下：

// The copy built-in function copies elements from a source slice into a
// destination slice. (As a special case, it also will copy bytes from a
// string to a slice of bytes.) The source and destination may overlap. Copy
// returns the number of elements copied, which will be the minimum of
// len(src) and len(dst).
func copy(dst, src []Type) int

copy会从原切片 src 拷贝 min(len(dst), len(src))个元素到指标切片dst，

因为拷贝的元素个数 min(len(dst), len(src)) 不会超过指标切片的长度 len(dst)，所以copy 执行后，指标切片的长度不会变，容量不会变。

留神 ：原切片和指标切片的内存空间可能会有重合，copy 后可能会扭转原切片的值，参考下例。

package main

import "fmt"

func main() {a := []int{1, 2, 3}
    b := a[1:] // [2 3]
    copy(a, b) // a 和 b 内存空间有重叠
    fmt.Println(a, b) // [2 3 3] [3 3]
}

总结

对于 slice，时刻想着对 slice 做了批改后，slice 里的 3 个字段：指针，长度，容量是怎么变的。

  • slice是一个构造体类型，外面蕴含 3 个字段：指向数组的 array 指针，长度 len 和容量 cap。给 slice 赋值是对slice 里的指针，长度和容量 3 个字段别离赋值。
  • :宰割操作符的后果是一个新切片，新 slice 构造体里的 array 指针指向原数组或者原 slice 的底层数组，新切片的长度是 ： 左边的数值减去右边的数值，新切片的容量是原切片的容量减去 : 右边的数值。

  • :宰割操作符左边的数值下限有 2 种状况：

    • 如果宰割的是数组，那下限是是被宰割的数组的长度。
    • 如果宰割的是切片，那下限是被宰割的切片的容量。留神，这个和下标操作不一样，如果应用下标索引拜访切片，下标索引的最大值是(切片的长度 -1)，而不是切片的容量。
  • 对于 append 操作和 copy 操作，要分明背地的执行逻辑。

  • 打印 slice 时，是依据 slice 的长度来打印的

    a := make([]int, 1, 4) // a 的长度是 1，容量是 4
b := append(a, 1) // 往 a 的开端增加元素 1，b=[0 1], a 的长度还是 1，a 和 b 指向同一个底层数组
fmt.Println(a, b) // [0] [0 1]
  • Go 在函数传参时，没有传援用这个说法，只有传值。网上有些文章写 Go 的 slice，map，channel 作为参数是传援用，这是谬误的，能够参考我之前的文章 Go 有援用变量和援用传递么？

开源地址

文章和示例代码开源地址在 GitHub: https://github.com/jincheng9/…

公众号：coding 进阶

集体网站：https://jincheng9.github.io/

思考题

留下 2 道思考题，欢送大家在评论区留下你们的答案。

  • 题目 1：

    package main

import "fmt"

func main() {a := []int{1, 2}
    b := append(a, 3)

    c := append(b, 4)
    d := append(b, 5)

    fmt.Println(a, b, c[3], d[3])
}

  • 题目 2 

    package main

import "fmt"

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

References

  • https://go101.org/quizzes/sli…
  • https://go.dev/blog/slices-intro
  • https://github.com/golang/go/…
  • https://qcrao91.gitbook.io/go…
退出移动版