Slice

参考

你真的了解go语言中的切片吗

基本介绍

go 语言中的切片对标于其他编程语言中通俗意义上的“数组”. 切片中的元素存放在一块内存地址连续的区域，使用索引可以快速检索到指定位置的元素；切片长度和容量是可变的，在使用过程中可以根据需要进行扩容.

Go slice 的底层实现原理?

切片是基于数组实现的，它的底层是数组，可以理解为对底层数组的抽象。

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

type slice struct {
	// 指向起点的地址
    array unsafe.Pointer
    // 切片长度
    len   int
    // 切片容量
    cap   int
}

Slice 占用 24 个字节

• Array: 指向底层数组的指针，占用 8 个字节

• Len: 切片的长度，占用 8 个字节

• Cap: 切片的容量，cap 总是大于等于 len 的，占用 8 个字节

Slice 有 4 种初始化方式

// 初始化方式1：直接声明
var slice1 []int

// 初始化方式2：使用字面量
slice2 := []int{1, 2, 3, 4}

// 初始化方式3：使用make创建slice
slice3 := make([]int, 3, 5)         

// 初始化方式4: 从切片或数组“截取”
slcie4 := arr[1:3]

通过一个简单程序，看下 slice 初始化调用的底层函数

package main

import "fmt"

func main() {
    slice := make([]int, 0)
    slice = append(slice, 1)
    fmt.Println(slice, len(slice), cap(slice))
}

通过 go tool compile -S test.go | grep CALL 得到汇编代码

0x0042 00066 (test.go:6)        CALL    runtime.makeslice(SB)
0x006d 00109 (test.go:7)        CALL    runtime.growslice(SB)
0x00a4 00164 (test.go:8)        CALL    runtime.convTslice(SB)
0x00c0 00192 (test.go:8)        CALL    runtime.convT64(SB)
0x00d8 00216 (test.go:8)        CALL    runtime.convT64(SB)
0x0166 00358 ($GOROOT/src/fmt/print.go:274)     CALL    fmt.Fprintln(SB)
0x0180 00384 (test.go:5)        CALL    runtime.morestack_noctxt(SB)
0x0079 00121 (<autogenerated>:1)        CALL    runtime.efaceeq(SB)
0x00a0 00160 (<autogenerated>:1)        CALL    runtime.morestack_noctxt(SB)

初始化 slice 调用的是 runtime. Makeslice，makeslice 函数的工作主要就是计算 slice 所需内存大小，然后调用 mallocgc 进行内存的分配

所需内存大小 = 切片中元素大小 * 切片的容量

func makeslice(et *_type, len, cap int) unsafe.Pointer {
    // 根据 cap 结合每个元素的大小，计算出消耗的总容量
    mem, overflow := math.MulUintptr(et.size, uintptr(cap))
    if overflow || mem > maxAlloc || len < 0 || len > cap {
        // 倘若容量超限，len 取负值或者 len 超过 cap，直接 panic
        mem, overflow := math.MulUintptr(et.size, uintptr(len))
        if overflow || mem > maxAlloc || len < 0 {
            panicmakeslicelen()
        }
        panicmakeslicecap()
    }
    // 走 mallocgc 进行内存分配以及切片初始化
    return mallocgc(mem, et, true)
}

Slice 切片的截取

 x := make([]int, 2, 10)
 _ = x[6:10]
 _ = x[6:]
 _ = x[2:]

//_ = x[6:] 这⼀⾏会发⽣panic, 截取符号 [i:j]，
//如果 j 省略，默认是原切⽚或者数组的⻓度，x 的⻓度是 2，⼩于起始下标 6 ，所以 panic

可以修改 slice 下标的方式，进行 slice 内容的截取，形如 s[a: b] 的格式，其中 a b 代表切片的索引 index，左闭右开，比如 s[a: b] 对应的范围是 [a,b)，代表的是取切片 slice index = a ~ index = b-1 范围的内容.

此外，这里我聊到的 a 和 b 是可以缺省的：

• 如果 a 缺省不填则默认取 0 ，则代表从切片起始位置开始截取. 比如 s[:b] 等价于 s[0:b]

•  如果 b 缺省不填，则默认取 len(s)，则代表末尾截取到切片长度 len 的终点，比如 s[a:] 等价于 s[a:len(s)]

