4.1. 数组

  • 数组是一个由固定长度的特定类型元素组成的序列，一个数组可以由零个或多个元素组成。
  • Go语言中很少直接使用数组，因为数组的长度是固定的
  • 和数组对应的类型是Slice（切片），它是可以增长和收缩的动态序列，slice功能也更灵活，
    • 但是要理解slice工作原理的话需要先理解数组
  • 创建数组和切片的直接区别：定义了长度
1
2
3
var x []int // 切片
x = append(x, 2)
var y = [...]int{1, 2, 3} // 数组

数组

  • 数组的每个元素可以通过索引下标来访问，索引下标的范围是从0开始到数组长度减1的位置。
  • 内置的len函数将返回数组中元素的个数。
1
2
3
4
5
6
7
8
9
10
11
12
13
var a [3]int             // array of 3 integers
fmt.Println(a[0])        // print the first element
fmt.Println(a[len(a)-1]) // print the last element, a[2]

// Print the indices and elements.
for i, v := range a {
    fmt.Printf("%d %d\n", i, v)
}

// Print the elements only.
for _, v := range a {
    fmt.Printf("%d\n", v)
}

数组的初始化

  • 默认情况下，数组的每个元素都被初始化为元素类型对应的零值，对于数字类型来说就是0。
  • 可以使用数组字面值语法用一组值来初始化数组
1
2
3
var q [3]int = [3]int{1, 2, 3}
var r [3]int = [3]int{1, 2}
fmt.Println(r[2]) // "0"
  • 在数组字面值中，如果在数组的长度位置出现的是“...”省略号，则表示数组的长度是根据初始化值的个数来计算
1
2
q := [...]int{1, 2, 3}
fmt.Printf("%T\n", q) // "[3]int"
  • 可以指定一个索引和对应值列表的方式初始化
1
2
3
4
5
6
7
8
9
10
11
12
type Currency int

const (
    USD Currency = iota // 美元
    EUR                 // 欧元
    GBP                 // 英镑
    RMB                 // 人民币
)

symbol := [...]string{USD: "$", EUR: "€", GBP: "￡", RMB: "￥"}

fmt.Println(RMB, symbol[RMB]) // "3 ￥"
  • 未指定初始值的元素将用零值初始化
1
r := [...]int{99: -1}

定义了一个含有100个元素的数组r，最后一个元素被初始化为-1，其它元素都是用0初始化。

数组的长度

  • 数组的长度是数组类型的一个组成部分，因此[3]int和[4]int是两种不同的数组类型
  • 数组的长度必须是常量表达式，因为数组的长度需要在编译阶段确定。
1
2
q := [3]int{1, 2, 3}
q = [4]int{1, 2, 3, 4} // compile error: cannot assign [4]int to [3]int

数组的比较

  • 如果一个数组的元素类型是可以相互比较的，那么数组类型也是可以相互比较的
  • 这时候我们可以直接通过==比较运算符来比较两个数组，只有当两个数组的所有元素都是相等的时候数组才是相等的
  • 不相等比较运算符!=遵循同样的规则
1
2
3
4
5
6
a := [2]int{1, 2}
b := [...]int{1, 2}
c := [2]int{1, 3}
fmt.Println(a == b, a == c, b == c) // "true false false"
d := [3]int{1, 2}
fmt.Println(a == d) // compile error: cannot compare [2]int == [3]int
例子

crypto/sha256包的Sum256函数对一个任意的字节slice类型的数据生成一个对应的消息摘要。消息摘要有256bit大小，因此对应[32]byte数组类型

1
2
3
4
5
6
7
8
9
10
11
12
import "crypto/sha256"

func main() {
    c1 := sha256.Sum256([]byte("x"))
    c2 := sha256.Sum256([]byte("X"))
    fmt.Printf("%x\n%x\n%t\n%T\n", c1, c2, c1 == c2, c1)
    // Output:
    // 2d711642b726b04401627ca9fbac32f5c8530fb1903cc4db02258717921a4881
    // 4b68ab3847feda7d6c62c1fbcbeebfa35eab7351ed5e78f4ddadea5df64b8015
    // false
    // [32]uint8
}

可以显式地传入一个数组指针，那样的话函数通过指针对数组的任何修改都可以直接反馈到调用者。

