切片
切片
切片通过对数组进行封装，为数据序列提供了更通用、强大而方便的接口。Slice 可以看做更为灵活的引用类型（Reference Type），它并不真实地存放数组值，而是包含数组指针(ptr)，len，cap 三个属性的结构体。换言之，Slice 可以看做对于数组中某个段的描述，包含了指向数组的指针，段长度，以及段的最大潜在长度，其结构如下图所示：
// 创建 len 为 5，cap 为 5 的 Slice
s := make([]byte, 5)
// 对 Slice 进行二次切片，此时 len 为 2，cap 为 3
s = s[2:4]
// 恢复 Slice 的长度
s = s[:cap(s)]
除了矩阵变换这类需要明确维度的情况外，Go 中的大部分数组编程都是通过切片来完成的。切片保存了对底层数组的引用，若你将某个切片赋予另一个切片，它们会引用同一个数组。若某个函数将一个切片作为参数传入，则它对该切片元素的修改对调用者而言同样可见，这可以理解为传递了底层数组的指针。例如 io 包中，File 类型的方法 Read。
func (f *File) Read(buf []byte) (n int, err error)
读取的最大字节说被限定在 buf 的长度（len(buf)）和 file 的剩余可读字节数。
切片定义
可以使用如下方式创建 Slice:
// 使用内置函数创建
make([]Type, length, capacity)
make([]Type, length)
// 声明为不定长度切片
[]Type{}
[]Type{value1, value2, ..., valueN}
var (
a []int // nil切片, 和 nil 相等, 一般用来表示一个不存在的切片
b = []int{} // 空切片, 和 nil 不相等, 一般用来表示一个空的集合
c = []int{1, 2, 3} // 有3个元素的切片, len和cap都为3
d = c[:2] // 有2个元素的切片, len为2, cap为3
e = c[0:2:cap(c)] // 有2个元素的切片, len为2, cap为3
f = c[:0] // 有0个元素的切片, len为0, cap为3
g = make([]int, 3) // 有3个元素的切片, len和cap都为3
h = make([]int, 2, 3) // 有2个元素的切片, len为2, cap为3
i = make([]int, 0, 3) // 有0个元素的切片, len为0, cap为3
)
// 对现有数组进行切片转换
array[:]
array[:2]
array[2:]
array[2:3]
// 不定类型切片声明
a := []interface{}{2, 1, []interface{}{3, []interface{}{4, 5}, 6}, 7, []interface{}{8}}
// 二维不定类型切片
b := [][]interface{}{
[]interface{}{1, 2},
[]interface{}{3, 4},
}
和数组一样，内置的 len 函数返回切片中有效元素的长度，内置的 cap 函数返回切片容量大小，容量必须大于或等于切片的长度。也可以通过 reflect.SliceHeader 结构访问切片的信息（只是为了说明切片的结构，并不是推荐的做法）。切片可以和 nil 进行比较，只有当切片底层数据指针为空时切片本身为 nil，这时候切片的长度和容量信息将是无效的。如果有切片的底层数据指针为空，但是长度和容量不为 0 的情况，那么说明切片本身已经被损坏了（比如直接通过 reflect.SliceHeader 或 unsafe 包对切片作了不正确的修改）。
值得一提的是，当需要声明空 Slice 的时候，
var t []string
// 优于
t := []string{}
前者是 nil 值，而后者是一个非 nil 切长度为 1 的 slice，通常两者的行为是一样的，但是在一些特殊情况下不同。例如 json 序列化的时候，前者别序列化为 null，而后者则为[]。
遍历
遍历切片的方式和遍历数组的方式类似：
for i := range a {
fmt.Printf("a[%d]: %d\n", i, a[i])
}
for i, v := range b {
fmt.Printf("b[%d]: %d\n", i, v)
}
for i := 0; i < len(c); i++ {
fmt.Printf("c[%d]: %d\n", i, c[i])
}
切片类型强制转换
为了安全，当两个切片类型[]T 和[]Y 的底层原始切片类型不同时，Go 语言是无法直接转换类型的。不过安全都是有一定代价的，有时候这种转换是有它的价值的——可以简化编码或者是提升代码的性能。比如在 64 位系统上，需要对一个[]float64 切片进行高速排序，我们可以将它强制转为[]int 整数切片，然后以整数的方式进行排序（因为 float64 遵循 IEEE754 浮点数标准特性，当浮点数有序时对应的整数也必然是有序的）。
下面的代码通过两种方法将[]float64 类型的切片转换为[]int 类型的切片：
// +build amd64 arm64
import "sort"
var a = []float64{4, 2, 5, 7, 2, 1, 88, 1}
func SortFloat64FastV1(a []float64) {
// 强制类型转换
var b []int = ((*[1 << 20]int)(unsafe.Pointer(&a[0])))[:len(a):cap(a)]
// 以int方式给float64排序
sort.Ints(b)
}
func SortFloat64FastV2(a []float64) {
// 通过 reflect.SliceHeader 更新切片头部信息实现转换
var c []int
aHdr := (*reflect.SliceHeader)(unsafe.Pointer(&a))
cHdr := (*reflect.SliceHeader)(unsafe.Pointer(&c))
*cHdr = *aHdr
// 以int方式给float64排序
sort.Ints(c)
}
第一种强制转换是先将切片数据的开始地址转换为一个较大的数组的指针，然后对数组指针对应的数组重新做切片操作。中间需要 unsafe.Pointer 来连接两个不同类型的指针传递。需要注意的是，Go 语言实现中非 0 大小数组的长度不得超过 2GB，因此需要针对数组元素的类型大小计算数组的最大长度范围（[]uint8 最大 2GB，[]uint16 最大 1GB，以此类推，但是[]struct{}数组的长度可以超过 2GB）。
第二种转换操作是分别取到两个不同类型的切片头信息指针，任何类型的切片头部信息底层都是对应 reflect.SliceHeader 结构，然后通过更新结构体方式来更新切片信息，从而实现 a 对应的[]float64 切片到 c 对应的[]int 类型切片的转换。
通过基准测试，我们可以发现用 sort.Ints 对转换后的[]int 排序的性能要比用 sort.Float64s 排序的性能好一点。不过需要注意的是，这个方法可行的前提是要保证[]float64 中没有 NaN 和 Inf 等非规范的浮点数（因为浮点数中 NaN 不可排序，正 0 和负 0 相等，但是整数中没有这类情形）。
切片操作
append
Go 提供了内置的 append 函数，来动态为 Slice 添加数据，该函数会返回新的切片对象，包含了原始的 Slice 中值以及新增的值。如果原有的 Slice 的容量不足以存放新增的序列，那么会自动分配新的内存：
// len=0 cap=0 []
var s []int
// len=1 cap=2 [0]
s = append(s, 0)
// len=2 cap=2 [0 1]
s = append(s, 1)
// len=5 cap=8 [0 1 2 3 4]
s = append(s, 2, 3, 4)
// 使用 ... 来自动展开数组并进行合并
a := []string{"John", "Paul"}
b := []string{"George", "Ringo", "Pete"}
a = append(a, b...) // equivalent to "append(a, b[0], b[1], b[2])"
// a == []string{"John", "Paul", "George", "Ringo", "Pete"}
当被追加 slice 有剩余容量时，新增的值，直接赋值到 slice 内部的数组中；反之 slice 将重新申请新的数组以容纳追加的元素，先拷贝原始内容，在添加新元素。
x1 := []byte{'h', 'e', 'l', 'l', 'o'}
x2 := x1[:0]
x2 = append(x2, []byte("shanexu")...)
fmt.Println(string(x1)) // 打印 hello，先拷贝，后追加
y1 := []byte{'h', 'e', 'l', 'l', 'o', 'w', 'o', 'r', 'l', 'd'}
y2 := y1[:0]
y2 = append(y2, []byte("shanexu")...)
fmt.Println(string(y1)) // 打印 shanexurld
每个添加操作中的第二个 append 调用都会创建一个临时切片，并将 a[i:]的内容复制到新创建的切片中，然后将临时创建的切片再追加到 a[:i]。由于 append 函数返回新的切片，也就是它支持链式操作。我们可以将多个 append 操作组合起来，实现在切片中间插入元素：
var a []int
a = append(a[:i], append([]int{x}, a[i:]...)...) // 在第i个位置插入x
a = append(a[:i], append([]int{1,2,3}, a[i:]...)...) // 在第i个位置插入切片
copy
我们也可以使用内置的 copy 函数，进行 Slice 的复制，该函数支持对于不同长度的 Slice 进行复制，其会自动使用最小的元素数目。同时，copy 函数还能够自动处理使用了相同的底层数组之间的 Slice 复制，以避免额外的空间浪费。
func copy(dst, src []T) int
// 申请较大的空间容量
t := make([]byte, len(s), (cap(s)+1)*2)
copy(t, s)
s = t
用 copy 和 append 组合也可以实现在中间位置插入多个元素(也就是插入一个切片):
a = append(a, x...) // 为x切片扩展足够的空间
copy(a[i+len(x):], a[i:]) // a[i:]向后移动len(x)个位置
copy(a[i:], x) // 复制新添加的切片
稍显不足的是，在第一句扩展切片容量的时候，扩展空间部分的元素复制是没有必要的。没有专门的内置函数用于扩展切片的容量，append 本质是用于追加元素而不是扩展容量，扩展切片容量只是 append 的一个副作用。
删除切片元素
根据要删除元素的位置有三种情况：从开头位置删除，从中间位置删除，从尾部删除。其中删除切片尾部的元素最快：
a = []int{1, 2, 3}
a = a[:len(a)-1] // 删除尾部1个元素
a = a[:len(a)-N] // 删除尾部N个元素
删除开头的元素可以直接移动数据指针：
a = []int{1, 2, 3}
a = a[1:] // 删除开头1个元素
a = a[N:] // 删除开头N个元素
删除开头的元素也可以不移动数据指针，但是将后面的数据向开头移动。可以用 append 原地完成（所谓原地完成是指在原有的切片数据对应的内存区间内完成，不会导致内存空间结构的变化）：
a = []int{1, 2, 3}
a = append(a[:0], a[1:]...) // 删除开头1个元素
a = append(a[:0], a[N:]...) // 删除开头N个元素
也可以用 copy 完成删除开头的元素：
a = []int{1, 2, 3}
a = a[:copy(a, a[1:])] // 删除开头1个元素
a = a[:copy(a, a[N:])] // 删除开头N个元素
对于删除中间的元素，需要对剩余的元素进行一次整体挪动，同样可以用 append 或 copy 原地完成：
a = []int{1, 2, 3, ...}
a = append(a[:i], a[i+1:]...) // 删除中间1个元素
a = append(a[:i], a[i+N:]...) // 删除中间N个元素
a = a[:i+copy(a[i:], a[i+1:])] // 删除中间1个元素
a = a[:i+copy(a[i:], a[i+N:])] // 删除中间N个元素
删除开头的元素和删除尾部的元素都可以认为是删除中间元素操作的特殊情况。
切片结构
切片的结构定义，reflect.SliceHeader：
type SliceHeader struct {
Data uintptr
Len int
Cap int
}
可以看出切片的开头部分和 Go 字符串是一样的，但是切片多了一个 Cap 成员表示切片指向的内存空间的最大容量（对应元素的个数，而不是字节数）。下图是 x := []int{2,3,5,7,11} 和 y := x[1:3] 两个切片对应的内存结构。
切片内存技巧
对于切片来说，len 为 0 但是 cap 容量不为 0 的切片则是非常有用的特性。当然，如果 len 和 cap 都为 0 的话，则变成一个真正的空切片，虽然它并不是一个 nil 值的切片。在判断一个切片是否为空时，一般通过 len 获取切片的长度来判断，一般很少将切片和 nil 值做直接的比较。
比如下面的 TrimSpace 函数用于删除[]byte 中的空格。函数实现利用了 0 长切片的特性，实现高效而且简洁。
func TrimSpace(s []byte) []byte {
b := s[:0]
for _, x := range s {
if x != ' ' {
b = append(b, x)
}
}
return b
}
其实类似的根据过滤条件原地删除切片元素的算法都可以采用类似的方式处理（因为是删除操作不会出现内存不足的情形）：
func Filter(s []byte, fn func(x byte) bool) []byte {
b := s[:0]
for _, x := range s {
if !fn(x) {
b = append(b, x)
}
}
return b
}
切片高效操作的要点是要降低内存分配的次数，尽量保证 append 操作不会超出 cap 的容量，降低触发内存分配的次数和每次分配内存大小。
避免切片内存泄漏
切片操作并不会复制底层的数据。底层的数组会被保存在内存中，直到它不再被引用。但是有时候可能会因为一个小的内存引用而导致底层整个数组处于被使用的状态，这会延迟自动内存回收器对底层数组的回收。
例如，FindPhoneNumber 函数加载整个文件到内存，然后搜索第一个出现的电话号码，最后结果以切片方式返回。
func FindPhoneNumber(filename string) []byte {
b, _ := ioutil.ReadFile(filename)
return regexp.MustCompile("[0-9]+").Find(b)
}
这段代码返回的[]byte 指向保存整个文件的数组。因为切片引用了整个原始数组，导致自动垃圾回收器不能及时释放底层数组的空间。一个小的需求可能导致需要长时间保存整个文件数据。这虽然这并不是传统意义上的内存泄漏，但是可能会拖慢系统的整体性能。
要修复这个问题，可以将感兴趣的数据复制到一个新的切片中（数据的传值是 Go 语言编程的一个哲学，虽然传值有一定的代价，但是换取的好处是切断了对原始数据的依赖）：
func FindPhoneNumber(filename string) []byte {
b, _ := ioutil.ReadFile(filename)
b = regexp.MustCompile("[0-9]+").Find(b)
return append([]byte{}, b...)
}
类似的问题，在删除切片元素时可能会遇到。假设切片里存放的是指针对象，那么下面删除末尾的元素后，被删除的元素依然被切片底层数组引用，从而导致不能及时被自动垃圾回收器回收（这要依赖回收器的实现方式）：
var a []*int{ ... }
a = a[:len(a)-1] // 被删除的最后一个元素依然被引用, 可能导致GC操作被阻碍
保险的方式是先将需要自动内存回收的元素设置为nil，保证自动回收器可以发现需要回收的对象，然后再进行切片的删除操作：
var a []*int{ ... }
a[len(a)-1] = nil // GC回收最后一个元素内存
a = a[:len(a)-1] // 从切片删除最后一个元素
当然，如果切片存在的周期很短的话，可以不用刻意处理这个问题。因为如果切片本身已经可以被 GC 回收的话，切片对应的每个元素自然也就是可以被回收的了。
案例：哈希表
Table 类型是包的基础。它在内部使用切片存储键/值字符串对，其中切片中的哈希表存储桶数由整数 m 确定：
-
较小的 m 表示将创建更少的存储桶，但是表中存储的每个密钥与其他密钥共享存储桶的可能性更高，从而降低了查找速度
-
较大的 m 表示将创建更多存储桶，因此表中存储的每个密钥与其他密钥共享存储桶的可能性较低，从而加快了查找速度
kv 类型是用于简化存储键/值字符串对的小帮手：
// Package hashtable implements a basic hashtable for string key/value pairs.
package hashtable
// A Table is a basic hashtable.
type Table struct {
m int
table [][]kv
}
// A kv stores key/value data in a Table.
type kv struct {
Key, Value string
}
// New creates a Table with m internal buckets.
func New(m int) *Table {
return &Table{
m: m,
table: make([][]kv, m),
}
}
该哈希表支持两种操作：
-
Get: 确定哈希表中是否存在键，返回值（如果找到）和一个布尔值，指示值是否存在
-
Insert: 将新的键/值对插入哈希表，覆盖同一键的所有先前值
这两个操作都需要一个哈希函数，该函数可以接受输入字符串并返回一个整数，该整数指示存储键值的存储区。
// hash picks a hashtable index to use to store a string with key s.
func (t *Table) hash(s string) int {
h := fnv.New32()
h.Write([]byte(s))
return int(h.Sum32()) % t.m
}
我选择 hash/fnv32 作为简单的非加密哈希函数，该函数返回整数。然后，通过计算模运算 hash % t.m，我们可以确保生成的整数返回我们哈希表存储桶之一的索引。
// Get determines if key is present in the hashtable, returning its value and
// whether or not the key was found.
func (t *Table) Get(key string) (string, bool) {
// Hash key to determine which bucket this key's value belongs in.
i := t.hash(key)
for j, kv := range t.table[i] {
if key == kv.Key {
// Found a match, return it!
return t.table[i][j].Value, true
}
}
// No match.
return "", false
}
Table.Get 的实现对输入键进行哈希处理，以确定使用哪个存储区来存储键的值。确定存储桶后，将遍历该存储桶中的所有键/值对：
- 如果输入键与该存储桶中的键匹配，则返回存储桶的值，并且布尔值为 true
- 如果不匹配，则返回一个空字符串，并返回布尔值 false
// Insert inserts a new key/value pair into the Table.
func (t *Table) Insert(key, value string) {
i := t.hash(key)
for j, kv := range t.table[i] {
if key == kv.Key {
// Overwrite previous value for the same key.
t.table[i][j].Value = value
return
}
}
// Add a new value to the table.
t.table[i] = append(t.table[i], kv{
Key: key,
Value: value,
})
}
Table.Insert 还必须对输入键进行哈希处理，以确定应使用哪个存储桶来插入键/值对。遍历存储桶中的键/值对时，我们可能发现匹配的键已存在：
- 如果输入键与该存储桶中的键匹配，请用输入值覆盖键的值
- 如果不匹配，则将新条目添加到存储桶的键/值对片中。
我们创建了一个非常基本的哈希表，可用于处理键/值字符串对。
// 8 buckets ought to be plenty.
t := hashtable.New(8)
t.Insert("foo", "bar")
t.Insert("baz", "qux")
v, ok := t.Get("foo")
fmt.Printf("t.Get(%q) = (%q, %t)", "foo", v, ok)
// t.Get("foo") = ("bar", true)
在实现通用哈希表时，我在 Gophers Slack 上的#performance 中与一些人进行了讨论，讨论如何访问内置 Go 映射使用的运行时“通用”哈希功能。
func hash(type A comparable)(a A) uintptr {
var m interface{} = make(map[A]struct{})
hf := (*mh)(*(*unsafe.Pointer)(unsafe.Pointer(&m))).hf
return hf(unsafe.Pointer(&a), 0)
}
func main() {
fmt.Println(hash(0))
fmt.Println(hash(false))
fmt.Println(hash("why hello there"))
}
///////////////////////////
/// stolen from runtime ///
///////////////////////////
// mh is an inlined combination of runtime._type and runtime.maptype.
type mh struct {
_ uintptr
_ uintptr
_ uint32
_ uint8
_ uint8
_ uint8
_ uint8
_ func(unsafe.Pointer, unsafe.Pointer) bool
_ *byte
_ int32
_ int32
_ unsafe.Pointer
_ unsafe.Pointer
_ unsafe.Pointer
hf func(unsafe.Pointer, uintptr) uintptr
}