Golang数组和切片区别及切片扩容

1. 内部结构

1.1. 数组 Array

先说一下数组, 的确在 Go 语言中, 因为 slice 的存在, 使得 array 的出场率不高。但想要很好的理解 slice, 还是要先要了解 array.
Go 语言的数组和其他语言一样, 没有什么特别的地方, 就是一段以元素类型(如int)为单位的连续内存空间。数组创建时, 被初始化为元素类型的零值.

声明举例:

数组初始化的完整写法是 {1:23, 2:8, 3:12}, 只不过可以省略 index 写成 {23, 8, 12}, index 自动从 0 开始累加, 最大的 index 值决定数组长度.
如 {5: 10, 11, 12, 6: 100} 是非法的, 因为它会被转换成 {5: 10, 6: 11, 7: 12, 6: 100}, 会出现编译错误 duplicate index in array literal: 6.

1.2. 切片 Slice

slice 通常用来表示一个变长序列, 也是基于数组实现的。看下图:

图中 Q2 和 summer 是 slice, 实际就是对数组 months 引用, 只是记录了引用了数组中的那些元素.

Q2的cap:13-4=9(length(months)-截取的前一个下标);summer的cap:13-6=7

再看一下 slice 在 Go 内部的定义

第一个字段表示 array 的指针,是真实数据的指针第二个是表示 slice 的长度,第三个是表示 slice 的容量。所以 unsafe.Sizeof(切片)永远都是 24。

当把 slice 作为参数,本身传递的是值,但其内容就 byte* array,实际传递的是引用,所以可以在函数内部修改,但如果对 slice 本身做 append,而且导致 slice 进行了扩容,实际扩容的是函数内复制的一份切片,对于函数外面的切片没有变化。

结果如下:

当append(list, [params]),先判断 list 的 cap 长度是否大于等于 len(list) + len([params]),如果大于那么 cap 不变,否则 cap = 2 * max{cap(list), cap[params]},所以当 append(numbers, 2, 3, 4) cap 从 2 变成 6。

1.3. 切片 Slice越界

slice 是可伸缩变长的, 导致很多人误以为 slice 是不会越界的, 下面我们来阐述下几种越界情况.

以上图中右侧的 summer 为例, summer[4] = "hello" 肯定会出现 index out of range 的 panic 信息, 尽管 cap(summer) = 7, 但 summer[4] 超出了 len(summer) = 3 的范围.

再看下面这个例子:

arr[:3:5] 基于 arr 创建一个 slice, len 是 3, cap 是 5; 然后再在这个 slice 的基础上分别创建一个 len = 4 和 len = 8 的 slice. 前者运行正常, 后者因超出 cap = 5 范围而 panic, 尽管后者实际想要的内存并没有超出 arr 数组范围.

slice 的操作记住两点:

  1. 数据直接访问(slice[index])时, index 值不能超过 len(slice) 范围
  2. 创建切片(slice[start:end])时, start 和 end 指定的区间不能超过 cap(slice) 范围
    • 创建一个 slice := make([]int, 5, 10), 然后 slice[8] 和 slice[:8] 的运行结果是什么? slice[8] 会 panic, 而 slice[:8] 正常返回.

2. 申请方式和初始化方式不同

3. 长度为 0

3.1. 数组 Array

比较特别的就是 [0]int, 长度为 0 的数组. 这种不占有任何内存空间的数据类型实际上是无意义的, 所以 Go 语言对此类数据特殊处理了一下, 此外还包括 struct{}, [10]struct{} 等。

前 5 个变量的内存地址一样, 第 6 个变量 f 有一个真实可用的内存. 也就是说 Go 并没有为 [0]int 和 struct{} 这类数据真正分配地址空间, 而是统一使用同一个地址空间.
这类数据结构在 map 中经常应用, 比如 map[string]struct{}. 声明这样一个 map 类型来标记某个 key 是否存在. 在 key 值很多的情况下, 要比 map[string]bool 之类的结构节约很多内存, 同时也减小 GC 压力.