1
2
3
4
5
6
7
8
9
func zero(ptr *[32]byte) {
    for i := range ptr {
        ptr[i] = 0
    }
}

func zero(ptr *[32]byte) {
    *ptr = [32]byte{}
}

4.2. Slice

  • Slice（切片）代表变长的序列，序列中每个元素都有相同的类型
  • 一个slice类型一般写作[]T，其中T代表slice中元素的类型；
  • slice的语法和数组很像，只是没有固定长度而已
  • 一个slice是一个轻量级的数据结构，提供了访问数组子序列（或者全部）元素的功能，而且slice的底层确实引用一个数组对象

slice的构成

  • 一个slice由三个部分构成：指针、长度和容量。
  • 指针指向第一个slice元素对应的底层数组元素的地址，要注意的是slice的第一个元素并不一定就是数组的第一个元素。
  • 长度对应slice中元素的数目；长度不能超过容量，
  • 容量一般是从slice的开始位置到底层数据的结尾位置。
  • 内置的len和cap函数分别返回slice的长度和容量

多个slice之间可以共享底层的数据，并且引用的数组部分区间可能重叠。

切片

  • slice的切片操作s[i:j]，其中0 ≤ i≤ j≤ cap(s)，用于创建一个新的slice，引用s的从第i个元素开始到第j-1个元素的子序列。

  • 新的slice将只有j-i个元素。

  • 如果i位置的索引被省略的话将使用0代替，如果j位置的索引被省略的话将使用len(s)代替

  • 如果切片操作超出cap(s)的上限将导致一个panic异常，但是超出len(s)则是意味着扩展了slice，因为新slice的长度会变大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
months := [...]string{1: "January", /* ... */, 12: "December"}

Q2 := months[4:7]
summer := months[6:9]
fmt.Println(Q2)     // ["April" "May" "June"]
fmt.Println(summer) // ["June" "July" "August"]

for _, s := range summer {
    for _, q := range Q2 {
        if s == q {
            fmt.Printf("%s appears in both\n", s)
        }
    }
}

fmt.Println(summer[:20]) // panic: out of range

endlessSummer := summer[:5] // extend a slice (within capacity)
fmt.Println(endlessSummer)  // "[June July August September October]"

字符串和[]byte的切片

  • 字符串的切片操作和[]byte字节类型切片的切片操作是类似的。

  • 都写作x[m:n]

  • 并且都是返回一个原始字节序列的子序列，底层都是共享之前的底层数组，因此这种操作都是常量时间复杂度

  • x[m:n]切片操作对于字符串则生成一个新字符串，如果x是[]byte的话则生成一个新的[]byte

  • 换句话说，复制一个slice只是对底层的数组创建了一个新的slice别名

例子

reverse函数在原内存空间将[]int类型的slice反转，而且它可以用于任意长度的slice

1
2
3
4
5
6
7
8
9
10
// reverse reverses a slice of ints in place.
func reverse(s []int) {
    for i, j := 0, len(s)-1; i < j; i, j = i+1, j-1 {
        s[i], s[j] = s[j], s[i]
    }
}

a := [...]int{0, 1, 2, 3, 4, 5}
reverse(a[:])
fmt.Println(a) // "[5 4 3 2 1 0]"

一种将slice元素循环向左旋转n个元素的方法是三次调用reverse反转函数，第一次是反转开头的n个元素，然后是反转剩下的元素，最后是反转整个slice的元素。（如果是向右循环旋转，则将第三个函数调用移到第一个调用位置就可以了。）

1
2
3
4
5
6
s := []int{0, 1, 2, 3, 4, 5}
// Rotate s left by two positions.
reverse(s[:2])
reverse(s[2:])
reverse(s)
fmt.Println(s) // "[2 3 4 5 0 1]"

切片的初始化

  • slice和数组的字面值语法很类似，它们都是用花括弧包含一系列的初始化元素，
  • 但是对于slice并没有指明序列的长度。
  • 这会隐式地创建一个合适大小的数组，然后slice的指针指向底层的数组。
  • slice的字面值也可以按顺序指定初始化值序列，或者是通过索引和元素值指定，或者用两种风格的混合语法初始化

切片的比较

  • slice之间不能比较，因此我们不能使用==操作符来判断两个slice是否含有全部相等元素
  • 标准库提供了高度优化的bytes.Equal函数来判断两个字节型slice是否相等（[]byte），但是对于其他类型的slice，我们必须自己展开每个元素进行比较
