Slice

1、概述：

Slice又称动态数组，依托数组实现，可以方便的进行扩容、传递等，实际使用中比数组更灵活。

2、实现原理

Slice依托数组实现，底层数组对用户屏蔽，在底层数组容量不足时可以实现自动重分配并生成新的Slice。接下来按照实际使用场景分别介绍其实现机制。

2.1 Slcie底层结构

源码包中src/runtime/slice.go:slice定义了Slice的数据结构：

type slice struct {
	array unsafe.Pointer   //指向底层数组的指针
	len   int   //切片长度
	cap   int   //切片容量
}

从数据结构看Slice很清晰, array指针指向底层数组，len表示切片长度，cap表示底层数组容量。

2.2 Slice的创建

2.2.1 使用 make 创建 slice

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

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

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

2.2.2 使用数组创建Slice

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

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

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

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

2.3 slice的容量

• 如果是make声明，slice := make([]int, 5, 10)，指定了容量是几，那就是几，如果没有指定，那么默认是和长度一样。
• 如果是数组声明，slice := array[5:7] ，如果没有指定最大值（也就是第三个方括号里面的参数），则容量是从开始位置到数组末尾。 如果指定了最大值（也就是第三个方括号里面的参数），则容量是从开始位置到最大值。
• 如果是 var slice []int slice = append(slice, 1, 2, 3) 这样声明slice, 目前不清楚

2.4 Slice 扩容

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

golang slice (切片) 扩容机制详解（1.18版本后）

growslice()方法**：用于 slice 的扩容

