深入理解 Go 数组、切片、字符串

打个广告：欢迎关注我的微信公众号，在这里您将获取更全面、更新颖的文章！

原文链接：深入理解 Go 数组、切片、字符串 欢迎点赞关注

前言

为什么在一篇文章里同时介绍数组、切片、字符串，了解这三个数据类型底层数据结构的同学一定知道，在go中这三个数据类型，底层有一定联系，切片和字符串底层都是基于数组实现的，字符切片和字符串之间还可以相互转换。

数组

类型

数组是一种复合类型，具体类型是由：数组的长度 + 数组元素的类型决定的，下面的是两种数组类型：

[10]int // 长度为10的int数组
[11]int // 长度为11的int数组

只有长度和元素类型都相同才是同一类型。

访问

我们通过指向数组开头的指针、元素的数量以及元素类型占的空间大小表示数组。如果我们不知道数组中元素的数量，访问时可能发生越界；而如果不知道数组中元素类型的大小，就没有办法知道应该一次取出多少字节的数据，无论丢失了哪个信息，我们都无法知道这片连续的内存空间到底存储了什么数据：

访问索引为1的元素只需要数组的起始地址偏移1个元素大小即可：P + 1 * size。

越界检查

Go 语言中可以在编译期间的静态类型检查判断数组越界，cmd/compile/internal/gc.typecheck1 会验证访问数组的索引：

func typecheck1(n *Node, top int) (res *Node) {
        switch n.Op {
        case OINDEX:
                ok |= ctxExpr
                l := n.Left  // array
                r := n.Right // index
                switch n.Left.Type.Etype {
                case TSTRING, TARRAY, TSLICE:
                        ...
                        if n.Right.Type != nil && !n.Right.Type.IsInteger() {
                                yyerror("non-integer array index %v", n.Right)
                                break
                        }
                        if !n.Bounded() && Isconst(n.Right, CTINT) {
                                x := n.Right.Int64()
                                if x < 0 {
                                        yyerror("invalid array index %v (index must be non-negative)", n.Right)
                                } else if n.Left.Type.IsArray() && x >= n.Left.Type.NumElem() {
                                        yyerror("invalid array index %v (out of bounds for %d-element array)", n.Right, n.Left.Type.NumElem())
                                }
                        }
                }
        ...
        }
}

1. 访问数组的索引是非整数时，报错 “non-integer array index %v”；

2. 访问数组的索引是负数时，报错 “invalid array index %v (index must be non-negative)"；

3. 访问数组的索引越界时，报错 “invalid array index %v (out of bounds for %d-element array)"；

除了上面的检查外，在生成SSA期间还会插入越界检查指令，我们编写如下代码，然后生成SSA中间代码：

package check

func outOfRange() int {
        arr := [3]int{1, 2, 3}
        i := 4
        elem := arr[i]return elem
}

$ GOSSAFUNC=outOfRange go build array.go
dumped SSA to ./ssa.html

ssa.html 中间代码如下：

b1:...
    v22 (6) = LocalAddr <*[3]int> {arr} v2 v20
    v23 (6) = IsInBounds <bool> v21 v11 // 判断idx是否小于len
If v23 → b2 b3 (likely) (6) // 如果小于执行 b2，否则（越界）执行 b3

b2: ← b1-
    v26 (6) = PtrIndex <*int> v22 v21
    v27 (6) = Copy <mem> v20
    v28 (6) = Load <int> v26 v27 (elem[int])...
Ret v30 (+7)

b3: ← b1-
    v24 (6) = Copy <mem> v20
    v25 (6) = PanicBounds <mem> [0] v21 v11 v24 // panic 退出
Exit v25 (6)

切片

Go 语言切片可以看做对数组的封账，Go 数组的长度不可改变，在特定场景中这样的集合就不太适用，Go 中提供了一种灵活，功能强悍的内置类型切片("动态数组")，与数组相比切片的长度是不固定的，可以追加元素，在追加时可能使切片的容量增大。

数据结构

编译期间的切片是 cmd/compile/internal/types.Slice 类型的，但是在运行时切片可以由如下的 reflect.SliceHeader 结构体表示，其中:

• Data 是指向数组的指针;

• Len 是当前切片的长度；

• Cap 是当前切片的容量，即 Data 数组的大小：

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

Data 是一片连续的内存空间，这片内存空间可以用于存储切片中的全部元素，数组中的元素只是逻辑上的概念，底层存储其实都是连续的，所以我们可以将切片理解成一片连续的内存空间加上长度与容量的标识。

创建切片

使用make创建Slice

使用make来创建Slice时，可以同时指定长度和容量，创建时底层会分配一个数组，数组的长度即容量。

例如，语句slice := make([]int, 5, 10)所创建的Slice，结构如下图所示：

该Slice长度为5，即可以使用下标slice[0] ~ slice[4]来操作里面的元素，capacity为10，表示后续向slice添加新的元素时可以不必重新分配内存，直接使用预留内存即可。

使用数组创建Slice

使用数组来创建Slice时，Slice将与原数组共用一部分内存。

例如，语句slice := array[5:7]所创建的Slice，结构如下图所示：