1
2
3
4
5
6
7
8
9
10
11
func equal(x, y []string) bool {
    if len(x) != len(y) {
        return false
    }
    for i := range x {
        if x[i] ![] {
            return false
        }
    }
    return true
}

为何slice不直接支持比较运算符呢

  • 第一个原因，一个slice的元素是间接引用的，一个slice甚至可以包含自身，虽然有很多办法处理这种情形，但是没有一个是简单有效的。
    • 当slice声明为[]interface{}时，slice的元素可以是自身
  • 第二个原因，因为slice的元素是间接引用的，一个固定的slice值（注：指slice本身的值，不是元素的值）在不同的时刻可能包含不同的元素，因为底层数组的元素可能会被修改
    • 例如Go语言中map的key只做简单的浅拷贝，它要求key在整个生命周期内保持不变性
      • 例如slice扩容，就会导致其本身的值/地址变化
    • 而用深度相等判断的话，显然在map的key这种场合不合适。对于像指针或chan之类的引用类型，==相等测试可以判断两个是否是引用相同的对象
    • 一个针对slice的浅相等测试的==操作符可能是有一定用处的，也能临时解决map类型的key问题
    • 但是slice和数组不同的相等测试行为会让人困惑。因此，安全的做法是直接禁止slice之间的比较操作
slice唯一合法的比较操作是和nil比较
1
if summer == nil { /* ... */ }
  • 一个零值的slice等于nil。
  • 一个nil值的slice并没有底层数组。
  • 一个nil值的slice的长度和容量都是0，但是也有非nil值的slice的长度和容量也是0的，例如[]int{}或make([]int, 3)[3:]。
  • 与任意类型的nil值一样，我们可以用[]int(nil)类型转换表达式来生成一个对应类型slice的nil值。
1
2
3
4
var s []int    // len(s) == 0, s == nil
s = nil        // len(s) == 0, s == nil
s = []int(nil) // len(s) == 0, s == nil
s = []int{}    // len(s) == 0, s != nil
  • 如果你需要测试一个slice是否是空的，使用len(s) == 0来判断，而不应该用s == nil来判断。
  • 除了和nil相等比较外，一个nil值的slice的行为和其它任意0长度的slice一样
  • 除了文档已经明确说明的地方，所有的Go语言函数应该以相同的方式对待nil值的slice和0长度的slice。

make函数创建slice

  • 内置的make函数创建一个指定元素类型、长度和容量的slice
  • 容量部分可以省略，在这种情况下，容量将等于长度。
1
2
make([]T, len)
make([]T, len, cap) // same as make([]T, cap)[:len]
  • 在底层，make创建了一个匿名的数组变量，然后返回一个slice；只有通过返回的slice才能引用底层匿名的数组变量。
  • 在第一种语句中，slice是整个数组的view。
  • 在第二个语句中，slice只引用了底层数组的前len个元素，但是容量将包含整个的数组。额外的元素是留给未来的增长用的。

slice的索引

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
//demo_8.go
package main

import (
	"fmt"
)

func main() {
	sli := [] int {1, 2, 3, 4, 5, 6}

	fmt.Println("sli[0:3] ==", sli[0:3])
	fmt.Printf("len=%d cap=%d slice=%v\n",len(sli[0:3]),cap(sli[0:3]),sli[0:3])

	fmt.Println("sli[0:3:4] ==", sli[0:3:4])
	fmt.Printf("len=%d cap=%d slice=%v\n",len(sli[0:3:4]),cap(sli[0:3:4]),sli[0:3:4])
}

// sli[0:3] == [1 2 3]
// len=3 cap=6 slice=[1 2 3]
// sli[0:3:5] == [1 2 3]
// len=3 cap=4 slice=[1 2 3]

上述切片方式中

  • 第一种：s[i:j]：从i截取到j
  • 第二种：s[i:j:k]：从i截取到j，容量为k

4.2.1. append函数

内置的append函数用于向slice追加元素

1
2
3
4
5
var runes []rune
for _, r := range "Hello, 世界" {
    runes = append(runes, r)
}
fmt.Printf("%q\n", runes) // "['H' 'e' 'l' 'l' 'o' ',' ' ' '世' '界']"

