golang 切片底层实现

淩亂°似流年 2022-09-12 04:57 219阅读 0赞

**本章不属于基础部分但是面试经常会问到建议学学，面试官经常问**

切片是 Go 中的一种基本的数据结构，使用这种结构可以用来管理数据集合。切片的设计想法是由动态数组概念而来，为了开发者可以更加方便的使一个数据结构可以自动增加和减少。但是切片本身并不是动态数据或者数组指针。切片常见的操作有 reslice、append、copy。与此同时，切片还具有可索引，可迭代的优秀特性。

### 切片的数据结构 ###

切片本身并不是动态数组或者数组指针。它内部实现的数据结构通过指针引用底层数组，设定相关属性将数据读写操作限定在指定的区域内。切片本身是一个只读对象，其工作机制类似数组指针的一种封装。

切片（slice）是对数组一个连续片段的引用，所以切片是一个引用类型（因此更类似于 C/C++ 中的数组类型，或者 Python 中的 list 类型）。这个片段可以是整个数组，或者是由起始和终止索引标识的一些项的子集。需要注意的是，终止索引标识的项不包括在切片内。切片提供了一个与指向数组的动态窗口。

给定项的切片索引可能比相关数组的相同元素的索引小。和数组不同的是，切片的长度可以在运行时修改，最小为 0 最大为相关数组的长度：切片是一个长度可变的数组。

Slice 的数据结构定义如下:

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

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JC95Yeh5bCYLg_size_20_color_FFFFFF_t_70_g_se_x_16]

切片的结构体由3部分构成，Pointer 是指向一个数组的指针，len 代表当前切片的长度，cap 是当前切片的容量。cap 总是大于等于 len 的。  
![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JC95Yeh5bCYLg_size_20_color_FFFFFF_t_70_g_se_x_16 1]

### 切片扩容 ###

当一个切片的容量满了，就需要扩容了。怎么扩，策略是什么？

func growslice(et *_type, old slice, cap int) slice {
        if raceenabled {
            callerpc := getcallerpc(unsafe.Pointer(&et))
            racereadrangepc(old.array, uintptr(old.len*int(et.size)), callerpc, funcPC(growslice))
        }
        if msanenabled {
            msanread(old.array, uintptr(old.len*int(et.size)))
        }
    
        if et.size == 0 {
            // 如果新要扩容的容量比原来的容量还要小，这代表要缩容了，那么可以直接报panic了。
            if cap < old.cap {
                panic(errorString("growslice: cap out of range"))
            }
    
            // 如果当前切片的大小为0，还调用了扩容方法，那么就新生成一个新的容量的切片返回。
            return slice{unsafe.Pointer(&zerobase), old.len, cap}
        }
    
      // 这里就是扩容的策略
        newcap := old.cap
        doublecap := newcap + newcap
        if cap > doublecap {
            newcap = cap
        } else {
            if old.len < 1024 {
                newcap = doublecap
            } else {
                for newcap < cap {
                    newcap += newcap / 4
                }
            }
        }
    
        // 计算新的切片的容量，长度。
        var lenmem, newlenmem, capmem uintptr
        const ptrSize = unsafe.Sizeof((*byte)(nil))
        switch et.size {
        case 1:
            lenmem = uintptr(old.len)
            newlenmem = uintptr(cap)
            capmem = roundupsize(uintptr(newcap))
            newcap = int(capmem)
        case ptrSize:
            lenmem = uintptr(old.len) * ptrSize
            newlenmem = uintptr(cap) * ptrSize
            capmem = roundupsize(uintptr(newcap) * ptrSize)
            newcap = int(capmem / ptrSize)
        default:
            lenmem = uintptr(old.len) * et.size
            newlenmem = uintptr(cap) * et.size
            capmem = roundupsize(uintptr(newcap) * et.size)
            newcap = int(capmem / et.size)
        }
    
        // 判断非法的值，保证容量是在增加，并且容量不超过最大容量
        if cap < old.cap || uintptr(newcap) > maxSliceCap(et.size) {
            panic(errorString("growslice: cap out of range"))
        }
    
        var p unsafe.Pointer
        if et.kind&kindNoPointers != 0 {
            // 在老的切片后面继续扩充容量
            p = mallocgc(capmem, nil, false)
            // 将 lenmem 这个多个 bytes 从 old.array地址 拷贝到 p 的地址处
            memmove(p, old.array, lenmem)
            // 先将 P 地址加上新的容量得到新切片容量的地址，然后将新切片容量地址后面的 capmem-newlenmem 个 bytes 这块内存初始化。为之后继续 append() 操作腾出空间。
            memclrNoHeapPointers(add(p, newlenmem), capmem-newlenmem)
        } else {
            // 重新申请新的数组给新切片
            // 重新申请 capmen 这个大的内存地址，并且初始化为0值
            p = mallocgc(capmem, et, true)
            if !writeBarrier.enabled {
                // 如果还不能打开写锁，那么只能把 lenmem 大小的 bytes 字节从 old.array 拷贝到 p 的地址处
                memmove(p, old.array, lenmem)
            } else {
                // 循环拷贝老的切片的值
                for i := uintptr(0); i < lenmem; i += et.size {
                    typedmemmove(et, add(p, i), add(old.array, i))
                }
            }
        }
        // 返回最终新切片，容量更新为最新扩容之后的容量
        return slice{p, old.len, newcap}
    }

