之前面腾讯的时候问到 Slice 把我问懵了，还是太菜了，只是简单的了解了一下 Slice 的底层结构，但是经不起深挖，基础有点太弱了。

String

底层结构

一个字符串是一个不可改变的字节序列，字符串通常是用来包含人类可读的文本数据。和数组不同的是，字符串的元素不可修改，是一个只读的字节数组。每个字符串的长度虽然也是固定的，但是字符串的长度并不是字符串类型的一部分。由于 Go 语言的源代码要求是 UTF8 编码，导致 Go 源代码中出现的字符串面值常量一般也是 UTF8 编码的。

源代码中的文本字符串通常被解释为采用 UTF8 编码的 Unicode 码点（rune）序列。因为字节序列对应的是只读的字节序列，因此字符串可以包含任意的数据，包括 byte 值 0。我们也可以用字符串表示 GBK 等非 UTF8 编码的数据，不过这种时候将字符串看作是一个只读的二进制数组更准确，因为 for range 等语法并不能支持非 UTF8 编码的字符串的遍历。

Golang 中 String 的定义如下（reflect.StringHeader）在 Go 1.20 之后就被废弃了，因为 uintptr 过于灵活，导致被滥用：

1
2
3
4
5
6
type StringHeader struct {
    // uintptr is an integer type that is large enough to hold the bit pattern of
    // any pointer.
    Data uintptr    // 指向底层数组
    Len  int
}

uintptr 是 Go（Golang）语言中的一种内置类型，全称是 “unsigned integer large enough to store the uninterpreted bits of a pointer value”。它的主要作用是用于将指针转换为整数，或者将整数转换回指针，但它本身并不表示一个指针。

alt text
可以发现，底层保存的方式就是和 []byte 保存方式一致。

1
2
3
var data = [...]byte{
    'h', 'e', 'l', 'l', 'o', ',', ' ', 'w', 'o', 'r', 'l', 'd',
}

字符串不是切片，但是也支持切片操作，不同的切片底层也是访问的同一个字符串数组。

1
2
3
4
5
6
7
8
9
s := "hello, world"
hello := s[:5]
world := s[7:]

// 简单来说就是改变了，len 的值
s1 := "hello, world"[:5] 
// 这是既改变了 Data 的偏移量，又改变了 len 的大小。
s2 := "hello, world"[7:]
// 这也解释了为什么切片是左开右闭的原因。

编码和解码

由于 Go 语言规范中，Go 语言的所有源文件都是 utf-8 进行编码的，当进行遍历的时候可能会出现乱码的情况，此时可以根据需要将其转化为 []byte 类型或者 []rune。

为什么会出现乱码，简单来说就是字符串被拆解了。在书中有一个示例：

1
2
3
4
s := "hello, 世界"
for i := 0; i < len(s); i++ {
    fmt.Printf("%c ", s[i]) // 错误解码
}

汉字需要三个字节进行编码，但是当你遍历的时候其实是一个一个读取的，这就会导致出现解码失败的现象。
alt text

因此，可以根据需要转化为 []byte 或者 []rune。
- []byte 不进行解码，直接使用二进制进行访问
- []rune 解码后转化为 Unicode 字符。

其中 rune 时 int32 的别名，并不是单独定义的数据结构。

unsafe.String、unsafe.StringData

前面说到 StringHead 被废弃了，为什么呢？根据 StringHeader

StringHeader is the runtime representation of a string. It cannot be used safely or portably and its representation may change in a later release. Moreover, the Data field is not sufficient to guarantee the data it references will not be garbage collected, so programs must keep a separate, correctly typed pointer to the underlying data.
StringHeader是字符串的运行时表示。它不能安全或可移植地使用，它的表示可能会在以后的版本中发生变化。此外，Data字段不足以保证它引用的数据不会被垃圾收集，因此程序必须保留一个单独的、类型正确的指向底层数据的指针。

看不懂官方给的原因，因此可以参考一下这个博客 别乱用了，用新的。Go SliceHeader 和 StringHeader 将会被废弃！

简单来说为什么出现这种情况，因为经常出现以下情况：
- 将 []byte 转换为 string。
- 将 string 转换为 []byte。
- 抓取数据指针（data pointer）字段用于 ffi 或其他用途。
- 将一种类型的 slice 转换为另一种类型的 slice。

一些经典的案例：

1
2
s := "脑子进煎鱼了？重背面试题(doge"
h := (*reflect.StringHeader)(unsafe.Pointer(&s))
1
2
3
4
unsafe.Pointer(&reflect.StringHeader{
  Data: uintptr(unsafe.Pointer(&s.Data[0])),
  Len:  int(s.Size),
 })