• •a 和 b 均缺省也是可以的，则代表截取整个切片长度的范围，比如 s[:] 等价于 s[0:len(s)

对切片 slice 执行截取操作时，本质上是一次引用传递操作，因为不论如何截取，底层复用的都是同一块内存空间中的数据，只不过，截取动作会创建出一个新的 slice header 实例

Slice 元素追加

通过 append 操作，可以在 slice 末尾，额外新增一个元素. 需要注意，这里的末尾指的是针对 slice 的长度 len 而言. 这个过程中倘若发现 slice 的剩余容量已经不足了，则会对 slice 进行扩容.

Slice 扩容

版本 1.18 之前 扩容会发生在 slice append 的时候，当 slice 的 cap 不足以容纳新元素，就会进行扩容，扩容规则如下

• 如果原有 slice 长度小于 1024，那么每次就扩容为原来的 2 倍
• 如果原 slice 长度大于等于 1024，那么每次扩容就扩为原来的 1.25 倍

1.18 +

切片的扩容流程源码位于 runtime/slice.go 文件的 growslice 方法当中，其中核心步骤如下：

• 倘若扩容后预期的新容量小于原切片的容量，则 panic

• 倘若切片元素大小为 0（元素类型为 struct{}），则直接复用一个全局的 zerobase 实例，直接返回

• 倘若预期的新容量超过老容量的两倍，则直接采用预期的新容量

• 倘若老容量小于 256，则直接采用老容量的2倍作为新容量

• 倘若老容量已经大于等于 256，则在老容量的基础上扩容 1/4 的比例并且累加上 192 的数值，持续这样处理，直到得到的新容量已经大于等于预期的新容量为止

•  结合 mallocgc 流程中，对内存分配单元 mspan 的等级制度，推算得到实际需要申请的内存空间大小

• 调用 mallocgc，对新切片进行内存初始化

• 调用 memmove 方法，将老切片中的内容拷贝到新切片中

•  返回扩容后的新切片

func growslice(et *_type, old slice, cap int) slice {
    //... 
    if cap < old.cap {
        panic(errorString("growslice: cap out of range"))
    }


    if et.size == 0 {
        // 倘若元素大小为 0，则无需分配空间直接返回
        return slice{unsafe.Pointer(&zerobase), old.len, cap}
    }


    // 计算扩容后数组的容量
    newcap := old.cap
    // 取原容量两倍的容量数值
    doublecap := newcap + newcap
    // 倘若新的容量大于原容量的两倍，直接取新容量作为数组扩容后的容量
    if cap > doublecap {
        newcap = cap
    } else {
        const threshold = 256
        // 倘若原容量小于 256，则扩容后新容量为原容量的两倍
        if old.cap < threshold {
            newcap = doublecap
        } else {
            // 在原容量的基础上，对原容量 * 5/4 并且加上 192
            // 循环执行上述操作，直到扩容后的容量已经大于等于预期的新容量为止
            for 0 < newcap && newcap < cap {             
                newcap += (newcap + 3*threshold) / 4
            }
            // 倘若数值越界了，则取预期的新容量 cap 封顶
            if newcap <= 0 {
                newcap = cap
            }
        }
    }


    var overflow bool
    var lenmem, newlenmem, capmem uintptr
    // 基于容量，确定新数组容器所需要的内存空间大小 capmem
    switch {
    // 倘若数组元素的大小为 1，则新容量大小为 1 * newcap.
    // 同时会针对 span class 进行取整
    case et.size == 1:
        lenmem = uintptr(old.len)
        newlenmem = uintptr(cap)
        capmem = roundupsize(uintptr(newcap))
        overflow = uintptr(newcap) > maxAlloc
        newcap = int(capmem)
    // 倘若数组元素为指针类型，则根据指针占用空间结合元素个数计算空间大小
    // 并会针对 span class 进行取整
    case et.size == goarch.PtrSize:
        lenmem = uintptr(old.len) * goarch.PtrSize
        newlenmem = uintptr(cap) * goarch.PtrSize
        capmem = roundupsize(uintptr(newcap) * goarch.PtrSize)
        overflow = uintptr(newcap) > maxAlloc/goarch.PtrSize
        newcap = int(capmem / goarch.PtrSize)
    // 倘若元素大小为 2 的指数，则直接通过位运算进行空间大小的计算   
    case isPowerOfTwo(et.size):
        var shift uintptr
        if goarch.PtrSize == 8 {
            // Mask shift for better code generation.
            shift = uintptr(sys.Ctz64(uint64(et.size))) & 63
        } else {
            shift = uintptr(sys.Ctz32(uint32(et.size))) & 31
        }
        lenmem = uintptr(old.len) << shift
        newlenmem = uintptr(cap) << shift
        capmem = roundupsize(uintptr(newcap) << shift)
        overflow = uintptr(newcap) > (maxAlloc >> shift)
        newcap = int(capmem >> shift)
    // 兜底分支：根据元素大小乘以元素个数
    // 再针对 span class 进行取整     
    default:
        lenmem = uintptr(old.len) * et.size
        newlenmem = uintptr(cap) * et.size
        capmem, overflow = math.MulUintptr(et.size, uintptr(newcap))
        capmem = roundupsize(capmem)
        newcap = int(capmem / et.size)
    }




    // 进行实际的切片初始化操作
    var p unsafe.Pointer
    // 非指针类型
    if et.ptrdata == 0 {
        p = mallocgc(capmem, nil, false)
        // ...
    } else {
        // 指针类型
        p = mallocgc(capmem, et, true)
        // ...
    }
    // 将切片的内容拷贝到扩容后的位置 p 
    memmove(p, old.array, lenmem)
    return slice{p, old.len, newcap}
}

Slice 元素删除

从切片中删除元素的实现思路，本质上和切片内容截取的思路是一致的.

需要删除 slice 中间的某个元素，操作思路则是采用内容截取加上元素追加的复合操作，可以先截取待删除元素的左侧部分内容，然后在此基础上追加上待删除元素后侧部分的内容：

    s := []int{0,1,2,3,4}
    // 删除 index = 2 的元素
    s = append(s[:2],s[3:]...)
    // s: [0,1,3,4], len: 4, cap: 5
    t.Logf("s: %v, len: %d, cap: %d", s, len(s), cap(s))
}

