Golang中的切片

1. 定义与特性

• 切片（Slice） 是Go语言中一个关键的数据类型，它提供了一个比数组更灵活、更强大的序列接口。
• 切片并不存储任何数据，它只是对底层数组的引用。
• 切片可以动态增长和收缩，提供了比数组更高的灵活性。

2. 创建切片

• 直接声明：例如 var s []int，这创建了一个nil切片。
• 从数组创建：例如 s := arr[start:end]，这根据数组 arr 的一个区间创建切片。
• 使用make函数：例如 s := make([]int, length, capacity)，这创建了一个具有指定长度和容量的切片。

3. 切片的长度和容量

• 长度（Length）：切片中元素的数量。
• 容量（Capacity）：从切片的第一个元素到其底层数组末尾的元素数量。
• 使用 len(s) 可以获取切片的长度，使用 cap(s) 可以获取切片的容量。

4. 切片操作

• 重新切片：可以通过 s = s[start:end] 来调整切片的长度，只要它在原始切片的容量范围内。
• 追加元素：append 函数可以向切片追加元素，如果超出容量，会自动扩展。
• 拷贝切片：copy 函数可以用来拷贝切片中的元素到另一个切片。
• 删除元素：
  • 删除切片中的第i位元素: s = append(s[:i], s[i+1:]...)
  • 删除切片中的首个元素: s = s[1:]
  • 删除切片中的最后一个元素: s = s[:len(s)-1]
  • 删除切片中的第i个到j个元素: s = append(s[:i], s[j:]...)

5. 切片的内部结构

• 切片在Go的内部实现中是一个结构体，包含三个字段：
  • 指针：指向底层数组中切片指定的开始位置。
  • 长度：切片中元素的数量。
  • 容量：从切片的开始位置到底层数组的末尾的元素数量。

6. 切片的注意事项

• 切片是引用类型，对切片的修改会影响到底层数组。
• 切片之间可以共享底层数组，修改一个切片可能会影响另一个切片。
• 切片的零值是nil，一个nil切片的长度和容量都是0，但它没有底层数组。

7. 使用场景

• 切片非常适合用于处理动态序列数据。
• 在函数间传递切片比传递数组更高效，因为切片是引用传递。
• 切片广泛用于Go标准库中，如字符串处理、文件操作、网络编程等。

示例代码

package main

import "fmt"

func main() {
    // 创建切片
    s := make([]int, 0, 5)

    // 追加元素
    s = append(s, 1, 2, 3)

    // 获取长度和容量
    fmt.Println("Length:", len(s), "Capacity:", cap(s))

    // 切片操作
    s2 := s[1:3]
    fmt.Println(s2)
}

当多个切片共享同一个底层数组时，对其中一个切片所做的修改可能会影响其他切片。这是因为切片仅是对数组片段的引用，并不拥有数组中的数据。下面详细介绍这个特性：

共享底层数组的特性

1. 创建共享底层数组的切片：
   • 当你从一个已存在的切片或数组创建新切片时，新切片会引用相同的底层数组。
   • 例如，newSlice := originalSlice[start:end] 创建了一个新切片 newSlice，它引用 originalSlice 的底层数组。
2. 影响范围：
   • 修改任一切片中的元素，如果这些元素在共享的底层数组中，其他切片也会受到影响。
   • 例如，如果 newSlice[0] 是 originalSlice[2] 的同一元素，修改 newSlice[0] 也会改变 originalSlice[2] 的值。
3. 容量与边界：
   • 切片的容量是指从其起始元素到底层数组末尾的元素个数。因此，即使两个切片共享相同的底层数组，它们的容量可能不同，这取决于各自的起始位置。
   • 一个切片对底层数组的修改可能超出其长度但在容量范围内，这可能会影响到其他切片。

示例：共享底层数组的影响

package main

import "fmt"

