数组和切片

标签:Go语言首次发布:2024-01-13最近修改:2024-04-02

数组的声明方式

数组的声明主要有三种方式,如下所示。

go
var array1 [3]intvar array2 = [3]int{1, 2, 3}array3 := [...]int{4, 5, 6}

数组是内存中一片连续的区域,需要在初始化时被指定长度,数组的大小取决于数组中存放的元素大小。至于第三种声明方式可以理解为一种语法糖,其让 Go 编译器在编译时自动推断数组元素的个数。

  • 可以通过 fmt.Printf 的%T 格式化打印出数组的类型,不同类型的数组之间不能进行比较。
  • 数组长度可以通过内置的 len 函数获取,数组中的元素可以通过下标获取。
  • 只能访问数组中已有的元素,如果数组访问越界,则在编译时会报错。

数组值复制

与 C 语言中的数组显著不同的是,Go 语言中的数组在赋值和函数调用时的形参都是值复制。如下所示,无论是赋值的 b 还是函数调用中的 c,都是值复制的。这意味着不管是修改 b 还是 c 的值,都不会影响 a 的值,因为他们是完全不同的数组。这种值复制的行为确保了数组在函数调用中的数据安全性,因为原始数据不会被无意间修改。

go
var a = [3]int{1, 2, 3}b := afunc Change(c [3]int) {}

可以打印它们的地址看看是不是同一个数组。

go
func Change(c [3]int) {    fmt.Printf("c:%p\n", &c)}func main() {    var a = [3]int{1, 2, 3}    b := a    fmt.Printf("a:%p\n", &a)    fmt.Printf("b:%p\n", &b)    Change(a)}

程序输出如下,每个数组在内存中的位置都是不相同的,验证了值复制。

bash
a:0xc000010180b:0xc000010198c:0xc0000101b0

切片数据结构

image-20240112101646350

go
// src\runtime\slice.gotype slice struct {    array unsafe.Pointer // 指向起点的地址    len   int			 // 切片长度    cap   int		     // 切片容量}

切片的类型定义如上,我们称之为 slice header,对应于每个 slice 实例,其中核心字段包括:

  • array:指向底层数组的起始地址。由于 slice 数据存放在连续的内存空间中,后续可以根据索引 index,在起点的基础上快速进行地址偏移,从而定位到目标元素。

  • len:切片的长度,指的是逻辑意义上 slice 中实际存放元素的个数

  • cap:切片的容量,指的是物理意义上为 slice 分配的存放元素的空间。 使用 slice 时,要求 cap 永远大于等于 len

切片初始化

声明但不初始化:下面给出的第一个例子,只是声明了 slice 的类型,但是并没有执行初始化操作,即 s 这个字面量此时是一个空指针 nil,并没有完成实际的内存分配操作

text
var s []int

下面先来介绍下切片的初始化操作:

基于 make 进行初始化

  1. make 初始化 slice 也分为两种方式,第一种方式如下:

    go
    s := make([]int,8)

    此时会将切片的长度 len 和 容量 cap 同时设置为 8。需要注意,切片的长度一旦被指定了,就代表对应位置已经被分配了元素,尽管设置的是对应元素类型下的零值。

  2. 第二种方式是分别指定切片的长度 len 和容量 cap,代码如下:

    go
    s := make([]int,8,16)

    如上所示,表示在切片中设置了 8 个元素,会设置为对应类型的零值;cap = 16 代表为 slice 分配了用于存放 16 个元素的空间。在 index 为[len, cap)的范围内,虽然内存空间已经分配了,但是逻辑意义上不存在元素,直接访问会 panic 报数组访问越界;但是访问 [0,len) 范围内的元素是能够正常访问到的,只不过会是对应元素类型下的零值。

初始化并赋值

初始化 slice 时还能一气呵成完成赋值操作。如下所示:

go
s := []int{2,3,4}

这样操作的话,会将 slice 长度 len 和容量 cap 均设置为 3,同时完成对这 3 个元素赋值。

源代码

下面是切片初始化的源码,代码位于 src/runtime/slice.go 文件的 makeslice 函数中:

