golang切片底层实现

本章不属于基础部分但是面试经常会问到建议学学&＃xff0c;面试官经常问

切片是 Go 中的一种基本的数据结构&＃xff0c;使用这种结构可以用来管理数据集合。切片的设计想法是由动态数组概念而来&＃xff0c;为了开发者可以更加方便的使一个数据结构可以自动增加和减少。但是切片本身并不是动态数据或者数组指针。切片常见的操作有 reslice、append、copy。与此同时&＃xff0c;切片还具有可索引&＃xff0c;可迭代的优秀特性。

切片的数据结构

切片本身并不是动态数组或者数组指针。它内部实现的数据结构通过指针引用底层数组&＃xff0c;设定相关属性将数据读写操作限定在指定的区域内。切片本身是一个只读对象&＃xff0c;其工作机制类似数组指针的一种封装。

切片&＃xff08;slice&＃xff09;是对数组一个连续片段的引用&＃xff0c;所以切片是一个引用类型&＃xff08;因此更类似于 C/C&＃43;&＃43; 中的数组类型&＃xff0c;或者 Python 中的 list 类型&＃xff09;。这个片段可以是整个数组&＃xff0c;或者是由起始和终止索引标识的一些项的子集。需要注意的是&＃xff0c;终止索引标识的项不包括在切片内。切片提供了一个与指向数组的动态窗口。

给定项的切片索引可能比相关数组的相同元素的索引小。和数组不同的是&＃xff0c;切片的长度可以在运行时修改&＃xff0c;最小为 0 最大为相关数组的长度&＃xff1a;切片是一个长度可变的数组。

Slice 的数据结构定义如下:

type slice struct {array unsafe.Pointerlen intcap int
}


切片的结构体由3部分构成&＃xff0c;Pointer 是指向一个数组的指针&＃xff0c;len 代表当前切片的长度&＃xff0c;cap 是当前切片的容量。cap 总是大于等于 len 的。

切片扩容

当一个切片的容量满了&＃xff0c;就需要扩容了。怎么扩&＃xff0c;策略是什么&＃xff1f;

func growslice(et *_type, old slice, cap int) slice {if raceenabled {callerpc :&＃61; getcallerpc(unsafe.Pointer(&et))racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))}if msanenabled {msanread(old.array, uintptr(old.len*int(et.size)))}if et.size &＃61;&＃61; 0 {// 如果新要扩容的容量比原来的容量还要小&＃xff0c;这代表要缩容了&＃xff0c;那么可以直接报panic了。if cap doublecap {newcap &＃61; cap} else {if old.len <1024 {newcap &＃61; doublecap} else {for newcap maxSliceCap(et.size) {panic(errorString("growslice: cap out of range"))}var p unsafe.Pointerif et.kind&kindNoPointers !&＃61; 0 {// 在老的切片后面继续扩充容量p &＃61; mallocgc(capmem, nil, false)// 将 lenmem 这个多个 bytes 从 old.array地址 拷贝到 p 的地址处memmove(p, old.array, lenmem)// 先将 P 地址加上新的容量得到新切片容量的地址&＃xff0c;然后将新切片容量地址后面的 capmem-newlenmem 个 bytes 这块内存初始化。为之后继续 append() 操作腾出空间。memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)} else {// 重新申请新的数组给新切片// 重新申请 capmen 这个大的内存地址&＃xff0c;并且初始化为0值p &＃61; mallocgc(capmem, et, true)if !writeBarrier.enabled {// 如果还不能打开写锁&＃xff0c;那么只能把 lenmem 大小的 bytes 字节从 old.array 拷贝到 p 的地址处memmove(p, old.array, lenmem)} else {// 循环拷贝老的切片的值for i :&＃61; uintptr(0); i }


扩容策略

先看看扩容策略。

func main() {slice :&＃61; []int{10, 20, 30, 40}newSlice :&＃61; append(slice, 50)fmt.Printf("Before slice &＃61; %v, Pointer &＃61; %p, len &＃61; %d, cap &＃61; %d\n", slice, &slice, len(slice), cap(slice))fmt.Printf("Before newSlice &＃61; %v, Pointer &＃61; %p, len &＃61; %d, cap &＃61; %d\n", newSlice, &newSlice, len(newSlice), cap(newSlice))newSlice[1] &＃43;&＃61; 10fmt.Printf("After slice &＃61; %v, Pointer &＃61; %p, len &＃61; %d, cap &＃61; %d\n", slice, &slice, len(slice), cap(slice))fmt.Printf("After newSlice &＃61; %v, Pointer &＃61; %p, len &＃61; %d, cap &＃61; %d\n", newSlice, &newSlice, len(newSlice), cap(newSlice))
}


输出结果&＃xff1a;

Before slice &＃61; [10 20 30 40], Pointer &＃61; 0xc4200b0140, len &＃61; 4, cap &＃61; 4Before newSlice &＃61; [10 20 30 40 50], Pointer &＃61; 0xc4200b0180, len &＃61; 5, cap &＃61; 8After slice &＃61; [10 20 30 40], Pointer &＃61; 0xc4200b0140, len &＃61; 4, cap &＃61; 4After newSlice &＃61; [10 30 30 40 50], Pointer &＃61; 0xc4200b0180, len &＃61; 5, cap &＃61; 8


用图表示出上述过程。

从图上我们可以很容易的看出&＃xff0c;新的切片和之前的切片已经不同了&＃xff0c;因为新的切片更改了一个值&＃xff0c;并没有影响到原来的数组&＃xff0c;新切片指向的数组是一个全新的数组。并且 cap 容量也发生了变化。这之间究竟发生了什么呢&＃xff1f;

Go 中切片扩容的策略是这样的&＃xff1a;

如果切片的容量小于 1024 个元素&＃xff0c;于是扩容的时候就翻倍增加容量。上面那个例子也验证了这一情况&＃xff0c;总容量从原来的4个翻倍到现在的8个。

一旦元素个数超过 1024 个元素&＃xff0c;那么增长因子就变成 1.25 &＃xff0c;即每次增加原来容量的四分之一。

注意&＃xff1a;扩容扩大的容量都是针对原来的容量而言的&＃xff0c;而不是针对原来数组的长度而言的。