对应这个特殊的问题我们可以通过Go语言内置的[]rune("Hello, 世界")转换操作完成。

append函数对于理解slice底层是如何工作的非常重要，所以让我们仔细查看究竟是发生了什么

实现appendInt函数

专门用于处理[]int类型的slice

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func appendInt(x []int, y int) []int {
    var z []int
    zlen := len(x) + 1
    if zlen <= cap(x) {
        // There is room to grow.  Extend the slice.
        z = x[:zlen]
    } else {
        // There is insufficient space.  Allocate a new array.
        // Grow by doubling, for amortized linear complexity.
        zcap := zlen
        if zcap < 2*len(x) {
            zcap = 2 * len(x)
        }
        z = make([]int, zlen, zcap)
        copy(z, x) // a built-in function; see text
    }
    z[len(x)] = y
    return z
}

  • 每次调用appendInt函数，必须先检测slice底层数组是否有足够的容量来保存新添加的元素。

  • 如果有足够空间的话，直接扩展slice（依然在原有的底层数组之上），将新添加的y元素复制到新扩展的空间，并返回slice。因此，输入的x和输出的z共享相同的底层数组。（line 4~6）

  • 如果没有足够的增长空间的话，appendInt函数则会先分配一个足够大的slice用于保存新的结果，先将输入的x复制到新的空间，然后添加y元素。结果z和输入的x引用的将是不同的底层数组。（line10~15）

  • 内置的copy函数可以方便地将一个slice复制另一个相同类型的slice。

    • copy函数的第一个参数是要复制的目标slice
    • 第二个参数是源slice
    • 目标和源的位置顺序和dst = src赋值语句是一致的。
    • 两个slice可以共享同一个底层数组，甚至有重叠也没有问题。
    • copy函数将返回成功复制的元素的个数（我们这里没有用到），等于两个slice中较小的长度，所以我们不用担心覆盖会超出目标slice的范围。

  • 为了提高内存使用效率，新分配的数组一般略大于保存x和y所需要的最低大小。

    • 通过在每次扩展数组时直接将长度翻倍从而避免了多次内存分配，也确保了添加单个元素操的平均时间是一个常数时间
通常是将append返回的结果直接赋值给输入的slice变量的原因
  • 内置的append函数可能使用比appendInt更复杂的内存扩展策略。
  • 因此，通常我们并不知道append调用是否导致了内存的重新分配
  • 因此我们也不能确认新的slice和原始的slice是否引用的是相同的底层数组空间。
  • 同样，我们不能确认在原先的slice上的操作是否会影响到新的slice。
1
runes = append(runes, r)

  • 要正确地使用slice，需要记住尽管底层数组的元素是间接访问的，但是slice对应结构体本身的指针、长度和容量部分是直接访问的。

  • 要更新这些信息需要像上面例子那样一个显式的赋值操作。

  • 从这个角度看，slice并不是一个纯粹的引用类型，它实际上是一个类似下面结构体的聚合类型：

1
2
3
4
type IntSlice struct {
    ptr      *int
    len, cap int
}

改进appendint函数--追加多个数

1
2
3
4
5
6
7
func appendInt(x []int, y ...int) []int {
    var z []int
    zlen := len(x) + len(y)
    // ...expand z to at least zlen...
    copy(z[len(x):], y)
    return z
}

4.2.2. Slice内存技巧

下面的nonempty函数将在原有slice内存空间之上返回不包含空字符串的列表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// Nonempty is an example of an in-place slice algorithm.
package main

import "fmt"

// nonempty returns a slice holding only the non-empty strings.
// The underlying array is modified during the call.
func nonempty(strings []string) []string {
    i := 0
    for _, s := range strings {
        if s != "" {
            strings[i] = s
            i++
        }
    }
    return strings[:i]
}

比较微妙的地方是，输入的slice和输出的slice共享一个底层数组。

这可以避免分配另一个数组，不过原来的数据将可能会被覆盖，正如下面两个打印语句看到的那样：

1
2
3
data := []string{"one", "", "three"}
fmt.Printf("%q\n", nonempty(data)) // `["one" "three"]`
fmt.Printf("%q\n", data)           // `["one" "three" "three"]`

nonempty函数也可以使用append函数实现