go
func makeslice(et *_type, len, cap int) unsafe.Pointer {    mem, overflow := math.MulUintptr(et.size, uintptr(cap))      // 检查是否有溢出,是否超过了允许的最大分配大小maxAlloc,或者是否len参数小于0或者大于cap    if overflow || mem > maxAlloc || len < 0 || len > cap {        mem, overflow := math.MulUintptr(et.size, uintptr(len))        if overflow || mem > maxAlloc || len < 0 {            panicmakeslicelen()        }        panicmakeslicecap()    }    return mallocgc(mem, et, true)}
  1. makeslice 函数,它接受三个参数:et 是一个指向 _type 结构体的指针,代表切片元素的类型;len 是切片的长度;cap 是切片的容量。函数返回一个 unsafe.Pointer 类型的值,指向新分配的内存。
  2. 使用 math.MulUintptr 函数来计算切片所需的总字节数。et.size 是单个元素的大小,uintptr(cap) 是切片的容量转换为 uintptr 类型。如果计算结果超出 uintptr 的最大值,则 overflow 变量会被设置为 true。
  3. 如果没有错误,mallocgc 函数会被调用来分配内存。这个函数接受所需内存的大小 mem,元素类型 et,和一个布尔值表示是否需要进行垃圾回收。分配成功后,它返回一个指向分配内存的 unsafe.Pointer。

值传递与引用传递

首先,我们要清楚引用传递和值传递这两个概念的区别。

image-20240112222159067

引用传递指的是将实例的地址信息传递到方法中,这样在方法中会直接通过地址追溯到实例所在位置,因此执行的一些修改操作会直接影响到原实例。

image-20240112222253482

值传递指的是对实例进行一轮拷贝,得到一个副本,然后将这个副本传递到方法中. 这样在方法内部发生的修改动作都作用于这个副本之上,而副本本身和实例是相互独立的,因此不会影响到原实例。

go 语言中的切片属于引用传递的类型,下面给出一个说明示例:

go
func Demo_slice(t *testing.T){    s := []int{1,2,3}    changeSlice(s)}func changeSlice(s []int){    // [1,2,3] -> [4,2,3]    s[0] = 4}

如代码所示,将主方法 Demo_slice 中声明的切片 s 作为 changeSlice 方法的入参进行传递,同时在 changeSlice 方法中对 s 内的元素进行修改,这样是会直接影响到 Demo_slice 中的切片 s 的。

可以结合前面提到的 slice header 的数据结构,每个切片实例对应一个 slice header,其中存储了三个字段:array、len、cap。当我们每次在方法间传递切片时,会对 slice header 实例本身进行一次值拷贝,然后将 slice header 的副本传递到局部方法中。然而,这个 slice header 副本中的 array 和原 slice 指向同一片内存空间,因此在局部方法中执行修改操作时,还会根据这个地址信息影响到原 slice 所属的内存空间,从而对内容发生影响。

切片内容截取

我认为切片截取只需要记住左闭右开这四个字即可。也就是说对于切片 s,其中 a 和 b 代表切片的索引,根据左闭右开,那么 s[a:b] 对应的范围就是 [a,b),即表示截取切片 s[a]到 s[b-1]范围的内容。并且这里的 a 和 b 是可以缺省的:

  • 如果 a 缺省不填则默认取 0 ,则代表从切片起始位置开始截取. 比如 s[:b] 等价于 s[0:b]
  • 如果 b 缺省不填,则默认取 len(s),则代表末尾截取到切片长度 len 的终点,比如 s[a:] 等价于 s[a:len(s)]
  • a 和 b 均缺省也是可以的,则代表截取整个切片长度的范围,比如 s[:] 等价于 s[0:len(s)]

在对切片执行截取操作时,本质上是一次引用传递操作,因为不论如何截取,底层复用的都是同一块内存空间中的数据。

下面用代码进行验证:

go
func cutSlice(s []int) {    newSlice := s[1:5]    fmt.Printf("截取后的切片:%#v 切片首地址为:%#p\n", newSlice, &newSlice[0])}func main() {    a := []int{9, 8, 7, 6, 5, 4}    fmt.Printf("截取前的切片:%#v 切片首地址为:%#p\n", a, &a[0])    cutSlice(a)}

运行结果如下:

bash
截取前的切片:[]int{9, 8, 7, 6, 5, 4} 切片首地址为c00000e390截取后的切片:[]int{8, 7, 6, 5} 切片首地址为c00000e398

切片截取的示意图如下:

image-20240113101155995

两个切片指向的底层数组首个元素的地址刚好相差 8 个字节,而 64 位系统中 int 类型的切片每个元素的大小刚好是 8 个字节,因此这两个切片用的是同一个底层数组。

切片扩容

当切片的当前的长度 len 与容量 cap 相等时,下一次 append 操作就会引发一次切片扩容。切片的扩容流程源码位于 src/runtime/slice.go 文件的 growslice 函数当中。

go
// et:表示元素的类型 old:是当前的切片 cap:是调用者请求的新容量func growslice(et *_type, old slice, cap int) slice {    // 数据竞争检测    if raceenabled {        callerpc := getcallerpc()        racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, abi.FuncPCABIInternal(growslice))    }    // 内存安全检测    if msanenabled {        msanread(old.array, uintptr(old.len*int(et.size)))    }    // 地址安全检测    if asanenabled {        asanread(old.array, uintptr(old.len*int(et.size)))    }    // 容量校验:如果请求的新容量小于当前容量,就会抛出一个错误    if cap < old.cap {        panic(errorString("growslice: cap out of range"))    }    // 零大小元素的处理(处理类型大小位0的类型,比如struct{}或[]int{})    if et.size == 0 {        // 直接创建一个新切片,长度为旧的长度,容量为请求的新容量,并且指针指向一个全局的zerobase变量        return slice{unsafe.Pointer(&zerobase), old.len, cap}    }      // 计算新容量    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 {                newcap += (newcap + 3*threshold) / 4            }            if newcap <= 0 {                newcap = cap            }        }    }    // 根据元素大小的不同,进行内存分配优化    var overflow bool    var lenmem, newlenmem, capmem uintptr    switch {    case et.size == 1:      ······    case et.size == goarch.PtrSize:      ······    case isPowerOfTwo(et.size):          ······    default:      ······    }    // 如果在计算过程中发生溢出,或者计算的新容量超过了最大可分配内存,则抛出异常    if overflow || capmem > maxAlloc {        panic(errorString("growslice: cap out of range"))    }    // 如果元素不包含指针,则使用 mallocgc 分配未清零的内存    // 如果包含指针,则分配清零的内存,并在写屏障启用的情况下处理旧数组的指针    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 将旧数组的数据复制到新分配的内存中    memmove(p, old.array, lenmem)    // 返回一个包含新内存指针、旧长度和新容量的切片结构    return slice{p, old.len, newcap}}

这么一长串的代码中,目前只需要研究如何计算新容量即可。扩容的具体逻辑如下:

  1. 当前容量翻倍 (doublecap):首先会尝试将切片的当前容量翻倍。这是通过简单地将 old.cap + old.cap 来实现的。
  2. 根据新容量(cap)决定策略
    • 如果所需容量 (cap) 大于翻倍后的容量 (doublecap),则直接将所需容量 (cap) 设置为新容量 (newcap)。
    • 如果所需容量 (cap) 小于等于翻倍后的容量 (doublecap), 则会有两种情况:
      • 如果当前容量 (old.cap) 小于 256,这意味着切片是小的,直接翻倍已经足够,因此翻倍后的容量 (doublecap) 将被设置为新容量 (newcap) 。
      • 如果当前容量 (old.cap) 大于或等于 256,这意味着切片已经相对较大,此时将使用更渐进的扩容策略,即每次将新容量增加当前容量的 1.25 倍,直到新容量 (newcap) 大于等于所需容量 (cap)。
  3. 平滑过渡:通过 (newcap + 3*threshold) / 4 的方式来平滑地从 2 倍增长过渡到 1.25 倍增长。这个过渡公式计算的结果就是每次迭代 newcap 会增加原来四分之一以上一点点。
  4. 溢出检查:在扩容循环中,还有一个检查 0 < newcap,这是为了检测整数溢出。如果 newcap 变成了负数,则表示发生了溢出,这时就会将 newcap 设置为所需容量 (cap),这是因为负数的容量没有意义,表明计算结果无效。
  5. 最终容量确认:循环结束后,如果newcap <= 0,这可能是由于溢出或者所需容量非常大,此时将所需的 cap 设置为 newcap。

文字描述有些枯燥,下面是切片扩容的流程图:

image-20240114101709659

切片拷贝

切片的拷贝可以分为简单拷贝和完整拷贝两种类型。

简单拷贝

要实现简单拷贝,只需要对切片的字面量进行赋值传递即可,这样相当于创建出了一个新的 slice header 实例,但是其中的指针 array、容量 cap 和长度 len 仍和老的 slice header 实例相同。

代码如下,最终输出的结果中,s1 和 s2 的地址是一致的。对 s2 修改后 s1 也同样会被改变。

go
func main() {    s1 := []int{9, 8, 7, 6, 5, 4}    s2 := s1    fmt.Printf("s1的地址:%p\ns2的地址:%p\n", s1, s2)    s2[0] = 1    fmt.Printf("修改后的s2:%#v\n修改后的s1:%#v\n", s2, s1)}

运行结果如下:

bash
s1的地址:0xc0000c8030s2的地址:0xc0000c8030修改后的s2:[]int{1, 8, 7, 6, 5, 4}修改后的s1:[]int{1, 8, 7, 6, 5, 4}

完整拷贝

切片的完整拷贝,指的是会创建出一个和切片容量大小相等的独立的内存区域,并将原切片中的元素一一拷贝到新空间中。在实现上,切片的完整拷贝可以调用系统方法 copy,代码示例如下,通过打印可以看到,s1 和 s2 的地址是相互独立的。

go
func main() {    s1 := []int{9, 8, 7, 6, 5, 4}    s2 := make([]int, len(s1))    copy(s2, s1)    fmt.Printf("s1的地址:%p\ns2的地址:%p\n", s1, s2)    s2[0] = 1    fmt.Printf("s2:%#v\ns1:%#v\n", s2, s1)}

运行结果如下:

bash
s1的地址:0xc00000e390s2的地址:0xc00000e3c0s2:[]int{1, 8, 7, 6, 5, 4}s1:[]int{9, 8, 7, 6, 5, 4}