切片从数组array[5]开始，到数组array[7]结束（不含array[7]），即切片长度为2，数组后面的内容都作为切片的预留内存，即capacity为5。

数组和切片操作可能作用于同一块内存，这也是使用过程中需要注意的地方。

切片扩容

使用append向Slice追加元素时，如果Slice空间不足，将会触发Slice扩容，扩容实际上重新一配一块更大的内存，将原Slice数据拷贝进新Slice，然后返回新Slice，扩容后再将数据追加进去。

例如，当向一个capacity为5，且length也为5的Slice再次追加1个元素时，就会发生扩容，如下图所示：

当切片的容量不足时，我们会调用 runtime.growslice 函数为切片扩容，扩容是为切片分配新的内存空间并拷贝原切片中元素的过程，我们先来看新切片的容量是如何确定的：

func growslice(et *_type, old slice, cap int) slice {
        newcap := old.cap
        doublecap := newcap + newcap
        if cap > doublecap {
                newcap = cap
        } else {
                if old.len < 1024 {
                        newcap = doublecap
                } else {
                        for 0 < newcap && newcap < cap {
                                newcap += newcap / 4
                        }
                        if newcap <= 0 {
                                newcap = cap
                        }
                }
        }

在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

1. 如果期望容量大于当前容量的两倍就会使用期望容量；

2. 如果当前切片的长度小于 1024 就会将容量翻倍；

3. 如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

上述代码片段仅会确定切片的大致容量，下面还需要根据切片中的元素大小对齐内存，当数组中元素所占的字节大小为 1、8 或者 2 的倍数时，运行时会使用如下所示的代码对齐内存：

var overflow bool
    var lenmem, newlenmem, capmem uintptr
    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 == sys.PtrSize:
            lenmem = uintptr(old.len) * sys.PtrSize
            newlenmem = uintptr(cap) * sys.PtrSize
            capmem = roundupsize(uintptr(newcap) * sys.PtrSize)
            overflow = uintptr(newcap) > maxAlloc/sys.PtrSize
            newcap = int(capmem / sys.PtrSize)
    case isPowerOfTwo(et.size):
            ...
    default:
            ...
    }

runtime.roundupsize 函数会将待申请的内存向上取整，取整时会使用 runtime.class_to_size 数组，使用该数组中的整数可以提高内存的分配效率并减少碎片，我们会在内存分配一节详细介绍该数组的作用：

var class_to_size = [_NumSizeClasses]uint16{
    0,
    8,
    16,
    32,
    48,
    64,
    80,
    ...,
}

下面举个例子，说明一下扩容和内存对齐的效果：

var arr []int64
arr = append(arr, 1, 2, 3, 4, 5)

fmt.Println(cap(arr)) // 6

上面代码里会触发 runtime.growslice 函数扩容 arr 切片并传入期望的新容量 5，这时期望分配的内存大小为 40 字节；不过因为切片中的元素大小等于 sys.PtrSize，所以运行时会调用 runtime.roundupsize 向上取整内存的大小到 48 字节，所以新切片的容量为 48 / 8 = 6。

切片copy

使用copy()内置函数拷贝两个切片时，会将源切片的数据逐个拷贝到目的切片指向的数组中，拷贝数量取两个切片长度的最小值，例如长度为10的切片拷贝到长度为5的切片时，将会拷贝5个元素，也就是说，copy过程中不会发生扩容。

func slicecopy(to, fm slice, width uintptr) int {
        if fm.len == 0 || to.len == 0 {
                return 0
        }
        n := fm.len
        if to.len < n {
                n = to.len
        }
        if width == 0 {
                return n
        }
        ...

        size := uintptr(n) * width
        if size == 1 {
                *(*byte)(to.array) = *(*byte)(fm.array)
        } else {
                memmove(to.array, fm.array, size)
        }
        return n
}

其他知识点

nil 切片和空切片

// nil切片
var s1 []int
    
// nil切片指针
s2 := new([]int)

// 空切片
s3 := make([]int, 0)
s4 := []int{}

sh1 := (*(*reflect.SliceHeader)(unsafe.Pointer(&s1)))
sh3 := (*(*reflect.SliceHeader)(unsafe.Pointer(&s3)))           

用debug看一下s1 s2 s3 s4的内存情况：

通过debug可以发现，nil切片的data指针指向的是nil，空切片的data指针指向的是空数组：

切片作为函数参数

在Go函数中，函数的参数传递均是值传递。那么，将切片通过参数传递给函数，其实质是复制了slice结构体对象，两个slice结构体的字段值均相等。正常情况下，由于函数内slice结构体的array和函数外slice结构体的array指向的是同一底层数组，所以当对底层数组中的数据做修改时，两者均会受到影响。

func main() {
    arr := []int{1,2,3}
    update(arr)
    fmt.Println(arr[1]) // 100
}

func update(arr []int) {
    arr[1] = 100
}

但是存在这样的问题：如果指向底层数组的指针被覆盖或者修改（copy、重分配、append触发扩容），此时函数内部对数据的修改将不再影响到外部的切片，代表长度的len和容量cap也均不会被修改。