Go 语言删除切片元素的方法：
1、指定删除位置，如【index := 1】;
2、查看删除位置之前的元素和之后的元素;
3、将删除点前后的元素连接起来即可。
Go 语言并没有对删除切片元素提供专用的语法或者接口，需要使用切片本身的特性来删除元素。
示例代码如下：

str := []string{"a","b","c"}
// step 1
index := 1
// step 2
fmt.Println(str[:index], str[index+1])
// step 3
str = append(str[:index], str[index+1]...)
// res
fmt.Println(str)

Slice 切片拷贝

slice 的拷贝可以分为简单拷贝和完整拷贝两种类型.

• 简单拷贝，只需要对切片的字面量进行赋值传递即可，这样相当于创建出了一个新的 slice header 实例，但是其中的指针 array、容量 cap 和长度 len 仍和老的 slice header 实例相同.

func Test_slice(t *testing.T) {
    s := []int{0, 1, 2, 3, 4}
    s1 := s
    t.Logf("address of s: %p, address of s1: %p", s, s1)
}

• slice 的完整复制，指的是会创建出一个和 slice 容量大小相等的独立的内存区域，并将原 slice 中的元素一一拷贝到新空间中.

func Test_slice(t *testing.T) {
    s := []int{0, 1, 2, 3, 4}
    s1 := make([]int, len(s))
    copy(s1, s)
    t.Logf("s: %v, s1: %v", s, s1)
    t.Logf("address of s: %p, address of s1: %p", s, s1)
}

Go array 和 slice 的区别？

1）数组长度不同

数组初始化必须指定长度，并且长度就是固定的

切片的长度是不固定的，可以追加元素，在追加时可能使切片的容量增大

2）函数传参不同

数组是值类型，将一个数组赋值给另一个数组时，传递的是一份深拷贝，函数传参操作都会复制整个数组数据，会占用额外的内存，函数内对数组元素值的修改，不会修改原数组内容。

切片是引用类型，将一个切片赋值给另一个切片时，传递的是一份浅拷贝，函数传参操作不会拷贝整个切片，只会复制 len 和 cap，底层共用同一个数组，不会占用额外的内存，函数内对数组元素值的修改，会修改原数组内容。

3）计算数组长度方式不同