也就是将指针传递给 Data 通过传递指针减少值的复制，但是这是未定义行为，但是可行。借助 (String|Slice) Header 来实现零拷贝的 string 到 bytes 的转换。

因此更新了相关函数：

  • func String(ptr *byte, len IntegerType) string：根据数据指针和字符长度构造一个新的 string。
  • func StringData(str string) *byte：返回指向该 string 的字节数组的数据指针。
  • func SliceData(slice []ArbitraryType) *ArbitraryType：返回该 slice 的数据指针

因此，转化变成了

1
2
3
4
5
6
7
func StringToBytes(s string) []byte {
    return unsafe.Slice(unsafe.StringData(s), len(s))
}
 
func BytesToString(b []byte) string {
    return unsafe.String(&b[0], len(b))
}

具体的可以参考 unsafe 库。

Slice

简单来说 Slice 就和 C++ 里面的 vector 一样（没有认真研究过），是一个动态数组。

相关定义如下（同 StringHeader 一样，在 Go 1.20 之后就被废弃了）

SliceHeader is the runtime representation of a slice. It cannot be used safely or portably and its representation may change in a later release. Moreover, the Data field is not sufficient to guarantee the data it references will not be garbage collected, so programs must keep a separate, correctly typed pointer to the underlying data.

Deprecated: Use unsafe.Slice or unsafe.SliceData instead.

1
2
3
4
5
type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

相关内存分布如下：
alt text

和 String 差不多，就是多了一个 cap，表示的最大的容量，如果容量不足就要进行扩容。切片可以和 nil 进行比较，只有当切片底层数据指针为空时切片本身为 nil，这时候切片的长度和容量信息将是无效的。如果有切片的底层数据指针为空，但是长度和容量不为 0 的情况，那么说明切片本身已经被损坏了

相关遍历方式如下：

1
2
3
4
5
6
7
8
9
for i := range a {
    fmt.Printf("a[%d]: %d\n", i, a[i])
}
for i, v := range b {
    fmt.Printf("b[%d]: %d\n", i, v)
}
for i := 0; i < len(c); i++ {
    fmt.Printf("c[%d]: %d\n", i, c[i])
}

其实除了遍历之外，只要是切片的底层数据指针、长度和容量没有发生变化的话，对切片的遍历、元素的读取和修改都和数组是一样的。在对切片本身赋值或参数传递时，和数组指针的操作方式类似，只是复制切片头信息（reflect.SliceHeader），并不会复制底层的数据。对于类型，和数组的最大不同是，切片的类型和长度信息无关，只要是相同类型元素构成的切片均对应相同的切片类型。

append

内置的泛型函数 append 可以在切片的尾部追加 N 个元素：

1
2
3
4
var a []int
a = append(a, 1)               // 追加 1 个元素
a = append(a, 1, 2, 3)         // 追加多个元素, 手写解包方式
a = append(a, []int{1,2,3}...) // 追加 1 个切片, 切片需要解包

不过要注意的是，在容量不足的情况下，append 的操作会导致重新分配内存，可能导致巨大的内存分配和复制数据代价。即使容量足够，依然需要用 append 函数的返回值来更新切片本身，因为新切片的长度已经发生了变化。

ps: 因此当时面试的时候应该说，append 确实修改了底层的数组，但是 slice 是一个复合型结构，其中还有 len、cap，append 只是修改了数组的数据，但是并没有更新 len、 cap，因此还是需要接收来自 append 的返回值。

比如说，当使用 append 时，如果容量不足，Go 会创建一个新的底层数组，并返回一个新的切片结构。因此，append 的返回值必须接收，否则你拿到的仍然是旧的 slice，即使底层数组可能已变化。

性能优化上可以借助 copy 和 append 两种方式：

1
2
3
a = append(a, x...)       // 为 x 切片扩展足够的空间
copy(a[i+len(x):], a[i:]) // a[i:] 向后移动 len(x) 个位置
copy(a[i:], x)            // 复制新添加的切片

delete

根据要删除元素的位置有三种情况：从开头位置删除，从中间位置删除，从尾部删除。其中删除切片尾部的元素最快。

为什么位部删除最快？因为这只是一个简单的view，只需要修改 Len 的大小就可以完成。

删除开头表面上也只是改变 Data 指针和 Len，但是底层数组的前一部分仍然存在（不能被 GC 回收），可能导致 内存泄漏，因此推荐方法：

1
2
3
4
func deleteHead(s []int) []int {
    copy(s, s[1:])        // 把后面的数据往前移
    return s
}

删除中间的也是可以使用 append 或者 copy

1
2
3
4
5
6
7
a = []int{1, 2, 3, ...}