#### 扩容策略 ####

先看看扩容策略。

func main() {
        slice := []int{10, 20, 30, 40}
        newSlice := append(slice, 50)
        fmt.Printf("Before slice = %v, Pointer = %p, len = %d, cap = %d\n", slice, &slice, len(slice), cap(slice))
        fmt.Printf("Before newSlice = %v, Pointer = %p, len = %d, cap = %d\n", newSlice, &newSlice, len(newSlice), cap(newSlice))
        newSlice[1] += 10
        fmt.Printf("After slice = %v, Pointer = %p, len = %d, cap = %d\n", slice, &slice, len(slice), cap(slice))
        fmt.Printf("After newSlice = %v, Pointer = %p, len = %d, cap = %d\n", newSlice, &newSlice, len(newSlice), cap(newSlice))
    }

输出结果：

Before slice = [10 20 30 40], Pointer = 0xc4200b0140, len = 4, cap = 4
        Before newSlice = [10 20 30 40 50], Pointer = 0xc4200b0180, len = 5, cap = 8
        After slice = [10 20 30 40], Pointer = 0xc4200b0140, len = 4, cap = 4
        After newSlice = [10 30 30 40 50], Pointer = 0xc4200b0180, len = 5, cap = 8

用图表示出上述过程。

![请添加图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JC95Yeh5bCYLg_size_20_color_FFFFFF_t_70_g_se_x_16 2]

从图上我们可以很容易的看出，新的切片和之前的切片已经不同了，因为新的切片更改了一个值，并没有影响到原来的数组，新切片指向的数组是一个全新的数组。并且 cap 容量也发生了变化。这之间究竟发生了什么呢？

Go 中切片扩容的策略是这样的：

**如果切片的容量小于 1024 个元素，于是扩容的时候就翻倍增加容量。上面那个例子也验证了这一情况，总容量从原来的4个翻倍到现在的8个。**

**一旦元素个数超过 1024 个元素，那么增长因子就变成 1.25 ，即每次增加原来容量的四分之一。**

**注意：扩容扩大的容量都是针对原来的容量而言的，而不是针对原来数组的长度而言的。**

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JC95Yeh5bCYLg_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/3abd854ad3d44b9d9ad8e56f8faa7f60.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JC95Yeh5bCYLg_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/92c0b42d71e64ba99f7dc7a44d113ffd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JC95Yeh5bCYLg_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220828/5cd541749cfd4f45b86bdfda78bf8c7c.png