func main() {
    arr := []int{1,2,3}
    update(arr)
    fmt.Println(len(arr)) // 3
}

func update(arr []int) {
    arr = append(arr, 4)
    fmt.Println(len(arr)) // 4
}

字符串

Go标准库builtin给出了所有内置类型的定义。 源代码位于src/builtin/builtin.go，其中关于string的描述如下:

// string is the set of all strings of 8-bit bytes, conventionally but not// necessarily representing UTF-8-encoded text. A string may be empty, but// not nil. Values of string type are immutable.type string string
解释

所以string是8比特字节的集合，通常但并不一定是UTF-8编码的文本。

另外，还提到了两点，非常重要：

• string可以为空（长度为0），但不会是nil；

• string对象不可以修改。

数据结构

字符串在 Go 语言中的接口其实非常简单，每一个字符串在运行时都会使用如下的 reflect.StringHeader 表示，其中包含指向字节数组的指针和数组的大小：

type StringHeader struct {
    Data uintptr
    Len  int
}

因为字符串作为只读的类型，我们并不会直接向字符串直接追加元素改变其本身的内存空间，所有在字符串上的写入操作都是通过拷贝实现的。

字符串拼接

Go 语言拼接字符串会使用 + 符号，底层实现是 runtime.concatstrings，它会先对遍历传入的切片参数，再过滤空字符串并计算拼接后字符串的长度。

func concatstrings(buf *tmpBuf, a []string) string {
        idx := 0
        l := 0
        count := 0
        for i, x := range a {
                n := len(x)
                if n == 0 {
                        continue
                }
                l += n
                count++
                idx = i
        }
        if count == 0 {
                return ""
        }
        if count == 1 && (buf != nil || !stringDataOnStack(a[idx])) {
                return a[idx]
        }
        s, b := rawstringtmp(buf, l)
        for _, x := range a {
                copy(b, x)
                b = b[len(x):]
        }
        return s
}

拼接的过程：

1. 通过遍历计算新字符串的长度

2. 生成新字符串

3. 在通过遍历，将原字符串拷贝到新字符串中

字节串与字符数组互转

从字节数组到字符串的转换需要使用 runtime.slicebytetostring 函数，例如：string(bytes)，该函数在函数体中会先处理两种比较常见的情况，也就是长度为 0 或者 1 的字节数组，这两种情况处理起来都非常简单：

func slicebytetostring(buf *tmpBuf, b []byte) (str string) {
        l := len(b)
        if l == 0 {
                return ""
        }
        if l == 1 {
                stringStructOf(&str).str = unsafe.Pointer(&staticbytes[b[0]])
                stringStructOf(&str).len = 1
                return
        }
        var p unsafe.Pointer
        if buf != nil && len(b) <= len(buf) {
                p = unsafe.Pointer(buf)
        } else {
                p = mallocgc(uintptr(len(b)), nil, false)
        }
        stringStructOf(&str).str = p
        stringStructOf(&str).len = len(b)
        memmove(p, (*(*slice)(unsafe.Pointer(&b))).array, uintptr(len(b)))
        return
}

处理过后会根据传入的缓冲区大小决定是否需要为新字符串分配一片内存空间，runtime.stringStructOf 会将传入的字符串指针转换成 runtime.stringStruct 结构体指针，然后设置结构体持有的字符串指针 str 和长度 len，最后通过 runtime.memmove 将原 []byte 中的字节全部复制到新的内存空间中。

当我们想要将字符串转换成 []byte 类型时，需要使用 runtime.stringtoslicebyte 函数，该函数的实现非常容易理解：

func stringtoslicebyte(buf *tmpBuf, s string) []byte {
        var b []byte
        if buf != nil && len(s) <= len(buf) {
                *buf = tmpBuf{}
                b = buf[:len(s)]
        } else {
                b = rawbyteslice(len(s))
        }
        copy(b, s)
        return b
}

上述函数会根据是否传入缓冲区做出不同的处理：

• 当传入缓冲区时，它会使用传入的缓冲区存储 []byte；

• 当没有传入缓冲区时，运行时会调用 runtime.rawbyteslice 创建新的字节切片并将字符串中的内容拷贝过去；

上面的两种转换方式都进行了内存复制，会存在一些性能问题，还有一种通过unsafe包进行类型转换的方式，不涉及到内存拷贝，但是unsafe包并不推荐在生产环境使用，所以大家使用时要谨慎：

// string转ytes
func Str2sbyte(s string) (b []byte) {
    *(*string)(unsafe.Pointer(&b)) = s        // 把s的地址付给b
    *(*int)(unsafe.Pointer(uintptr(unsafe.Pointer(&b)) + 2*unsafe.Sizeof(&b))) = len(s)        // 修改容量为长度
    return
}

// []byte转string
func Sbyte2str(b []byte) string {
    return *(*string)(unsafe.Pointer(&b))
}

参考

https://draveness.me/golang/docs/part2-foundation/ch03-datastructure/golang-array

https://books.studygolang.com/GoExpertProgramming/chapter01/1.2-slice.html

本文由 mdnice 多平台发布