数组需要遍历计算数组长度，时间复杂度为 O (n)

切片底层包含 len 字段，可以通过 len ()计算切片长度，时间复杂度为 O (1)

Go slice 深拷贝和浅拷贝

深拷贝：拷贝的是数据本身，创造一个新对象，新创建的对象与原对象不共享内存，新创建的对象在内存中开辟一个新的内存地址，新对象值修改时不会影响原对象值

实现深拷贝的方式：

1. Copy (slice 2, slice 1)
2. 遍历 append 赋值

func main() {
    slice1 := []int{1, 2, 3, 4, 5}
    slice2 := make([]int, 5, 5)
    fmt.Printf("slice1: %v, %p\n", slice1, slice1)
    copy(slice2, slice1)
    fmt.Printf("slice2: %v, %p\n", slice2, slice2)
    slice3 := make([]int, 0, 5)
    for _, v := range slice1 {
        slice3 = append(slice3, v)
    }
    fmt.Printf("slice3: %v, %p\n", slice3, slice3)
}

slice1: [1 2 3 4 5], 0xc0000b0030
slice2: [1 2 3 4 5], 0xc0000b0060
slice3: [1 2 3 4 5], 0xc0000b0090

浅拷贝：拷贝的是数据地址，只复制指向的对象的指针，此时新对象和老对象指向的内存地址是一样的，新对象值修改时老对象也会变化

实现浅拷贝的方式：

引用类型的变量，默认赋值操作就是浅拷贝

func main() {
    slice1 := []int{1, 2, 3, 4, 5}
    fmt.Printf("slice1: %v, %p\n", slice1, slice1)
    slice2 := slice1
    fmt.Printf("slice2: %v, %p\n", slice2, slice2)
}

slice1: [1 2 3 4 5], 0xc00001a120
slice2: [1 2 3 4 5], 0xc00001a120

Go slice 为什么不是线程安全的？

先看下线程安全的定义：

多个线程访问同一个对象时，调用这个对象的行为都可以获得正确的结果，那么这个对象就是线程安全的。

若有多个线程同时执行写操作，一般都需要考虑线程同步，否则的话就可能影响线程安全。

再看 Go 语言实现线程安全常用的几种方式：

1. 互斥锁
2. 读写锁
3. 原子操作
4. Sync. Once
5. Sync. Atomic
6. Channel

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
}

nil 切片和空切片指向的地址一样？

func main() {
    var s1 []int
    s2 := make([]int, 0)
    s3 := make([]int, 0)
    data1 := (*reflect.SliceHeader)(unsafe.Pointer(&s1)).Data
    data2 := (*reflect.SliceHeader)(unsafe.Pointer(&s2)).Data
    data3 := (*reflect.SliceHeader)(unsafe.Pointer(&s3)).Data

    fmt.Printf("s1 data:%+v\n", data1)
    fmt.Printf("s2 data:%+v\n", data2)
    fmt.Printf("s3 data:%+v\n", data3)

    fmt.Printf("s1:s2=>%t\n", data1 == data2)
    fmt.Printf("s2:s3=>%t\n", data2 == data3)
}

//输出
s1 data:0
s2 data:824634859200
s3 data:824634859200
s1:s2=>false
s2:s3=>true

Nil 切片和空切片指向的地址不一样。

Nil 切片引用数组指针地址为 0（无指向任何实际地址）

空切片的引用数组指针地址是有的，且固定为一个值。

//切片的数据结构
type SliceHeader struct {
    Data uintptr //引用数组指针地址
    Len  int
    Cap  int
}

Nil 切片和空切片最大的区别在于指向的数组引用地址是不一样的

拷贝大切片一定比小切片代价大吗？

并不是，所有切片的大小相同；三个字段（一个 uintptr，两个 int）。切片中的第一个字段是指向切片底层数组的指针，这是切片的存储空间，第二个字段是切片的长度，第三个字段是容量。将一个 slice 变量分配给另一个变量只会复制三个机器字。所以拷贝大切片跟小切片的代价应该是一样的。

SliceHeader 是切片在 go 的底层结构。

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

大切片跟小切片的区别无非就是 Len 和 Cap 的值比小切片的这两个值大一些，如果发生拷贝，本质上就是拷贝上面的三个字段。

json 库对 nil slice 和空 slice 的处理是一致的吗？

