首页 > 编程知识 正文

golang切片底层原理,go切片底层实现

时间:2023-05-05 03:41:56 阅读:157318 作者:1739

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

片是Go中的基本数据结构,可以使用该结构管理数据集合。 切片的设计理念来自动态数组的概念,是为了让开发者更容易地自动增减一个数据结构。 但是切片本身不是动态数据或数组指针。 切片中常见的操作有reslice、append、copy。 同时,切片具有可索引、可重复的优良特性。

切片的数据结构切片本身不是动态数组或数组指针。 其内部实现的数据结构通过指针参照下级数组,设置相关属性将数据的读写操作限定在指定区域内。 切片本身是只读对象,其作用类似于数组指针的封装。

切片是引用类型的,因为切片是对数组中连续片段的引用。 因此,它类似于C/C的数组类型和Python的list类型。 此片段可以是整个数组,也可以是由开始索引和结束索引标识的某些项目的子集。 请注意,用于结束索引标记的项目不包括在切片中。 切片有一个指向数组的动态窗口。

指定项目的切片索引可能小于关联数组中相同元素的索引。 与数组不同,切片的长度可以在运行时更改。 最小为0,最大为相关数组的长度。 切片是可变长度的数组。

Slice的数据结构定义如下:

typeslicestruct { array unsafe.pointerlenintcapint }

片的结构体由3部分构成,Pointer是指向数组的指针,len是当前片的长度,cap是当前片的容量。 cap总是在len以上。

切片放大需要在切片容量填满时进行放大。 如何扩大,战略是什么?

funcgrowslice(et*_type,old slice,cap int ) slice ) ifraceenabled ) callerPC:=getcallerpc ) unsafe.pointer ) funcPC ) growslice ) } ifmsanenabled { msan read } old.array,uint ppay ifcapold.cap { panic (errorstring ) grow slice 3360 cc return slice { unsafe.pointer (zero base ),old.len, cap} } //此处为扩展策略newcap :=old.capdoublecap :=newcapnewcapifcapdoublecap { newcap=cap } else { if old.len 1024 var lenmem,newlenmem,capmemuintptrconstptrsize=unsafe.sizeof () byte(nil ) ) switch et.size (case 1: len mem=uii capmem=roundupsize (uintptr (newcap ) ) newcap=int ) capmem ) caseptrsize 3360 len mem=uintptr (old.len ) * ptrsizenenenenenene ptrsizecapmem=roundupsize (uintptr (newcap ) ptrsize ) newcap=int (capmem/ptrsize ) default:lenmem=uintptr )

uintptr(newcap) * et.size) newcap = int(capmem / et.size) } // 判断非法的值,保证容量是在增加,并且容量不超过最大容量 if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) { panic(errorString("growslice: cap out of range")) } var p unsafe.Pointer if et.kind&kindNoPointers != 0 { // 在老的切片后面继续扩充容量 p = mallocgc(capmem, nil, false) // 将 lenmem 这个多个 bytes 从 old.array地址 拷贝到 p 的地址处 memmove(p, old.array, lenmem) // 先将 P 地址加上新的容量得到新切片容量的地址,然后将新切片容量地址后面的 capmem-newlenmem 个 bytes 这块内存初始化。为之后继续 append() 操作腾出空间。 memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem) } else { // 重新申请新的数组给新切片 // 重新申请 capmen 这个大的内存地址,并且初始化为0值 p = mallocgc(capmem, et, true) if !writeBarrier.enabled { // 如果还不能打开写锁,那么只能把 lenmem 大小的 bytes 字节从 old.array 拷贝到 p 的地址处 memmove(p, old.array, lenmem) } else { // 循环拷贝老的切片的值 for i := uintptr(0); i < lenmem; i += et.size { typedmemmove(et, add(p, i), add(old.array, i)) } } } // 返回最终新切片,容量更新为最新扩容之后的容量 return slice{p, old.len, newcap}} 扩容策略

先看看扩容策略。

func main() { slice := []int{10, 20, 30, 40} newSlice := append(slice, 50) fmt.Printf("Before slice = %v, Pointer = %p, len = %d, cap = %dn", slice, &slice, len(slice), cap(slice)) fmt.Printf("Before newSlice = %v, Pointer = %p, len = %d, cap = %dn", newSlice, &newSlice, len(newSlice), cap(newSlice)) newSlice[1] += 10 fmt.Printf("After slice = %v, Pointer = %p, len = %d, cap = %dn", slice, &slice, len(slice), cap(slice)) fmt.Printf("After newSlice = %v, Pointer = %p, len = %d, cap = %dn", newSlice, &newSlice, len(newSlice), cap(newSlice))}

输出结果:

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

用图表示出上述过程。

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

Go 中切片扩容的策略是这样的:

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

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

注意:扩容扩大的容量都是针对原来的容量而言的,而不是针对原来数组的长度而言的。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。