深圳集团网站开发网站开发公司电话,法制教育网站,怎么爬虫做网站,北京关键词优化平台目录
切片的底层数据结构
扩容机制
总结#xff1a;
练习验证代码 这是切片的底层探索下篇#xff0c;上篇地址请见#xff1a;GO语言-切片底层探索#xff08;上#xff09;
在上篇我们讲解了切片的两个重要实现或者说是两个特征
切片是引用类型#xff0c;会进行…目录
切片的底层数据结构
扩容机制
总结
练习验证代码 这是切片的底层探索下篇上篇地址请见GO语言-切片底层探索上
在上篇我们讲解了切片的两个重要实现或者说是两个特征
切片是引用类型会进行引用传递切片会随着元素数量的增加进行扩容改变其底层数组的指向
这篇文章我们将会顺着讲解切片的底层数据结构和扩容机制
切片的底层数据结构
我们可以在src/runtime/slice.go下看到切片slice的底层数据结构
type slice struct {array unsafe.Pointerlen intcap 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 : oldCapdoublecap : newcap newcapif newLen doublecap {newcap newLen} else {const threshold 256if 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}}}......
}
基本机制
如果新切片的长度大于旧切片的二倍容量就直接令新切片的容量等于新切片的长度如果旧切片的容量小于256,进行二倍扩容如果就切片的容量大于等于256按照newcapnewcap3*threshold/4公式进行扩容扩容速度减缓向1.25倍进行过渡。
在基本扩容规则的基础上还会考虑元素类型与内存分配规则对实际的扩张值做一些微调。从这一个基本规则中我们可以看出Go语言对slice性能和空间使用率的思考
当切片较小时采用较大的扩容倍速可以避免频繁地扩容从而减少内容分配次数和数据拷贝的代价。当切片较大时采用较小的扩容倍速主要是为了避免空间浪费。 因此使用append()向slice添加一个元素的实现步骤如下
假如slice容量够用则将新元素追加进去slice.len返回原slice原slice容量不够则将slice先扩容扩容后得到新slice将新元素追加进新sliceslice.len返回新的slice。
总结
切片是go语言中常用的容器由于其扩容特性容易发生一些不容易被发现的错误这就需要我们对切片的底层扩容机制有足够的了解知道什么时候切片会进行扩容操作和如果高效地使用切片进行数据的存储和处理。
练习验证代码
package mainimport fmttype student struct {name stringage intaddress 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 : arrayslice 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 : arrayslice 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))
//}