Json 库对 nil slice 和空 slice 的处理是不一致的，

因为 nil slice 只是声明了 slice，却没有给实例化的对象。

	var f1 []string
    f2 := make([]string, 0)
    json1, _ := json.Marshal(Person{f1})
    json2, _ := json.Marshal(Person{f2})
    fmt.Printf("%s\n", string(json1))
    fmt.Printf("%s\n", string(json2))

//输出
{"Friends":null}
{"Friends":[]}

Json 库对 nil slice 编码为 null, json 库对空 slice 编码为[]。

扩容前后的 Slice 是否相同?

情况一：原数组还有容量可以扩容（实际容量没有填充完），这种情况下，扩容以后的数组还是指向原来的数组，对一个切片的操作可能影响多个指针指向相同地址的 slice。

情况二：原来数组的容量已经达到了最大值，再想扩容，go 默认会先开一片内存区域，把原来的值拷贝过来，然后再执行 append ()操作。这种情况丝毫不影响原数组。要复制一个 slice，最好使用 copy 函数。

输出：

函数内s=[1,2]
主函数内s=[1]

使用值为 nil 的 slice、map 会发生啥

允许对值为 nil 的 slice 添加元素，但对值为 nil 的 map 添加元素，则会造成运行时 panic。

// map 错误示例  
func main () {  
    var m map[string]int  
    m["one"] = 1  // error: panic: assignment to entry in nil map  
    // m := make (map[string]int)// map 的正确声明，分配了实际的内存  
}      
  
// slice 正确示例  
func main () {  
 var s []int  
 s = append (s, 1)  
}

如果先使用 make(),那么可以使用 m["one"]=1,因为分配了内存。

slice 分配在堆上还是栈上

有可能分配到栈上，也有可能分配到栈上。当开辟切片空间较大时，会逃逸到堆上。

通过命令 go build -gcflags "-m -l" xxx.go 观察 golang 是如何进行逃逸分析的

// map 错误示例
func main() {
    var m map[string]int
    m["one"] = 1  // error: panic: assignment to entry in nil map
    // m := make(map[string]int)// map 的正确声明，分配了实际的内存
}    

// slice 正确示例
func main() {
 var s []int
 s = append(s, 1)
}

Go 中如果 new 一个切片会怎么样

new ([]int) 之后的 list 是⼀个未设置⻓度的 * []int 类型的指针不能对未设置⻓度的指针执⾏ append 操作。

package main

import "fmt"

func main() {
	list := new([]int)
	// 编译错误
	// new([]int) 之后的 list 是⼀个未设置⻓度的 *[]int 类型的指针
	// 不能对未设置⻓度的指针执⾏ append 操作。
	*list = append(*list, 1)
	fmt.Println(*list)
	s1 := []int{1, 2, 3}
	s2 := []int{4, 5}
	// 编译错误，s2需要展开
	s1 = append(s1, s2...)
	fmt.Println(s1)
}//正确写法

整型切片如何初始化？

//数组初始化
arr1 := [3]int{1, 2, 3}
arr2 := [...]int{1, 2, 3}
arr3 := [3]int{0:3,1:4}

数组怎么转集合 ?

可以使用数组的索引作为 map 的 key，数组的值作为 map 的值。

//数组初始化
arr1 := [3]int{1, 2, 3}
arr2 := [...]int{1, 2, 3}
arr3 := [3]int{0:3,1:4}

数组是如何实现根据下标随机访问数组元素的吗？

例如： a := [10]int{0}

• 计算机给数组 a，分配了一组连续的内存空间。
• 比如内存块的首地址为 base_address=1000。
• 当计算给每个内存单元分配一个地址，计算机通过地址来访问数据。当计算机需要访问数组的某个元素的时候，会通过一个寻址公式来计算存储的内存地址。

一个函数传参一个 slice，先 append 再赋值和另一个函数先赋值再 append，哪个会发生变化？

package main

import "fmt"

func BeforeAppend(s []int) []int {
	s = append(s, 1)
	s = []int{1, 2, 3}
	return s
}

func AfterAppend(s []int) []int {
	s = []int{1, 2, 3}
	s = append(s, 1)
	return s
}

func main() {
	s := make([]int, 0)
	fmt.Println(BeforeAppend(s))
	fmt.Println(AfterAppend(s))
}