func growslice(et *_type, old slice, cap int) slice {
   //  ......
	newcap := old.cap
	doublecap := newcap + newcap    //双倍扩容（原容量的两倍）
	if cap > doublecap {   //如果所需容量大于 两倍扩容，则直接扩容到所需容量
		newcap = cap
	} else {
		const threshold = 256   //这里设置了一个 阈值 -- 256
		if old.cap < threshold {		//如果旧容量 小于 256，则两倍扩容
			newcap = doublecap   
		} else {
	    // 检查 0 < newcap 以检测溢出并防止无限循环。
			for 0 < newcap && newcap < cap {   //如果新容量 > 0  并且 原容量 小于 所需容量
			
               // 从小片的增长2x过渡到大片的增长1.25x。这个公式给出了两者之间的平滑过渡。
				newcap += (newcap + 3*threshold) / 4
                //新容量是 = 1.25 原容量 + 3/4 阈值 
                
              //当newcap计算溢出时，将newcap设置为请求的上限。
			if newcap <= 0 {   // 如果发生了溢出，将新容量设置为请求的容量大小
				newcap = cap
			}
		}
	}
}

具体情况如下：

1. 如果请求容量 大于 两倍现有容量 ，则新容量 直接为请求容量

2. 否则（请求容量 小于等于 两倍现有容量）

​ 如果 现有容量 小于 256 ，则新容量是原来的两倍

​ 否则：新容量 = 1.25 原容量 + 3/4 阈值 “这个公式给出了从1.25倍增长 过渡到2 倍增长，两者之间的平滑过渡。” 在此情况下，如果发生了溢出，将新容量设置为请求的容量大小.(这里的系数会随着容量的大小发生变化，从2.0到无线接近1.25)

扩容容量的选择遵循以下规则：

在 1.18 版本前，切片扩容，在容量小于1024时，以2倍大小扩容。超过1024后，以1.25倍扩容。

在1.18版本后，切片扩容，在容量小于256时，以2倍大小扩容。超过256后，以（1.25倍+0.75阈值）扩容。

使用append()向Slice添加一个元素的实现步骤如下：

1. 假如Slice容量够用，则将新元素追加进去，Slice.len++，返回原Slice
2. 原Slice容量不够，则将Slice先扩容，扩容后得到新Slice，再将新元素追加进新Slice，Slice.len++，返回新的Slice。

2.5 Slice Copy

使用copy()内置函数拷贝两个切片时，会将源切片的数据逐个拷贝到目的切片指向的数组中，拷贝数量取决于两个切片长度的最小值。

例如长度为10的切片拷贝到长度为5的切片时，将会拷贝5个元素。

也就是说，copy过程中不会发生扩容。

2.6 特殊切片

跟据数组或切片生成新的切片一般使用slice := array[start:end]方式，这种新生成的切片并没有指定切片的容量，实际上新切片的容量是从start开始直至array的结束。

比如下面两个切片，长度和容量都是一致的，使用共同的内存地址：

sliceA := make([]int, 5, 10)
sliceB := sliceA[0:5]

根据数组或切片生成切片还有另一种写法，即切片同时也指定容量，即slice[start : end : cap], 其中cap即为新切片的容量，当然容量不能超过原切片实际值，如下所示：

    sliceA := make([]int, 5, 10)  //length = 5; capacity = 10
    sliceB := sliceA[0:5]         //length = 5; capacity = 10
    sliceC := sliceA[0:5:5]       //length = 5; capacity = 5

这切片方法不常见，在Golang源码里能够见到，不过非常利于切片的理解。

2.7 Slice的函数传递

首先给出结论：slice在作为函数参数进行传递时，分两种情况：

1. 如果不发生扩容，则是引用传递，也就是函数内对切片的操作会影响函数外的切片。
2. 如果发生扩容，则函数内的切片的内存地址发生变化，此时对函数内切片的操作不会影响函数外。

因此，如果想要函数内对切片的操作始终影响函数外，那么在传参时使用指针即可。

代码示例：

func Slicefunc2(paramSlice *[]int) {
	paramSliceV := *paramSlice
	paramSliceV[2] = 9
	for index := 0; index < 6; index++ {
		*paramSlice = append(*paramSlice, index)
	}
	fmt.Printf("Slicefunc2函数内slice的值为：%v\n", paramSlice)
}
func Slicefunc1(paramSlice []int) {
	paramSlice[2] = 9
	for index := 0; index < 6; index++ {
		paramSlice = append(paramSlice, index)
	}
	fmt.Printf("Slicefunc1函数内slice的值为：%v\n", paramSlice)
}
func main() {
	slice := make([]int, 5)
	slice[0] = 2
	slice[1] = 3
	fmt.Println("main函数中的slice: ", slice)
	Slicefunc1(slice)
	fmt.Println("经过Slicefunc1后，main函数中的slice: ", slice)
	Slicefunc2(&slice)
	fmt.Println("经过Slicefunc2后，main函数中的slice: ", slice)
}

//输出结果
//main函数中的slice:  [2 3 0 0 0]
//Slicefunc1函数内slice的值为：[2 3 9 0 0 0 1 2 3 4 5]
//经过Slicefunc1后，main函数中的slice:  [2 3 9 0 0]
//Slicefunc2函数内slice的值为：&[2 3 9 0 0 0 1 2 3 4 5]
//经过Slicefunc2后，main函数中的slice:  [2 3 9 0 0 0 1 2 3 4 5]

3. 编程Tips

创建切片时可跟据实际需要预分配容量，尽量避免追加过程中扩容操作，有利于提升性能；

• 切片拷贝时需要判断实际拷贝的元素个数
• 谨慎使用多个切片操作同一个数组，以防读写冲突

4. Slice总结

• 每个切片都指向一个底层数组
• 每个切片都保存了当前切片的长度、底层数组可用容量
• 使用len()计算切片长度时间复杂度为O(1)，不需要遍历切片
• 使用cap()计算切片容量时间复杂度为O(1)，不需要遍历切片
• 通过函数传递切片时，不会拷贝整个切片，因为切片本身只是个结构体而矣
• 使用append()向切片追加元素时有可能触发扩容，扩容后将会生成新的切片