3.2. 切片 Slice

  • 值为 nil 的 slice 变量的 len 和 cap 都是 0. 虽然它没有指向具体某个数组(slice.array 为空), 但是它的 slice.len 和 slice.cap 默认就是 0.

4. 作为函数参数

  • func(arr []int) 这种函数对参数 arr 的修改, 会影响到外面数值, 因为函数内部操作的内存与外界是同一个. 这是 slice 和 array 的主要区别之一。slice看起来像个引用传递,原因是,在slice的结构内部有一个指向底层数组的指针,slice的下标取值,通过类似C语言指针取值的方式,实际操作底层数组。

5. 扩容性

  • 数组一开始已定义好连续内存,之后再分配很难。
  • 如果使用切片,其扩容性将大大提高。当slice的cap不够时,将自动扩容,扩容后的slice可能与原来的slice地址不一样。

5.1. 切片拷贝例1

append 会让切片和与他相关的切片脱钩,但地址不变;

5.2. 切片拷贝例2

以上代码执行输出结果为:

len:1 cap: 1 array ptr: 0xc8200640f0
len:2 cap: 2 array ptr: 0xc820064110
len:3 cap: 4 array ptr: 0xc8200680c0
len:4 cap: 4 array ptr: 0xc8200680c0
len:5 cap: 8 array ptr: 0xc82006c080
len:6 cap: 8 array ptr: 0xc82006c080
Array: [0 0 1 2 3 4]

  • 大概解释:每次cap改变的时候指向array内存的指针都在变化。当在使用 append 的时候,如果 cap==len 了这个时候就会新开辟一块更大内存,然后把之前的数据复制过去(实际go在append的时候放大cap是有规律的。在 cap 小于1024的情况下是每次扩大到 2 cap ,当大于1024之后就每次扩大到 1.25 cap 。所以上面的测试中cap变化是 1, 2, 4, 8); 但是这么说也不完全准确,需要根据具体情况决定。见下一章append数据空间申请。

5.3. append函数深入理解

append函数的数据空间申请

  • 问题:len=5 cap=6 slice=[0 1 2 3 4].为什么这里的 cap 不是 5 呢?答案请往下看

5.4. 扩容原理

可以通过查看$GOROOT/src/cmd/compile/internal/gc/walk.go $GOROOT/src/runtime/slice.go 源码,其中扩容相关代码如下,调用顺序依次appendslice中调用growslice:

从上面的代码可以看出以下内容:

  • 步骤一:appendslice中比较参数
    append 发生扩容时,原有切片长度简述为l1,容量c;添加切片长度l2;则新申请容量是n = l1 + l2;
    当新申请容量n大于原有切片容量c时,调用growslice函数;

  • 步骤二:growslice
    首先判断,如果新申请容量(cap)大于2倍的旧容量(old.cap),最终容量(newcap)就是新申请的容量(cap)。
    否则判断,如果旧切片的长度小于1024,则最终容量(newcap)就是旧容量(old.cap)的两倍,即(newcap=doublecap),
    否则判断,如果旧切片长度大于等于1024,则最终容量(newcap)从旧容量(old.cap)开始循环增加原来的1/4,即(newcap=old.cap,for {newcap += newcap/4})直到最终容量(newcap)大于等于新申请的容量(cap),即(newcap >= cap)
    如果最终容量(cap)计算值溢出,则最终容量(cap)就是新申请容量(cap)。
    需要注意的是,切片扩容还会根据切片中元素的类型不同而做不同的处理,比如int和string类型的处理方式就不一样。

  • 步骤三:roundupsize向上取整大小函数
    在这里进行扩容大小的计算,传入参数为bit。如果申请空间为5字节40bit,则入参size uintptr值为40;
    接着调用了 roundupsize 函数,et.size=8,传入 40,所以divRoundUp返回为= 5;获取 size_to_class8 数组中索引为 5 的元素为 5;获取 class_to_size 中索引为 5 的元素为 48,roundupsize 返回48,表示比特大小。
    最终,新的 slice 的容量为 6

6. 参考文章

赞赏

微信赞赏支付宝赞赏

发表评论

邮箱地址不会被公开。 必填项已用*标注