共计 9054 个字符,预计需要花费 23 分钟才能阅读完成。
看完这篇文章,上面这些高频面试题你都会答了吧
- Go slice 的底层实现原理
- Go array 和 slice 的区别
- Go slice 深拷贝和浅拷贝
- Go slice 扩容机制是怎么的?
- 为什么 Go slice 是非线程平安的?
实现原理
slice 是无固定长度的数组,底层构造是一个构造体,蕴含如下 3 个属性
一个 slice
在 golang 中占用 24 个 bytes
type slice struct {
array unsafe.Pointer
len int
cap int
}
array : 蕴含了一个指向一个数组的指针,数据实际上存储在这个指针指向的数组上,占用 8 bytes
len: 以后 slice 应用到的长度,占用 8 bytes
cap : 以后 slice 的容量,同时也是底层数组 array 的长度,8 bytes
slice 并不是真正意义上的动静数组,而是一个援用类型。slice 总是指向一个底层 array,slice 的申明也能够像 array 一样,只是长度可变。golang 中通过语法糖,使得咱们能够像申明 array 一样,主动创立 slice 构造体
依据 索引地位取切片slice 元素值时,默认取值范畴是(0~len(slice)-1),个别输入 slice 时,通常是指 slice[0:len(slice)-1],依据下标就能够输入所指向底层数组中的值
次要个性
援用类型
golang 有三个罕用的高级类型 slice、map、channel, 它们都是 援用类型,当援用类型作为函数参数时,可能会批改原内容数据。
func sliceModify(s []int) {s[0] = 100
}
func sliceAppend(s []int) []int {s = append(s, 100)
return s
}
func sliceAppendPtr(s *[]int) {*s = append(*s, 100)
return
}
// 留神:Go 语言中所有的传参都是值传递(传值),都是一个正本,一个拷贝。// 拷贝的内容是非援用类型(int、string、struct 等这些),在函数中就无奈批改原内容数据;// 拷贝的内容是援用类型(interface、指针、map、slice、chan 等这些),这样就能够批改原内容数据。func TestSliceFn(t *testing.T) {
// 参数为援用类型 slice:外层 slice 的 len/cap 不会扭转,指向的底层数组会扭转
s := []int{1, 1, 1}
newS := sliceAppend(s)
// 函数内产生了扩容
t.Log(s, len(s), cap(s))
// [1 1 1] 3 3
t.Log(newS, len(newS), cap(newS))
// [1 1 1 100] 4 6
s2 := make([]int, 0, 5)
newS = sliceAppend(s2)
// 函数内未产生扩容
t.Log(s2, s2[0:5], len(s2), cap(s2))
// [] [100 0 0 0 0] 0 5
t.Log(newS, newS[0:5], len(newS), cap(newS))
// [100] [100 0 0 0 0] 1 5
// 参数为援用类型 slice 的指针:外层 slice 的 len/cap 会扭转,指向的底层数组会扭转
sliceAppendPtr(&s)
t.Log(s, len(s), cap(s))
// [1 1 1 100] 4 6
sliceModify(s)
t.Log(s, len(s), cap(s))
// [100 1 1 100] 4 6
}
公众号后盾 caspar 回复【代码】获取本文所有示例代码
切片状态
切片有 3 种非凡的状态,分为「零切片」、「空切片」和「nil 切片」
func TestSliceEmptyOrNil(t *testing.T) {var slice1 []int
// slice1 is nil slice
slice2 := make([]int, 0)
// slcie2 is empty slice
var slice3 = make([]int, 2)
// slice3 is zero slice
if slice1 == nil {t.Log("slice1 is nil.")
// 会输入这行
}
if slice2 == nil {t.Log("slice2 is nil.")
// 不会输入这行
}
t.Log(slice3) // [0 0]
}
非线程平安
slice 不反对并发读写,所以并不是线程平安的,应用多个 goroutine 对类型为 slice 的变量进行操作,每次输入的值大概率都不会一样,与预期值不统一; slice 在并发执行中不会报错,然而数据会失落
/**
* 切片非并发平安
* 屡次执行,每次失去的后果都不一样
* 能够思考应用 channel 自身的个性 (阻塞) 来实现平安的并发读写
*/
func TestSliceConcurrencySafe(t *testing.T) {a := make([]int, 0)
var wg sync.WaitGroup
for i := 0; i < 10000; i++ {wg.Add(1)
go func(i int) {a = append(a, i)
wg.Done()}(i)
}
wg.Wait()
t.Log(len(a))
// not equal 10000
}
如果想实现 slice 线程平安,有两种形式:
形式一:通过加锁实现 slice 线程平安,适宜对性能要求不高的场景。
func TestSliceConcurrencySafeByMutex(t *testing.T) {
var lock sync.Mutex // 互斥锁
a := make([]int, 0)
var wg sync.WaitGroup
for i := 0; i < 10000; i++ {wg.Add(1)
go func(i int) {defer wg.Done()
lock.Lock()
defer lock.Unlock()
a = append(a, i)
}(i)
}
wg.Wait()
t.Log(len(a))
// equal 10000
}
形式二:通过 channel 实现 slice 线程平安,适宜对性能要求高的场景。
func TestSliceConcurrencySafeByChanel(t *testing.T) {buffer := make(chan int)
a := make([]int, 0)
// 消费者
go func() {
for v := range buffer {a = append(a, v)
}
}()
// 生产者
var wg sync.WaitGroup
for i := 0; i < 10000; i++ {wg.Add(1)
go func(i int) {defer wg.Done()
buffer <- i
}(i)
}
wg.Wait()
t.Log(len(a))
// equal 10000
}
共享存储空间
多个切片如果共享同一个底层数组,这种状况下,对其中一个切片或者底层数组的更改,会影响到其余切片
/**
* 切片共享存储空间
*/
func TestSliceShareMemory(t *testing.T) {slice1 := []string{"1", "2", "3", "4", "5", "6", "7", "8", "9", "10", "11", "12"}
Q2 := slice1[3:6]
t.Log(Q2, len(Q2), cap(Q2))
// [4 5 6] 3 9
Q3 := slice1[5:8]
t.Log(Q3, len(Q3), cap(Q3))
// [6 7 8] 3 7
Q3[0] = "Unkown"
t.Log(Q2, Q3)
// [4 5 Unkown] [Unkown 7 8]
a := []int{1, 2, 3, 4, 5}
shadow := a[1:3]
t.Log(shadow, a)
// [2 3] [1 2 3 4 5]
shadow = append(shadow, 100)
// 会批改指向数组的所有切片
t.Log(shadow, a)
// [2 3 100] [1 2 3 100 5]
}
罕用操作
创立
slice 的创立有 4 种形式,如下:
func TestSliceInit(t *testing.T) {
// 初始化形式 1:间接申明
var slice1 []int
t.Log(len(slice1), cap(slice1))
// 0, 0
slice1 = append(slice1, 1)
t.Log(len(slice1), cap(slice1))
// 1, 1, 24
// 初始化形式 2:应用字面量
slice2 := []int{1, 2, 3, 4}
t.Log(len(slice2), cap(slice2))
// 4, 4, 24
// 初始化形式 3:应用 make 创立 slice
slice3 := make([]int, 3, 5)
// make([]T, len, cap) cap 不传则和 len 一样
t.Log(len(slice3), cap(slice3))
// 3, 5
t.Log(slice3[0], slice3[1], slice3[2])
// 0, 0, 0
// t.Log(slice3[3], slice3[4])
// panic: runtime error: index out of range [3] with length 3
slice3 = append(slice3, 1)
t.Log(len(slice3), cap(slice3))
// 4, 5, 24
// 初始化形式 4: 从切片或数组“截取”arr := [100]int{}
for i := range arr {arr[i] = i
}
slcie4 := arr[1:3]
slice5 := make([]int, len(slcie4))
copy(slice5, slcie4)
t.Log(len(slcie4), cap(slcie4), unsafe.Sizeof(slcie4))
// 2,99,24
t.Log(len(slice5), cap(slice5), unsafe.Sizeof(slice5))
// 2,2,24
}
减少
func TestSliceGrowing(t *testing.T) {slice1 := []int{}
for i := 0; i < 10; i++ {slice1 = append(slice1, i)
t.Log(len(slice1), cap(slice1))
}
// 1 1
// 2 2
// 3 4
// 4 4
// 5 8
// 6 8
// 7 8
// 8 8
// 9 16
// 10 16
}
删除
func TestSliceDelete(t *testing.T) {slice1 := []int{1, 2, 3, 4, 5}
var x int
// 删除最初一个元素
x, slice1 = slice1[len(slice1)-1], slice1[:len(slice1)-1]
t.Log(x, slice1, len(slice1), cap(slice1))
// 5 [1 2 3 4] 4 5
// 删除第 2 个元素
slice1 = append(slice1[:2], slice1[3:]...)
t.Log(slice1, len(slice1), cap(slice1))
// [1 2 4] 3 5
}
查找
v := s[i] // 下标拜访
批改
s[i] = 5 // 下标批改
截取
/**
* 切片截取
*/
func TestSliceSubstr(t *testing.T) {slice1 := []int{1, 2, 3, 4, 5}
slice2 := slice1[:]
// 截取 slice[left:right:max]
// left:省略默认 0
// right:省略默认 len(slice1)
// max: 省略默认 len(slice1)
// len = right-left+1
// cap = max-left
t.Log(slice2, len(slice2), cap(slice2))
// 1 2 3 4 5] 5 5
slice3 := slice1[1:]
t.Log(slice3, len(slice3), cap(slice3))
// [2 3 4 5] 4 4
slice4 := slice1[:2]
t.Log(slice4, len(slice4), cap(slice4))
// [1 2] 2 5
slice5 := slice1[1:2]
t.Log(slice5, len(slice5), cap(slice5))
// [2] 1 4
slice6 := slice1[:2:5]
t.Log(slice6, len(slice6), cap(slice6))
// [1 2] 2 5
slice7 := slice1[1:2:2]
t.Log(slice7, len(slice7), cap(slice7))
// [2] 1 1
}
遍历
切片有 3 种遍历形式
/**
* 切片遍历
*/
func TestSliceTravel(t *testing.T) {slice1 := []int{1, 2, 3, 4}
for i := 0; i < len(slice1); i++ {t.Log(slice1[i])
}
for idx, e := range slice1 {t.Log(idx, e)
}
for _, e := range slice1 {t.Log(e)
}
}
反转
func TestSliceReverse(t *testing.T) {a := []int{1, 2, 3, 4, 5}
for left, right := 0, len(a)-1; left < right; left, right = left+1, right-1 {a[left], a[right] = a[right], a[left]
}
t.Log(a, len(a), cap(a))
// [5 4 3 2 1] 5 5
}
拷贝
开发中会常常的把一个变量复制给另一个变量,那么这个过程,可能是深浅拷贝,那么明天帮大家辨别一下这两个拷贝的区别和具体的区别
深拷贝
拷贝的是数据自身,发明一个样的新对象,新创建的对象与原对象不共享内存,新创建的对象在内存中开拓一个新的内存地址,新对象值批改时不会影响原对象值。既然内存地址不同,开释内存地址时,可别离开释
值类型的数据,默认赋值操作都是深拷贝,Array、Int、String、Struct、Float,Bool。援用类型的数据如果想实现深拷贝,须要通过辅助函数实现
比方 golang 深拷贝 copy 办法会把源切片值 (即 from Slice) 中的元素复制到指标切片 (即 to Slice) 中,并返回被复制的元素个数,copy 的两个类型必须统一。copy 办法最终的 复制后果取决于较短的那个切片,当较短的切片复制实现,整个复制过程就全副实现了
/**
* 深拷贝
*/
func TestSliceDeepCopy(t *testing.T) {slice1 := []int{1, 2, 3, 4, 5}
slice2 := make([]int, 5, 5)
// 深拷贝
copy(slice2, slice1)
t.Log(slice1, len(slice1), cap(slice1))
// [1 2 3 4 5] 5 5
t.Log(slice2, len(slice2), cap(slice2))
// [1 2 3 4 5] 5 5
slice1[1] = 100
t.Log(slice1, len(slice1), cap(slice1))
// [1 100 3 4 5] 5 5
t.Log(slice2, len(slice2), cap(slice2))
// [1 2 3 4 5] 5 5
}
浅拷贝
拷贝的是数据地址,只复制指向的对象的指针,此时新对象和老对象指向的内存地址是一样的,新对象值批改时老对象也会变动。开释内存地址时,同时开释内存地址。
援用类型的数据,默认全部都是浅拷贝,Slice、Map 等
目标切片和源切片指向同一个底层数组,任何一个数组元素扭转,都会同时影响两个数组。
/**
* 浅拷贝
*/
func TestSliceShadowCopy(t *testing.T) {slice1 := []int{1, 2, 3, 4, 5}
// 浅拷贝(留神 := 对于援用类型是浅拷贝,对于值类型是深拷贝)slice2 := slice1
t.Logf("%p", slice1) // 0xc00001c120
t.Logf("%p", slice2) // 0xc00001c120
// 同时扭转两个数组,这时就是浅拷贝,未扩容时,批改 slice1 的元素之后,slice2 的元素也会跟着批改
slice1[0] = 10
t.Log(slice1, len(slice1), cap(slice1))
// [10 2 3 4 5] 5 5
t.Log(slice2, len(slice2), cap(slice2))
// [10 2 3 4 5] 5 5
// 留神下:扩容后,slice1 和 slice2 不再指向同一个数组,批改 slice1 的元素之后,slice2 的元素不会被批改了
slice1 = append(slice1, 5, 6, 7, 8)
slice1[0] = 11
// 这里能够发现,slice1[0] 被批改为了 11, slice1[0] 还是 10
t.Log(slice1, len(slice1), cap(slice1))
// [11 2 3 4 5 5 6 7 8] 9 10
t.Log(slice2, len(slice2), cap(slice2))
// [10 2 3 4 5] 5 5
}
在复制 slice 的时候,slice 中数组的指针也被复制了,在触发扩容逻辑之前,两个 slice 指向的是雷同的数组,触发扩容逻辑之后指向的就是不同的数组了
扩容
扩容会产生在 slice append 的时候,当 slice 的 cap 不足以包容新元素,就会进行扩容
源码:https://github.com/golang/go/…
func growslice(et *_type, old slice, cap int) slice {
// 省略一些判断...
newcap := old.cap
doublecap := newcap + newcap
if cap > doublecap {newcap = cap} else {
if old.len < 1024 {newcap = doublecap} else {
// Check 0 < newcap to detect overflow
// and prevent an infinite loop.
for 0 < newcap && newcap < cap {newcap += newcap / 4}
// Set newcap to the requested cap when
// the newcap calculation overflowed.
if newcap <= 0 {newcap = cap}
}
}
// 省略一些后续...
}
- 如果新申请容量比两倍原有容量大,那么扩容后容量大小 等于 新申请容量
- 如果原有 slice 长度小于 1024,那么每次就扩容为原来的 2 倍
- 如果原 slice 大于等于 1024,那么每次扩容就扩为原来的 1.25 倍
内存泄露
因为 slice 的底层是数组,很可能数组很大,但 slice 所取的元素数量却很小,这就导致数组占用的绝大多数空间是被节约的
Case1:
比方上面的代码,如果传入的 slice b
是很大的,而后援用很小局部给全局量 a
,那么b
未被援用的局部(下标 1 之后的数据)就不会被开释,造成了所谓的内存透露。
var a []int
func test(b []int) {a = b[:1] // 和 b 共用一个底层数组
return
}
那么只有全局量 a
在,b
就不会被回收。
如何防止?
在这样的场景下留神:如果咱们只用到一个 slice 的一小部分,那么底层的整个数组也将持续保留在内存当中。当这个底层数组很大,或者这样的场景很多时,可能会造成内存急剧减少,造成解体。
所以在这样的场景下,咱们能够将须要的分片复制到一个新的 slice 中去,缩小内存的占用
var a []int
func test(b []int) {a = make([]int, 1)
copy(a, b[:0])
return
}
Case2:
比方上面的代码,返回的 slice 是很小一部分,这样该函数退出后,原来那个体积较大的底层数组也无奈被回收
func test2() []int{s = make([]int, 0, 10000)
for i := 0; i < 10000; i++ {s = append(s, p)
}
s2 := s[100:102]
return s2
}
如何防止?
将须要的分片复制到一个新的 slice 中去,缩小内存的占用
func test2() []int{s = make([]int, 0, 10000)
for i := 0; i < 10000; i++ {
// 一些计算...
s = append(s, p)
}
s2 := make([]int, 2)
copy(s2, s[100:102])
return s2
}
切片与数组比照
数组是一个固定长度的,初始化时候必须要指定长度,不指定长度的话就是切片了
数组是值类型,将一个数组赋值给另一个数组时,传递的是一份深拷贝,赋值和函数传参操作都会复制整个数组数据,会占用额定的内存;切片是援用类型,将一个切片赋值给另一个切片时,传递的是一份浅拷贝,赋值和函数传参操作只会复制 len 和 cap,但底层共用同一个数组,不会占用额定的内存。
// a 是一个数组,留神数组是一个固定长度的,初始化时候必须要指定长度,不指定长度的话就是切片了
a := [3]int{1, 2, 3}
// b 是数组,是 a 的一份深拷贝
b := a
// c 是切片,是援用类型,底层数组是 a
c := a[:]
for i := 0; i < len(a); i++ {a[i] = a[i] + 1
}
// 扭转 a 的值后,b 是 a 的拷贝,b 不变,c 是援用,c 的值扭转
fmt.Println(a)
//[2,3,4]
fmt.Println(b)
//[1 2 3]
fmt.Println(c)
//[2,3,4]
// a 是一个切片,不指定长度的话就是切片了
a := []int{1, 2, 3}
// b 是切片,是 a 的一份拷贝
b := a
// c 是切片,是援用类型
c := a[:]
for i := 0; i < len(a); i++ {a[i] = a[i] + 1
}
// 扭转 a 的值后,b 是 a 的浅拷贝,b 的值改派,c 是援用,c 的值扭转
fmt.Println(a)
//[2,3,4]
fmt.Println(b)
//[2,3,4]
fmt.Println(c)
//[2,3,4]
总结
- 创立切片时可依据理论须要预调配容量,尽量避免追加过程中进行扩容操作,有利于晋升性能
- 应用 append() 向切片追加元素时有可能触发扩容,扩容后将会生成新的切片
- 应用 len()、cap()计算切片长度、容量时,工夫复杂度均为 O(1),不须要遍历切片
- 切片是非线程平安的,如果要实现线程平安,能够加锁或者应用 Channel
- 大数组作为函数参数时,会复制整个数组数据,耗费过多内存,倡议应用切片或者指针
- 切片作为函数参数时,能够扭转切片指向的数组,不能扭转切片自身 len 和 cap;想要扭转切片自身,能够将扭转后的切片返回 或者 将 切片指针 作为函数参数。
- 如果只用到大 slice 的一小部分,倡议将须要的分片复制到一个新的 slice 中去,缩小内存的占用
本文由博客一文多发平台 OpenWrite 公布!