GO语言-切片底层探索（下）

目录

切片的底层数据结构

扩容机制

总结：

练习验证代码

这是切片的底层探索下篇，上篇地址请见：GO语言-切片底层探索（上）

在上篇我们讲解了切片的两个重要实现或者说是两个特征

1. 切片是引用类型，会进行引用传递；
2. 切片会随着元素数量的增加，进行扩容，改变其底层数组的指向；

这篇文章我们将会顺着讲解切片的底层数据结构和扩容机制

切片的底层数据结构

我们可以在src/runtime/slice.go下看到切片slice的底层数据结构：

type slice struct {
	array unsafe.Pointer
	len   int
	cap   int
}

我们可以发现，切片slice的基础定义很简单：

• 指针类型的array，指向底层数组
• int类型的len,存储切片的长度
• int类型的cap,存储切片的容量

由于在slice结构体中直接定义了len、cap字段，因此我们平常使用len(slice)和cap(slice)，其时间复杂度为O(1)，不需要遍历整个切片。

扩容机制

Go语言切片的扩容机制由基本机制和调整机制组成

func growslice(oldPtr unsafe.Pointer, newLen, oldCap, num int, et *_type) slice {
	.....
	newcap := oldCap
	doublecap := newcap + newcap
	if newLen > doublecap {
		newcap = newLen
	} else {
		const threshold = 256
		if oldCap < threshold {
			newcap = doublecap
		} else {
			// Check 0 < newcap to detect overflow
			// and prevent an infinite loop.
			for 0 < newcap && newcap < newLen {
				// Transition from growing 2x for small slices
				// to growing 1.25x for large slices. This formula
				// gives a smooth-ish transition between the two.
				newcap += (newcap + 3*threshold) / 4
			}
			// Set newcap to the requested cap when
			// the newcap calculation overflowed.
			if newcap <= 0 {
				newcap = newLen
			}
		}
	}
  ......
}

基本机制：

1. 如果新切片的长度大于旧切片的二倍容量，就直接令新切片的容量等于新切片的长度
2. 如果旧切片的容量小于256,进行二倍扩容
3. 如果就切片的容量大于等于256，按照newcap+=（newcap+3*threshold）/4公式进行扩容，扩容速度减缓，向1.25倍进行过渡。

在基本扩容规则的基础上，还会考虑元素类型与内存分配规则，对实际的扩张值做一些微调。从这一个基本规则中我们可以看出Go语言对slice性能和空间使用率的思考：

• 当切片较小时，采用较大的扩容倍速，可以避免频繁地扩容，从而减少内容分配次数和数据拷贝的代价。
• 当切片较大时，采用较小的扩容倍速，主要是为了避免空间浪费。

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

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

总结：

切片是go语言中常用的容器，由于其扩容特性，容易发生一些不容易被发现的错误，这就需要我们对切片的底层扩容机制有足够的了解，知道什么时候切片会进行扩容操作和如果高效地使用切片进行数据的存储和处理。

练习验证代码

package main

import "fmt"

type student struct {
	name    string
	age     int
	address string
}

func main() {
	//256以下的二倍扩容
	slice := make([]int, 255)
	fmt.Println(len(slice), cap(slice))
	newSlice := append(slice, 2)
	fmt.Println(len(newSlice), cap(newSlice))
}

/*func main() {
	//结构体指针类型切片cap为1024的1.5倍扩容
	array := make([]*student, 1024)
	fmt.Println(len(array), cap(array))
	slice := array
	slice = append(slice, &student{name: "wang", age: 12, address: "河南"})
	fmt.Println(len(slice), cap(slice))
}*/

/*func main() {
	//结构体类型切片cap为1024的1.6倍扩容
	array := make([]student, 1024)
	fmt.Println(len(array), cap(array))
	slice := array
	slice = append(slice, student{name: "wang", age: 12, address: "河南"})
	fmt.Println(len(slice), cap(slice))
}*/

//func main() {
//	//int类型的cap为1024的1.5倍扩容
//	array := make([]int, 1024)
//	fmt.Println(len(array), cap(array))
//	slice := array
//	slice = append(slice, 1)
//	fmt.Println(len(slice), cap(slice))
//}