Go 语言是如何实现切片扩容

Go 语言中的切片(slice)是一个非常灵活的数据结构,它可以根据需求自动扩容。slice 的扩容机制如下:

1. 初始容量:

   • 当使用 make([]T, len, cap) 创建 slice 时,可以指定初始长度 len 和容量 cap。
   • 如果只指定长度,则容量默认等于长度。

2. 添加元素时的扩容:

   • 当向 slice 中添加元素,并且当前容量不足时,Go 运行时会自动扩容。
   • 扩容策略是: 新容量 = 旧容量 + max(旧容量, 1)。
   • 也就是说,容量每次会至少翻倍,直到满足新增元素的需求。

3. 扩容过程:

   • 分配一块新的连续内存空间,容量是旧容量的 1.5 倍或更大。
   • 将旧 slice 中的元素拷贝到新内存空间。
   • 更新 slice 的底层数组指针、长度和容量。

4. 复制数据:

   • 扩容时会将旧 slice 中的数据完整地拷贝到新的内存空间。
   • 这意味着如果 slice 中的元素是指针或其他引用类型,那么这些引用也会被拷贝。

示例代码:

package main

import "fmt"

func main() {
   
    // 初始容量为 3
    s := make([]int, 0, 3)

    // 添加元素直到触发扩容
    for i := 0; i < 10; i++ {
   
        s = append(s, i)
        fmt.Printf("len=%d, cap=%d\n", len(s), cap(s))
    }
}

输出:

len=1, cap=3
len=2, cap=3
len=3, cap=3
len=4, cap=6
len=5, cap=6
len=6, cap=6
len=7, cap=9
len=8, cap=9
len=9, cap=9
len=10, cap=15

从输出中可以看到,slice 的容量每次都会增加一倍以上,直到满足新增元素的需求。这种扩容机制保证了 slice 的灵活性和性能。