切片
切片
切片通过对数组进行封装，为数据序列提供了更通用、强大而方便的接口。
// 创建 len 为 5，cap 为 5 的 Slice
s := make([]byte, 5)
// 对 Slice 进行二次切片，此时 len 为 2，cap 为 3
s = s[2:4]
// 恢复 Slice 的长度
s = s[:cap(s)]
除了矩阵变换这类需要明确维度的情况外，
func (f *File) Read(buf []byte) (n int, err error)
读取的最大字节说被限定在
切片定义
可以使用如下方式创建
// 使用内置函数创建
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},
}
和数组一样，内置的
值得一提的是，当需要声明空
var t []string
// 优于
t := []string{}
前者是
遍历
遍历切片的方式和遍历数组的方式类似：
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])
}
切片类型强制转换
为了安全，当两个切片类型
下面的代码通过两种方法将
// +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)
}
第一种强制转换是先将切片数据的开始地址转换为一个较大的数组的指针，然后对数组指针对应的数组重新做切片操作。中间需要
第二种转换操作是分别取到两个不同类型的切片头信息指针，任何类型的切片头部信息底层都是对应
通过基准测试，我们可以发现用
切片操作
append
// 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"}
当被追加
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
每个添加操作中的第二个
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
我们也可以使用内置的
func copy(dst, src []T) int
// 申请较大的空间容量
t := make([]byte, len(s), (cap(s)+1)*2)
copy(t, s)
s = t
用
a = append(a, x...) // 为x切片扩展足够的空间
copy(a[i+len(x):], a[i:]) // a[i:]向后移动len(x)个位置
copy(a[i:], x) // 复制新添加的切片
稍显不足的是，在第一句扩展切片容量的时候，扩展空间部分的元素复制是没有必要的。没有专门的内置函数用于扩展切片的容量，
删除切片元素
根据要删除元素的位置有三种情况：从开头位置删除，从中间位置删除，从尾部删除。其中删除切片尾部的元素最快：
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个元素
删除开头的元素也可以不移动数据指针，但是将后面的数据向开头移动。可以用
a = []int{1, 2, 3}
a = append(a[:0], a[1:]...) // 删除开头1个元素
a = append(a[:0], a[N:]...) // 删除开头N个元素
也可以用
a = []int{1, 2, 3}
a = a[:copy(a, a[1:])] // 删除开头1个元素
a = a[:copy(a, a[N:])] // 删除开头N个元素
对于删除中间的元素，需要对剩余的元素进行一次整体挪动，同样可以用
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
}
可以看出切片的开头部分和x := []int{2,3,5,7,11} 和 y := x[1:3] 两个切片对应的内存结构。
切片内存技巧
对于切片来说，
比如下面的
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
}
切片高效操作的要点是要降低内存分配的次数，尽量保证
避免切片内存泄漏
切片操作并不会复制底层的数据。底层的数组会被保存在内存中，直到它不再被引用。但是有时候可能会因为一个小的内存引用而导致底层整个数组处于被使用的状态，这会延迟自动内存回收器对底层数组的回收。
例如，
func FindPhoneNumber(filename string) []byte {
b, _ := ioutil.ReadFile(filename)
return regexp.MustCompile("[0-9]+").Find(b)
}
这段代码返回的
要修复这个问题，可以将感兴趣的数据复制到一个新的切片中（数据的传值是
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] // 从切片删除最后一个元素
当然，如果切片存在的周期很短的话，可以不用刻意处理这个问题。因为如果切片本身已经可以被
案例：哈希表
-
较小的
m 表示将创建更少的存储桶，但是表中存储的每个密钥与其他密钥共享存储桶的可能性更高，从而降低了查找速度 -
较大的
m 表示将创建更多存储桶，因此表中存储的每个密钥与其他密钥共享存储桶的可能性较低，从而加快了查找速度
// 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
}
- 如果输入键与该存储桶中的键匹配，则返回存储桶的值，并且布尔值为
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,
})
}
- 如果输入键与该存储桶中的键匹配，请用输入值覆盖键的值
- 如果不匹配，则将新条目添加到存储桶的键
/ 值对片中。
我们创建了一个非常基本的哈希表，可用于处理键
// 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)
在实现通用哈希表时，我在
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
}