什么是数组？
数组大家应该都非常熟悉我们来简单的回顾一下：
1.数组是一个具有连续的内存空间和相同类型的数据的数据结构
2.我们随机访问任意一个下标的数据的时间复杂度都是 O(1)
3但是正是由于这种特性，导致它插入和删除元素的效率比较低，是 O(n)
Go 中的数组
func main() {
// 初始化数组
var arr = [3] int {
1, 2, 3
}
// 查找元素
fmt.Printf("arr[1]: %d\n", arr[1])
// 删除元素
remove( & arr, 2)
// remove(&arr, 3) // will panic
fmt.Println(arr)
}
// 删除数组 arr 的某个元素
// index 为需要删除的索引
// 从需要删除的元素开始，依次将后面的元素往前移动一位即可
// 然后将最后一位修改为该类型的默认值
func remove(arr * [3] int, index int) {
if index >= len(arr) {
log.Panicf("%d remove out range arr", index)
}
for i: = index;
i < len(arr) - 1;
i++{
arr[i] = arr[i + 1]
}
arr[len(arr) - 1] = 0
}
Q: 为什么我们在 remove 函数当中的参数使用的是指针
这是因为在 go 中参数的传递都是值传递，如果不用指针的话，那么就会复制一份数据到函数中，这样就无法做到删除的作用
// 在函数 main 中
fmt.Printf("main: %p --> %+v\n", & arr, arr)
p(arr)
p2( & arr)
func p(arr[3] int) {
fmt.Printf("p: %p --> %+v\n", & arr, arr)
}
func p2(arr * [3] int) {
fmt.Printf("p2: %p --> %+v\n", arr, arr)
}
输出:
main: 0xc0000c2000-- > [1 2 0]
p: 0xc0000c2080-- > [1 2 0]
p2: 0xc0000c2000-- > & [1 2 0]
通过上面的例子我们就可以发现，在函数 p 中我们直接传递的数组，最后打印的变量地址是和 main 中不同的，就印证了我们之前的说法
在实际使用过程中，我们其实是很少使用到固定长度的数组的，而是使用可以自动扩容的 slice，接下来我们就深入的看一下 slice 当中的一些细节
深入理解 Slice
使用
基础使用
// 初始化
s1: = make([] int, 2)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [0 0], len: 2, cap: 2
// 赋值
s1[0] = 1
s1[1] = 2
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 2], len: 2, cap: 2
// 扩容
s1 = append(s1, 3)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 2 3], len: 3, cap: 4
// 删除元素
s1 = append(s1[: 1], s1[2: ]...)
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [1 3], len: 2, cap: 4
1.可以发现，通过 append 之后 s1 的容量和长度都发生了变化，说明完成了自动扩容
2.删除元素之后我们的长度发生了变化，但是容量还是原本不变
常见坑
// 复制一个 slice
s2: = s1[: 2]
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", & s2, s2, len(s2), cap(s2))
// s2(0xc00000c120): [1 3], len: 2, cap: 4
s1[0] = 10 // 这里可以发现，s1[0] s2[0] 都被修改为了 10
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00000c080): [10 3], len: 2, cap: 4
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", & s2, s2, len(s2), cap(s2))
// s2(0xc00000c120): [10 3], len: 2, cap: 4
s1 = append(s1, 5, 6, 7, 8)
s1[0] = 11 // 这里可以发现，s1[0] 被修改为了 11, s2[0] 还是10
fmt.Printf("s1(%p): %v, len: %d, cap: %d\n", & s1, s1, len(s1), cap(s1))
// s1(0xc00011c020): [11 3 5 6 7 8], len: 6, cap: 8
fmt.Printf("s2(%p): %v, len: %d, cap: %d\n", & s2, s2, len(s2), cap(s2))
// s2(0xc00011c0c0): [10 3], len: 2, cap: 4
这是一个常见的例子，我们从 s1 复制了一个 s2
修改 s1 的第一个元素之后，s2 的一个元素也被修改了
但是我们触发了 s1 的自动扩容之后，s2 的第一个元素就不会随着 s1 的修改而变化了
这也是当函数的参数是 slice 时我们不允许直接修改，如果需要修改需要返回这个 slice 的原因，因为函数的参数也是值的复制
func sliceChange(s[] int) {
// 不允许直接这么操作
s[0] = 1
}
结构
大家如果使用过一段时间 golang 应该知道 slice 的底层结构其实是一个 struct
https://github.com/golang/go/blob/go1.15/src/runtime/slice.go
type slice struct {
array unsafe.Pointer
len int
cap int
}
如图所示我们可以发现，slice 的底层结构是一个结构体：
1.它包含了一个指向一个数组的指针，数据实际上存储在这个指针指向的数组上
2.len 表示当前 slice 使用到的长度
3.cap 表示当前 slice 的容量，同时也是底层数组 array 的长度
这也就回答了我们上面的发现的现象，在复制 slice 的时候，slice 中数组的指针也被复制了，在出发扩容逻辑之前，两个 slice 指向的是相同的数组，出发扩容逻辑之后指向的就是不同的数组了
同时因为结构体中 array 是一个指针所以在 slice 作为参数传递的时候，这个指针也会被复制一份，所以也会有相同的问题
创建
// 创建一个 slice
// et: 数据的类型
// len: slice 长度
// cap: slice 容量
// 返回一个指针
func makeslice(et * _type, len, cap int) unsafe.Pointer {
// 通过 cap 计算当前类型的 slice 需要的内存容量以及是否超出最大容量
mem, overflow: = math.MulUintptr(et.size, uintptr(cap))
// 异常情况判断
if overflow || mem > maxAlloc || len < 0 || len > cap {
// 通过 len 计算当前类型的 slice 需要的内存容量以及是否超出最大容量
// 如果是 len 超过限制则抛出 len 的相关异常，否则抛出 cap 异常
mem, overflow: = math.MulUintptr(et.size, uintptr(len))
if overflow || mem > maxAlloc || len < 0 {
panicmakeslicelen()
}
panicmakeslicecap()
}
return mallocgc(mem, et, true)
}
还有一个 64 位的:
64 位对比默认的只是进行了一下数据格式转换，但是这个转换的对比还是很有意思的
如果是在 64 位的机器上，那么 int == int64 的
如果是在 32 位的机器上，那么 int == int32，如果 int64(int(len64)) != len64，那么就说明这个长度超出了当前机器的内存位数，直接抛出异常错误就好了
func makeslice64(et * _type, len64, cap64 int64) unsafe.Pointer {
len: = int(len64)
if int64(len) != len64 {
panicmakeslicelen()
}
cap: = int(cap64)
if int64(cap) != cap64 {
panicmakeslicecap()
}
return makeslice(et, len, cap)
}
扩容
// 当 append 需要扩容的时候会调用这个函数
// et 是当前 slice 的类型
// old 是原有的 slice
// cap 是满足扩容所需的最小容量
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
}
}
}
// 下面去计算新的数组所需要的内存
// 通过 old.len, cap, 以及 newcap 计算
var overflow bool
var lenmem, newlenmem, capmem uintptr
// Specialize for common values of et.size.
// For 1 we don't need any division/multiplication.
// For sys.PtrSize, compiler will optimize division/multiplication into a shift by a constant.
// For powers of 2, use a variable shift.
switch {
case et.size == 1:
lenmem = uintptr(old.len)
newlenmem = uintptr(cap)
capmem = roundupsize(uintptr(newcap))
overflow = uintptr(newcap) > maxAlloc
newcap = int(capmem)
// ... 有好几个分支，看一个类似的就可以了
}
// 检查是不是超过内存限制
if overflow || capmem > maxAlloc {
panic(errorString("growslice: cap out of range"))
}
// 分配内存
var p unsafe.Pointer
if et.ptrdata == 0 {
p = mallocgc(capmem, nil, false)
// The append() that calls growslice is going to overwrite from old.len to cap (which will be the new length).
// Only clear the part that will not be overwritten.
memclrNoHeapPointers(add(p, newlenmem), capmem - newlenmem)
} else {
// Note: can't use rawmem (which avoids zeroing of memory), because then GC can scan uninitialized memory.
p = mallocgc(capmem, et, true)
if lenmem > 0 && writeBarrier.enabled {
// Only shade the pointers in old.array since we know the destination slice p
// only contains nil pointers because it has been cleared during alloc.
bulkBarrierPreWriteSrcOnly(uintptr(p), uintptr(old.array), lenmem - et.size + et.ptrdata)
}
}
// 将原本的数组复制到新数组上
memmove(p, old.array, lenmem)
return slice {
p, old.len, newcap
}
}
我们重点看一下扩容的算法，可以发现有三种逻辑：
1.如果需要的最小容量比两倍原有容量大，那么就取需要的容量
2.如果原有 slice 长度小于 1024 那么每次就扩容为原来的两倍
3.如果原 slice 大于等于 1024 那么每次扩容就扩为原来的 1.25 倍
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
我们先看一下 Slice 初始化的方式
var s1 []int
s2 := make([]uint, 0)
s3 := []int{}
// fmt.Printf("%p: %v, len: %d, cap: %d\n", s1, s1, len(s1), cap(s1))
// 0x0: [], len: 0, cap: 0
// 0x587450: [], len: 0, cap: 0
// 0x587450: [], len: 0, cap: 0
tips: %p 打印 slice 会打印 slice 底层指向的数组的地址
我们可以发现，第一种方式进行初始化，出现的也就是 slice 的零值，底层的数组指针是一个 nil
第二种和第三种的底层指针都有一个值，不过没有实际分配内存
这三种方式初始化出来的 cap、和 len 的长度都是 0
规范技巧
1.slice 作为参数时，不要直接存储它的引用，而是通过 copy 复制一份
原因请查看上文，Slice 的结构
示例：Uber Go 规范: nil-是一个有效的-slice
2.要检查切片是否为空，请始终使用 len(s) == 0 。而非 nil 。
原因请查看上文，Slice 初始化
示例：Uber Go 规范: 在边界处拷贝-Slices-和-Maps