a = append(a[:i], a[i+1:]...) // 删除中间 1 个元素
a = append(a[:i], a[i+N:]...) // 删除中间 N 个元素

a = a[:i+copy(a[i:], a[i+1:])]  // 删除中间 1 个元素
a = a[:i+copy(a[i:], a[i+N:])]  // 删除中间 N 个元素

Slice 技巧

如前面所说，切片操作并不会复制底层的数据。底层的数组会被保存在内存中，直到它不再被引用。但是有时候可能会因为一个小的内存引用而导致底层整个数组处于被使用的状态，这会延迟自动内存回收器对底层数组的回收。

例如，FindPhoneNumber 函数加载整个文件到内存，然后搜索第一个出现的电话号码，最后结果以切片方式返回。

1
2
3
4
func FindPhoneNumber(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    return regexp.MustCompile("[0-9]+").Find(b)
}

这段代码返回的 []byte 指向保存整个文件的数组。因为切片引用了整个原始数组，导致自动垃圾回收器不能及时释放底层数组的空间。一个小的需求可能导致需要长时间保存整个文件数据。这虽然这并不是传统意义上的内存泄漏，但是可能会拖慢系统的整体性能。

要修复这个问题，可以将感兴趣的数据复制到一个新的切片中（数据的传值是 Go 语言编程的一个哲学，虽然传值有一定的代价，但是换取的好处是切断了对原始数据的依赖）：

1
2
3
4
5
func FindPhoneNumber(filename string) []byte {
    b, _ := ioutil.ReadFile(filename)
    b = regexp.MustCompile("[0-9]+").Find(b)
    return append([]byte{}, b...)
}

类似的问题，在删除切片元素时可能会遇到。假设切片里存放的是指针对象，那么下面删除末尾的元素后，被删除的元素依然被切片底层数组引用，从而导致不能及时被自动垃圾回收器回收（这要依赖回收器的实现方式）：

1
2
var a []*int{ ... }
a = a[:len(a)-1]    // 被删除的最后一个元素依然被引用, 可能导致 GC 操作被阻碍

保险的方式是先将需要自动内存回收的元素设置为 nil，保证自动回收器可以发现需要回收的对象，然后再进行切片的删除操作：

1
2
3
var a []*int{ ... }
a[len(a)-1] = nil // GC 回收最后一个元素内存
a = a[:len(a)-1]  // 从切片删除最后一个元素

当然，如果切片存在的周期很短的话，可以不用刻意处理这个问题。因为如果切片本身已经可以被 GC 回收的话，切片对应的每个元素自然也就是可以被回收的了。

类型强转

为了安全，当两个切片类型 []T 和 []Y 的底层原始切片类型不同时，Go 语言是无法直接转换类型的。不过安全都是有一定代价的，有时候这种转换是有它的价值的——可以简化编码或者是提升代码的性能。比如在 64 位系统上，需要对一个 []float64 切片进行高速排序，我们可以将它强制转为 []int 整数切片，然后以整数的方式进行排序（因为 float64 遵循 IEEE754 浮点数标准特性，当浮点数有序时对应的整数也必然是有序的）。

下面的代码通过两种方法将 []float64 类型的切片转换为 []int 类型的切片：

前提条件为：

  • Go 中 float64 是 8 字节
  • int 在 amd64 和 arm64 平台下也是 8 字节
  • 所以在这些平台上，float64 和 int 的底层大小一致，内存对齐也一致
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
// +build amd64 arm64

import "sort"

var a = []float64{4, 2, 5, 7, 2, 1, 88, 1}

func SortFloat64FastV1(a []float64) {
    // 强制类型转换
    // &a[0] 获取切片 a 底层数组的首地址
    // 转换为 [1<<20]int 的指针（也就是大数组）
    // 再切成和原始 a 相同长度和容量的 []int
    // 排序 b（即底层 a 的整数表示）
    var b []int = ((*[1 << 20]int)(unsafe.Pointer(&a[0])))[:len(a):cap(a)]

    // 以 int 方式给 float64 排序
    sort.Ints(b)
}

func SortFloat64FastV2(a []float64) {
    // 通过 reflect.SliceHeader 更新切片头部信息实现转换
    // 通过 reflect.SliceHeader 读取 a 的 Data/Len/Cap
    // 构造一个 []int 的 slice header，和 a 的内存结构完全一样
    // 排序 c
    var c []int
    aHdr := (*reflect.SliceHeader)(unsafe.Pointer(&a))
    cHdr := (*reflect.SliceHeader)(unsafe.Pointer(&c))
    *cHdr = *aHdr

    // 以 int 方式给 float64 排序
    sort.Ints(c)
}