func main() {
    // 创建一个数组
    arr := [5]int{1, 2, 3, 4, 5}

    // 创建切片，共享相同的底层数组
    slice1 := arr[1:4]  // 包含元素 2, 3, 4
    slice2 := arr[2:5]  // 包含元素 3, 4, 5

    // 修改slice1的一个元素
    slice1[1] = 100  // 将元素3改为100

    // 打印两个切片和原始数组
    fmt.Println("slice1:", slice1)  // 输出：slice1: [2 100 4]
    fmt.Println("slice2:", slice2)  // 输出：slice2: [100 4 5]
    fmt.Println("arr:", arr)        // 输出：arr: [1 2 100 4 5]
}

注意事项

• 当函数接收切片参数时，如果函数内部修改了切片元素，调用该函数的外部环境中相应的切片也会受到影响。
• 在需要独立修改数据而不影响原始数据时，应考虑使用 copy 函数来创建一个新的切片副本。

理解这一点对于避免数据共享带来的意外副作用非常重要，尤其是在并发编程和复杂数据结构处理中。

数组与切片的区别

数组的定义

数组的定义需要指定元素的数量（长度固定），格式为 [n]T，其中 n 是数组的长度，T 是数组中元素的类型。例如：

• 定义一个长度为5的整数数组：var arr [5]int
• 初始化数组时指定所有元素的值：arr := [5]int{1, 2, 3, 4, 5}
• 让编译器根据初始化值的数量自动确定数组长度：arr := [...]int{1, 2, 3, 4, 5}

切片的定义

切片的定义不需要指定元素的数量，格式为 []T，只指定元素类型 T。切片的长度和容量在运行时可以改变。例如：

• 定义一个整数切片：var s []int
• 使用 make 创建切片并指定长度和容量：s := make([]int, length, capacity)
• 从数组或另一个切片初始化切片：s := arr[start:end]

关键区别

• 长度：数组的长度是其类型的一部分，一旦声明就不能改变。切片的长度是动态的，可以通过 append 和重新切片操作来改变。
• 类型表示：在类型表示上，数组需要在类型前指定长度（例如 [5]int），而切片不需要（例如 []int）。

这些区别导致了数组和切片在Go语言中的使用方式和场景上的不同。arrays 通常用于较小的或固定大小的数据集合，而 slices 用于更加动态和灵活的数据处理。

数组和切片在Go语言中都用于存储序列数据，但它们在使用上有明显的区别：

1. 长度的固定性：
   • 数组：长度固定，声明时需指定数组的大小，且大小不能改变。
   • 切片：长度可变，可以动态地增加或减少元素。
2. 数据类型：
   • 数组：是值类型，赋值和作为参数传递时会复制整个数组。
   • 切片：是引用类型，赋值和作为参数传递时只会复制切片本身（底层数组不会被复制）。
3. 内存分配：
   • 数组：在编译时分配固定大小的内存。
   • 切片：可以在运行时动态分配和调整大小。
4. 性能考虑：
   • 数组：由于是值类型，较大的数组在作为参数传递时可能会有性能问题。
   • 切片：更适合作为参数传递，因为只传递引用。

作为函数参数传递

数组

当数组作为参数传递给函数时，会发生数组的整体拷贝。也就是对于数组的修改不会影响到原来的数组。对于较大的数组，这可能导致性能问题。

切片

当切片作为函数参数传递时，实际上传递的是切片的副本。这个副本引用的是同一个底层数组。这意味着：

• 传递值：虽然切片本身是以值的形式传递的（即传递切片的副本），但由于切片内部包含对底层数组的引用，所以对切片内容的修改会影响原始切片。
• 改变元素：如果在函数内部改变了切片的元素，这些改变会反映到原始切片上。
• 改变大小：如果尝试改变切片的大小（例如，通过 append 函数添加元素），情况就会变得复杂：
  • 如果改变后的大小不超过原切片的容量，那么这个改变也会反映到原始切片上。
  • 如果改变导致切片扩容（即超出原有容量），则会分配一个新的底层数组。这时，函数内部的切片副本会指向这个新的数组，而外部的原始切片仍然指向旧的数组。

传递切片的引用

在Go中，没有直接的方式来传递切片的“引用”。但如果您想在函数内部改变切片的长度并反映到原始切片，您可以：