1
2
3
4
5
6
7
8
9
func nonempty2(strings []string) []string {
    out := strings[:0] // zero-length slice of original
    for _, s := range strings {
        if s != "" {
            out = append(out, s)
        }
    }
    return out
}
  • 无论如何实现，以这种方式重用一个slice一般都要求最多为每个输入值产生一个输出值，事实上很多这类算法都是用来过滤或合并序列中相邻的元素。
  • 这种slice用法是比较复杂的技巧，虽然使用到了slice的一些技巧，但是对于某些场合是比较清晰和有效的。

用slice模拟stack

一个slice可以用来模拟一个stack。

最初给定的空slice对应一个空的stack，然后可以使用append函数将新的值压入stack

1
stack = append(stack, v) // push v

stack的顶部位置对应slice的最后一个元素：

1
top := stack[len(stack)-1] // top of stack

通过收缩stack可以弹出栈顶的元素

1
stack = stack[:len(stack)-1] // pop

删除slice中的元素

要删除slice中间的某个元素并保存原有的元素顺序，可以通过内置的copy函数将后面的子slice向前依次移动一位完成：

1
2
3
4
5
6
7
8
9
func remove(slice []int, i int) []int {
    copy(slice[i:], slice[i+1:])
    return slice[:len(slice)-1]
}

func main() {
    s := []int{5, 6, 7, 8, 9}
    fmt.Println(remove(s, 2)) // "[5 6 8 9]"
}

如果删除元素后不用保持原来顺序的话，我们可以简单的用最后一个元素覆盖被删除的元素：

1
2
3
4
5
6
7
8
9
func remove(slice []int, i int) []int {
    slice[i] = slice[len(slice)-1]
    return slice[:len(slice)-1]
}

func main() {
    s := []int{5, 6, 7, 8, 9}
    fmt.Println(remove(s, 2)) // "[5 6 9 8]
}

练习

练习 4.3： 重写reverse函数，使用数组指针代替slice。

练习 4.4： 编写一个rotate函数，通过一次循环完成旋转。

练习 4.5： 写一个函数在原地完成消除[]string中相邻重复的字符串的操作。

练习 4.6： 编写一个函数，原地将一个UTF-8编码的[]byte类型的slice中相邻的空格（参考unicode.IsSpace）替换成一个空格返回

练习 4.7： 修改reverse函数用于原地反转UTF-8编码的[]byte。是否可以不用分配额外的内存？

4.3. Map

  • 哈希表是一种巧妙并且实用的数据结构。
  • 它是一个无序的key/value对的集合，其中所有的key都是不同的，然后通过给定的key可以在常数时间复杂度内检索、更新或删除对应的value。
  • 在Go语言中，一个map就是一个哈希表的引用，map类型可以写为map[K]V，其中K和V分别对应key和value
  • map中所有的key都有相同的类型，所有的value也有着相同的类型，但是key和value之间可以是不同的数据类型
    • key必须是支持==比较运算符的数据类型、

创建一个Map

使用make函数
1
ages := make(map[string]int) // mapping from strings to ints
使用map字面量，可指定一些最初的key/value
1
2
3
4
5
6
7
8
9
ages := map[string]int{
    "alice":   31,
    "charlie": 34,
}

// 等价于
ages := make(map[string]int)
ages["alice"] = 31
ages["charlie"] = 34
另外一种创建方法
1
map[string]int{}

Map元素

访问
1
2
ages["alice"] = 32
fmt.Println(ages["alice"]) // "32"
删除
1
2
ages["alice"] = 32
fmt.Println(ages["alice"]) // "32"

  • 所有这些操作是安全的，即使这些元素不在map中也没有关系

  • 如果一个查找失败将返回value类型对应的零值

  • x += y和x++等简短赋值语法也可以用在map上

  • map中的元素并不是一个变量，因此我们不能对map的元素进行取址操作

1
_ = &ages["bob"] // compile error: cannot take address of map element

遍历map中所有元素

可以使用range风格的for循环（无序）
1
2
3
for name, age := range ages {
    fmt.Printf("%s\t%d\n", name, age)
}
  • Map的迭代顺序是不确定的，并且不同的哈希函数实现可能导致不同的遍历顺序。
  • 在实践中，遍历的顺序是随机的，每一次遍历的顺序都不相同。这是故意的，每次都使用随机的遍历顺序可以强制要求程序不会依赖具体的哈希函数实现。