• 返回修改后的切片，并在调用函数后使用这个返回值。
• 使用指向切片的指针作为参数（虽然这不是常见的做法）。

示例

这个例子展示了当切片作为函数参数传递时，如何改变其大小：

package main

import "fmt"

func appendSlice(slice []int, values ...int) []int {
    return append(slice, values...)
}

func main() {
    originalSlice := []int{1, 2, 3}
    modifiedSlice := appendSlice(originalSlice, 4, 5)

    fmt.Println("Original Slice:", originalSlice)
    fmt.Println("Modified Slice:", modifiedSlice)
}

在这个例子中，appendSlice 函数返回一个新的切片，这个切片可能引用了一个新的底层数组（如果进行了扩容的话）。这样，可以在函数外部接收这个改变后的切片。

总结来说，切片作为函数参数传递时，虽然传递的是切片的副本，但由于切片内部包含对底层数组的引用，所以对其元素的修改会影响到原始切片。但是，如果需要改变切片的大小，并希望这种改变反映到原切片上，需要特别处理，比如通过返回新切片或使用指向切片的指针。

切片的扩容机制

切片的扩容是Go语言切片最重要的特性之一。切片的扩容过程如下：

1. 初始容量：当使用 make 函数创建切片时，可以指定切片的初始容量。如果未指定，切片的容量默认为其长度。
2. 追加元素：当使用 append 函数向切片追加元素，且当前切片容量不足以容纳更多元素时，切片会自动扩容。

Go 1.17版本切片扩容

Go 1.17切片扩容时会进行内存对齐，这个和内存分配策略相关。进行内存对齐之后，新 slice 的容量是要 大于等于老 slice 容量的 2倍或者1.25倍。

• 当新切片需要的容量cap大于两倍扩容的容量，则直接按照新切片需要的容量扩容；
• 当原 slice 容量 < 1024 的时候，新 slice 容量变成原来的 2 倍；
• 当原 slice 容量 > 1024，进入一个循环，每次容量变成原来的1.25倍,直到大于期望容量。

Go 1.18版本切片扩容

Go1.18不再以1024为临界点，而是设定了一个值为256的threshold，以256为临界点；超过256，不再是每次扩容1/4，而是每次增加（旧容量+3*256）/4；

• 当新切片需要的容量cap大于两倍扩容的容量，则直接按照新切片需要的容量扩容；
• 当原 slice 容量 < threshold 的时候，新 slice 容量变成原来的 2 倍；
• 当原 slice 容量 > threshold，进入一个循环，每次容量增加（旧容量+3*threshold）/4。

最后还有一个内存对齐步骤，实际容量会比这个公式计算出来的大。

内存对齐

内存对齐是计算机硬件对内存访问的一种优化。对于现今的计算机硬件设计，内存是按照一个固定大小（如4 bytes, 8 bytes, 16 bytes等）的块来读取或者写入的。如果数据没有按照这样的块边界来存放，硬件可能需要多次访问内存才能读取或者写入数据，这会降低程序的性能。

以4 bytes为例，如果我们要读取一个4 bytes的数据，在内存中的起始地址如果不是4的倍数，硬件需要两次读取操作才能获取到完整的4 bytes数据。第一次读取会获取到数据的一部分，然后第二次读取才能获取到剩余的数据。这是因为硬件只能从地址是4的倍数的地方开始读取4 bytes的数据。

反之，如果数据在内存中的起始地址是4的倍数，硬件只需要一次读取操作就能获取到完整的4 bytes数据。这就是为什么内存对齐可以提高性能的原因。

因此在Go 1.18版本中，切片的扩容操作在确定扩容容量后，还会做一个内存对齐的步骤，确保扩容后的切片在内存中的存放位置能满足硬件的最优访问需求。

源代码注释

growth formula a bit smoother
Instead of growing 2x for < 1024 elements and 1.25x for >= 1024 elements,
use a somewhat smoother formula for the growth factor. Start reducing
the growth factor after 256 elements, but slowly.

starting cap    growth factor
256             2.0
512             1.63
1024            1.44
2048            1.35
4096            1.30

(Note that the real growth factor, both before and now, is somewhat
larger because we round up to the next size class.)

This CL also makes the growth monotonic (larger initial capacities
make larger final capacities, which was not true before). See discussion
at https://groups.google.com/g/golang-nuts/c/UaVlMQ8Nz3o

256 was chosen as the threshold to roughly match the total number of
reallocations when appending to eventually make a very large
slice. (We allocate smaller when appending to capacities [256,1024]
and larger with capacities [1024,...]).

通过减小阈值并固定增加一个常数，使得优化后的扩容的系数在阈值前后不再会出现从2到1.25的突变，该commit作者给出了几种原始容量下对应的“扩容系数”：

oldcap	扩容系数
256	2.0
512	1.63
1024	1.44
2048	1.35
4096	1.30

可以看到，Go1.18的扩容策略中，随着容量的增大，其扩容系数是越来越小的，可以更好地节省内存。注意这个不是一个间断函数，而是连续函数，上面的表只是在oldcap取不同值时计算出来的“扩容系数”，实际上对于不同的oldcap，扩容系数是逐渐变化的。当oldcap远大于256的时候，扩容系数将会无限接近1.25。

测试扩容

package main

import (
    "testing"
)

func TestCap(t *testing.T) {
    var s []int
    lastCap := cap(s)

    for i := 0; i < 1000; i++ {
        s = append(s, i)
        newCap := cap(s)

        if newCap != lastCap {
            expectedCap := calculateExpectedCap(lastCap, i+1) // i+1 是因为添加了一个新元素
            t.Logf("Added element %d, length: %d, actual capacity: %d, expected capacity: %d\n", i, len(s), newCap, expectedCap)
            lastCap = newCap
        }
    }
}

func calculateExpectedCap(oldcap, cap int) int {
    threshold := 256
    if cap > oldcap*2 {
        return cap
    }
    if oldcap < threshold {
        return oldcap * 2
    }
    return oldcap + (oldcap+3*threshold)/4
}

输出结果

    cap_test.go:17: Added element 0, length: 1, actual capacity: 1, expected capacity: 1
    cap_test.go:17: Added element 1, length: 2, actual capacity: 2, expected capacity: 2
    cap_test.go:17: Added element 2, length: 3, actual capacity: 4, expected capacity: 4
    cap_test.go:17: Added element 4, length: 5, actual capacity: 8, expected capacity: 8
    cap_test.go:17: Added element 8, length: 9, actual capacity: 16, expected capacity: 16
    cap_test.go:17: Added element 16, length: 17, actual capacity: 32, expected capacity: 32
    cap_test.go:17: Added element 32, length: 33, actual capacity: 64, expected capacity: 64
    cap_test.go:17: Added element 64, length: 65, actual capacity: 128, expected capacity: 128
    cap_test.go:17: Added element 128, length: 129, actual capacity: 256, expected capacity: 256
    cap_test.go:17: Added element 256, length: 257, actual capacity: 512, expected capacity: 512
    cap_test.go:17: Added element 512, length: 513, actual capacity: 848, expected capacity: 832
    cap_test.go:17: Added element 848, length: 849, actual capacity: 1280, expected capacity: 1252
--- PASS: TestCap (0.00s)
PASS

为什么实际扩容与预期不符呢？

实际上，growslice 的后半部分还有更进一步的优化（内存对齐等），靠的是 roundupsize 函数，在计算完 newcap 值之后，还会有一个步骤计算最终的容量：

capmem = roundupsize(uintptr(newcap) * ptrSize)
newcap = int(capmem / ptrSize)

growslice 函数在 Go 中的实现不仅仅是简单的容量增长算法，它还涉及到内存对齐的优化，这是通过 roundupsize 函数来实现的。roundupsize 函数确保分配的内存大小是特定大小类的倍数，这有助于减少内存碎片和提高内存分配效率。我们无法直接模拟 roundupsize 函数的行为，因为这需要深入 Go 的内存分配器的实现细节。

但是确定的是，最终的容量可能会比计算出的 newcap 更大，因为要适应内存对齐的需求。