Golang学习笔记之数据结构

[hackstoic]

数据结构

变量和常量

变量

Go 是静态类型语⾔，不能在运⾏期改变变量类型。 也就是说必须在使用时声明， 且使用过程赋值不对的话会报错。 比如给一个int类型的变量赋值一个字符串，就会报错。 var x int // 只定义不赋值， 默认系统赋值为0 var f float32 = 1.6 // 声明类型，并具体赋值 var s = "abc" // 不声明类型， 系统会自动判断 z := 5 // 用于定义新的局部变量或修改全局变量的值，不能修改局部变量的值! var （ m int n string ） // 定义多个变量， 注意这里时括号，不是花括号 var m, n, p int // 如果多个变量都是同种类型，可以使用这种方式简化定义 s, p = 0, "test" // 给多个变量赋值, 赋值时请先检查有没有定义，否则会报错 特殊变量： 用于忽略值，该变量 只写不可读 编译器会将未使⽤的局部变量当做错误。 var s string // 全局变量没问题。 func main() { i := 0 // Error: i declared and not used。(可使⽤ " = i" 规避) } 注意重新赋值与定义新同名变量的区别。 s := "abc" println(&s) s, y := "hello", 20 // 重新赋值: 与前 s 在同⼀层次的代码块中，且有新的变量被定义。 println(&s, y) // 通常函数多返回值 err 会被重复使⽤。 { s, z := 1000, 30 // 定义新同名变量: 不在同⼀层次代码块。 println(&s, z) } 输出： 0x2210230f30 0x2210230f30 20 0x2210230f18 30

在函数中， := 简洁赋值语句在明确类型的地方，可以用于替代 var 定义。

函数外的每个语句都必须以关键字开始（ var 、 func 、等等）， := 结构不能使用在函数外。

常量

const 常量值必须是编译期可确定的数字、字符串、布尔值

const x, y int = 1, 2 // 多常量初始化
const s = "Hello, World!" // 类型推断
const ( // 常量组
 a, b = 10, 100
 c bool = false
)
func main() {
 const x = "xxx" // 未使⽤局部常量不会引发编译错误。这个和变量有所不同
}

不⽀持 1UL、2LL 这样的类型后缀。 在常量组中，如不提供类型和初始化值，那么视作与上⼀常量相同。 const ( s = "abc" x // x = "abc" ) 常量值还可以是 len、cap、unsafe.Sizeof 等编译期可确定结果的函数返回值。 const ( a = "abc" b = len(a) c = unsafe.Sizeof(b) ) 如果常量类型⾜以存储初始化值，那么不会引发溢出错误 枚举 关键字 iota 定义常量组中从 0 开始按⾏计数的⾃增枚举值。 const ( Sunday = iota // 0 Monday // 1，通常省略后续⾏表达式。 Tuesday // 2 Wednesday // 3 Thursday // 4 Friday // 5 Saturday // 6 )

const ( _ = iota // iota = 0 KB int64 = 1 << (10 * iota) // iota = 1 MB // 与 KB 表达式相同，但 iota = 2 GB TB ) 在同⼀常量组中，可以提供多个 iota，它们各⾃增⻓。 const ( A, B = iota, iota << 10 // 0, 0 << 10 C, D // 1, 1 << 10 ) 如果 iota ⾃增被打断，须显式恢复。 const ( A = iota // 0 B // 1 C = "c" // c D // c，与上⼀⾏相同。 E = iota // 4，显式恢复。注意计数包含了 C、D 两⾏。 F // 5 ) 可通过⾃定义类型来实现枚举类型限制。

type Color int
const (
 Black Color = iota
 Red
 Blue
)
func test(c Color) {}
func main() {
 c := Black
 test(c)
 x := 1
 test(x) // Error: cannot use x (type int) as type Color in function argument
 test(1) // 常量会被编译器⾃动转换。
}

Tips：

1. 常量如果没有定义，默认和上一个定义同种类型
2. iota是golang中独有的关键字，是一种自增枚举类型

基本数据类型

更明确的数字类型命名，⽀持 Unicode，⽀持常⽤数据结构。

类型 |⻓度| 默认值 |说明
bool |1| false
byte |1| 0| uint8
rune |4 |0 |Unicode Code Point, int32
int, uint| 4 或 8| 0 |32 或 64 位
int8, uint8 |1 |0| -128 ~ 127, 0 ~ 255
int16, uint16| 2| 0 |-32768 ~ 32767, 0 ~ 65535
int32, uint32 |4| 0| -21亿 ~ 21 亿, 0 ~ 42 亿
int64, uint64| 8| 0
float32| 4 |0.0
float64| 8| 0.0
complex64| 8
complex128| 16
uintptr| 4 或 8| |⾜以存储指针的 uint32 或 uint64 整数
array|| |值类型
struct|| |值类型
string ||""| UTF-8 字符串
slice ||nil |引⽤类型
map|| nil |引⽤类型
channel ||nil |引⽤类型
interface ||nil |接⼝
function ||nil| 函数

⽀持⼋进制、⼗六进制，以及科学记数法。标准库 math 定义了各数字类型取值范围。 a, b, c, d := 071, 0x1F, 1e9, math.MinInt16 空指针值 nil，⽽⾮ C/C++ NULL。

Go 的在不同类型之间的项目赋值时需要显式转换, 比如

var i int = 42
var f float64 = float64(i)
var u uint = uint(f)

字符串类型

字符串是不可变值类型，内部⽤指针指向 UTF-8 字节数组。 • 默认值是空字符串 ""。 • ⽤索引号访问某字节，如 s[i]。 • 不能⽤序号获取字节元素指针，&s[i] ⾮法。 • 不可变类型，⽆法修改字节数组。 • 字节数组尾部不包含 NULL。 runtime.h struct String { byte* str; intgo len; }; 使⽤索引号访问字符 (byte)。 s := "abc" println(s[0] == '\x61', s[1] == 'b', s[2] == 0x63) 输出： true true true 使⽤ "" 定义不做转义处理的原始字符串，⽀持跨⾏。 s :=a b\r\n\x00 c` println(s) 输出: a b\r\n\x00 c

⽀持⽤两个索引号返回⼦串。⼦串依然指向原字节数组，仅修改了指针和⻓度属性。 s := "Hello, World!" s1 := s[:5] // Hello s2 := s[7:] // World! s3 := s[1:5] // ello

单引号字符常量表⽰ Unicode Code Point，⽀持 \uFFFF、\U7FFFFFFF、\xFF 格式。 对应 rune 类型，UCS-4。 func main() { fmt.Printf("%T\n", 'a') var c1, c2 rune = '\u6211', '们' println(c1 == '我', string(c2) == "\xe4\xbb\xac") } 输出： int32 // rune 是 int32 的别名 true true

要修改字符串，可先将其转换成 []rune 或 []byte，完成后再转换为 string。⽆论哪种转 换，都会重新分配内存，并复制字节数组。 func main() { s := "abcd" bs := []byte(s) bs[1] = 'B' println(string(bs)) u := "电脑" us := []rune(u) us[1] = '话' println(string(us)) } 输出: aBcd 电话 ⽤ for 循环遍历字符串时，也有 byte 和 rune 两种⽅式。 func main() { s := "abc汉字" for i := 0; i < len(s); i++ { // byte fmt.Printf("%c,", s[i]) } fmt.Println() for _, r := range s { // rune fmt.Printf("%c,", r) } } 输出： a,b,c,æ,±,,å,­,, a,b,c,汉,字,

结构体

时间日期类型

复杂数据类型

Array

和以往认知的数组有很⼤不同。 • 数组是值类型，赋值和传参会复制整个数组，⽽不是指针。 • 数组⻓度必须是常量，且是类型的组成部分。[2]int 和 [3]int 是不同类型。 • ⽀持 "=="、"!=" 操作符，因为内存总是被初始化过的。 • 指针数组 [n]T，数组指针 [n]T。 可⽤复合语句初始化

a := [3]int{1, 2} // 未初始化元素值为 0。
b := [...]int{1, 2, 3, 4} // 通过初始化值确定数组⻓度。
c := [5]int{2: 100, 4:200} // 使⽤索引号初始化元素。
d := [...]struct {
 name string
 age uint8
}{
 {"user1", 10}, // 可省略元素类型。
 {"user2", 20}, // 别忘了最后⼀⾏的逗号。
}

⽀持多维数组。

a := [2][3]int{{1, 2, 3}, {4, 5, 6}}
b := [...][2]int{{1, 1}, {2, 2}, {3, 3}} // 第 2 纬度不能⽤ "..."。

值拷⻉⾏为会造成性能问题，通常会建议使⽤ slice，或数组指针。

func test(x [2]int) {
 fmt.Printf("x: %p\n", &x)
 x[1] = 1000
}
func main() {
 a := [2]int{}
 fmt.Printf("a: %p\n", &a)
 test(a)
 fmt.Println(a)
}
// 输出：
a: 0x2101f9150
x: 0x2101f9170
[0 0]

内置函数 len 和 cap 都返回数组⻓度 (元素数量)。

a := [2]int{}
println(len(a), cap(a)) // 2, 2

Slice

需要说明，slice 并不是数组或数组指针。它通过内部指针和相关属性引⽤数组⽚段，以 实现变⻓⽅案。 runtime.h

struct Slice
{ // must not move anything
 byte* array; // actual data
 uintgo len; // number of elements
 uintgo cap; // allocated number of elements
};

引⽤类型。但⾃⾝是结构体，值拷⻉传递。 • 属性 len 表⽰可⽤元素数量，读写操作不能超过该限制。 • 属性 cap 表⽰最⼤扩张容量，不能超出数组限制。 • 如果 slice == nil，那么 len、cap 结果都等于 0。

data := [...]int{0, 1, 2, 3, 4, 5, 6}
slice := data[1:4:5] // [low : high : max]

创建表达式使⽤的是元素索引号，⽽⾮数量

data := [...]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}

|expression |slice | len| cap |comment|
data[:6:8] |[0 1 2 3 4 5]| 6|8 |省略 low.
data[5:] |[5 6 7 8 9]| 5 |5| 省略 high、max。
data[:3] |[0 1 2] |3 |10| 省略 low、max。
data[:] |[0 1 2 3 4 5 6 7 8 9] |10 |10| 全部省略。

读写操作实际⺫标是底层数组，只需注意索引号的差别。

data := [...]int{0, 1, 2, 3, 4, 5}
s := data[2:4]
s[0] += 100
s[1] += 200
fmt.Println(s)
fmt.Println(data)
//输出：
[102 203]
[0 1 102 203 4 5]

可直接创建 slice 对象，⾃动分配底层数组。

s1 := []int{0, 1, 2, 3, 8: 100} // 通过初始化表达式构造，可使⽤索引号。
fmt.Println(s1, len(s1), cap(s1))
s2 := make([]int, 6, 8) // 使⽤ make 创建，指定 len 和 cap 值。
fmt.Println(s2, len(s2), cap(s2))
s3 := make([]int, 6) // 省略 cap，相当于 cap = len。
fmt.Println(s3, len(s3), cap(s3))

//输出：
[0 1 2 3 0 0 0 0 100] 9 9
[0 0 0 0 0 0] 6 8
[0 0 0 0 0 0] 6 6

使⽤ make 动态创建 slice，避免了数组必须⽤常量做⻓度的⿇烦。还可⽤指针直接访问底层数组，退化成普通数组操作。

s := []int{0, 1, 2, 3}
p := &s[2] // *int, 获取底层数组元素指针。
*p += 100
fmt.Println(s)
//输出：
[0 1 102 3]

⾄于 [][]T，是指元素类型为 []T

data := [][]int{
 []int{1, 2, 3},
 []int{100, 200},
 []int{11, 22, 33, 44},
}

可直接修改 struct array/slice 成员。

d := [5]struct {
 x int
}{}
s := d[:]
d[1].x = 10
s[2].x = 20
fmt.Println(d)
fmt.Printf("%p, %p\n", &d, &d[0])
//输出:
[{0} {10} {20} {0} {0}]
0x20819c180, 0x20819c180

所谓 reslice，是基于已有 slice 创建新 slice 对象，以便在 cap 允许范围内调整属性。

s := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
s1 := s[2:5] // [2 3 4]
s2 := s1[2:6:7] // [4 5 6 7]
s3 := s2[3:6] // Error

data | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | +---+---+---+---+---+---+---+---+---+---+ 0 2 5 +---+---+---+---+---+---+---+---+ s1 | 2 | 3 | 4 | | | | | | len = 3, cap = 8 +---+---+---+---+---+---+---+---+ 0 2 6 7 +---+---+---+---+---+ s2 | 4 | 5 | 6 | 7 | | len = 4, cap = 5 +---+---+---+---+---+ 0 3 4 5 +---+---+---+ s3 | 7 | 8 | X | error: slice bounds out of range

新对象依旧指向原底层数组。

s := []int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
s1 := s[2:5] // [2 3 4]
s1[2] = 100
s2 := s1[2:6] // [100 5 6 7]
s2[3] = 200
fmt.Println(s)
//输出：
[0 1 2 3 100 5 6 200 8 9]

向 slice 尾部添加数据，返回新的 slice 对象。

s := make([]int, 0, 5)
fmt.Printf("%p\n", &s)
s2 := append(s, 1)
fmt.Printf("%p\n", &s2)
fmt.Println(s, s2)
//输出：
0x210230000
0x210230040
[] [1]

⼀旦超出原 slice.cap 限制，就会重新分配底层数组，即便原数组并未填满。

data := [...]int{0, 1, 2, 3, 4, 10: 0}
s := data[:2:3]
s = append(s, 100, 200) // ⼀次 append 两个值，超出 s.cap 限制。
fmt.Println(s, data) // 重新分配底层数组，与原数组⽆关。
fmt.Println(&s[0], &data[0]) // ⽐对底层数组起始指针。
//输出：
[0 1 100 200] [0 1 2 3 4 0 0 0 0 0 0]
0x20819c180 0x20817c0c0 

从输出结果可以看出，append 后的 s 重新分配了底层数组，并复制数据。如果只追加⼀个值，则不会超过 s.cap 限制，也就不会重新分配。 通常以 2 倍容量重新分配底层数组。在⼤批量添加数据时，建议⼀次性分配⾜够⼤的空间，以减少内存分配和数据复制开销。或初始化⾜够⻓的 len 属性，改⽤索引号进⾏操作。及时释放不再使⽤的 slice 对象，避免持有过期数组，造成 GC ⽆法回收。

s := make([]int, 0, 1)
c := cap(s)
for i := 0; i < 50; i++ {
 s = append(s, i)
 if n := cap(s); n > c {
 fmt.Printf("cap: %d -> %d\n", c, n)
 c = n
 }
}
输出:
cap: 1 -> 2
cap: 2 -> 4
cap: 4 -> 8
cap: 8 -> 16
cap: 16 -> 32
cap: 32 -> 64

函数 copy 在两个 slice 间复制数据，复制⻓度以 len ⼩的为准。两个 slice 可指向同⼀底层数组，允许元素区间重叠。

data := [...]int{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
s := data[8:]
s2 := data[:5]
copy(s2, s) // dst:s2, src:s
fmt.Println(s2)
fmt.Println(data)
//输出：
[8 9 2 3 4]
[8 9 2 3 4 5 6 7 8 9]

应及时将所需数据 copy 到较⼩的 slice，以便释放超⼤号底层数组内存。

Map

引⽤类型，哈希表。键必须是⽀持相等运算符 (==、!=) 类型，⽐如 number、string、 pointer、array、struct，以及对应的 interface。值可以是任意类型，没有限制。

m := map[int]struct {
 name string
 age int
}{
 1: {"user1", 10}, // 可省略元素类型。
 2: {"user2", 20},
}
println(m[1].name)

预先给 make 函数⼀个合理元素数量参数，有助于提升性能。因为事先申请⼀⼤块内存， 可避免后续操作时频繁扩张。

m := make(map[string]int, 1000)

常⻅操作：

m := map[string]int{
 "a": 1,
}
if v, ok := m["a"]; ok { // 判断 key 是否存在。
 println(v)
}
println(m["c"]) // 对于不存在的 key，直接返回 \0，不会出错。
m["b"] = 2 // 新增或修改。
delete(m, "c") // 删除。如果 key 不存在，不会出错。
println(len(m)) // 获取键值对数量。cap ⽆效。
for k, v := range m { // 迭代，可仅返回 key。随机顺序返回，每次都不相同。
 println(k, v)
}

不能保证迭代返回次序，通常是随机结果，具体和版本实现有关。 从 map 中取回的是⼀个 value 临时复制品，对其成员的修改是没有任何意义的。

type user struct{ name string }
m := map[int]user{ // 当 map 因扩张⽽重新哈希时，各键值项存储位置都会发⽣改变。 因此，map
 1: {"user1"}, // 被设计成 not addressable。 类似 m[1].name 这种期望透过原 value
} // 指针修改成员的⾏为⾃然会被禁⽌。
m[1].name = "Tom" // Error: cannot assign to m[1].name

正确做法是完整替换 value 或使⽤指针。

u := m[1]
u.name = "Tom"
m[1] = u // 替换 value。
m2 := map[int]*user{
 1: &user{"user1"},
}
m2[1].name = "Jack" // 返回的是指针复制品。透过指针修改原对象是允许的。

可以在迭代时安全删除键值。但如果期间有新增操作，那么就不知道会有什么意外了。

for i := 0; i < 5; i++ {
 m := map[int]string{
 0: "a", 1: "a", 2: "a", 3: "a", 4: "a",
 5: "a", 6: "a", 7: "a", 8: "a", 9: "a",
 }
 for k := range m {
 m[k+k] = "x"
 delete(m, k)
 }
 fmt.Println(m)
}
//输出：
map[12:x 16:x 2:x 6:x 10:x 14:x 18:x]
map[12:x 16:x 20:x 28:x 36:x]
map[12:x 16:x 2:x 6:x 10:x 14:x 18:x]
map[12:x 16:x 2:x 6:x 10:x 14:x 18:x]
map[12:x 16:x 20:x 28:x 36:x]

Struct

值类型，赋值和传参会复制全部内容。可⽤ "_" 定义补位字段，⽀持指向⾃⾝类型的指针 成员。

type Node struct {
 _ int
 id int
 data *byte
 next *Node
}
func main() {
 n1 := Node{
 id: 1, 
 data: nil,
 }
 n2 := Node{
 id: 2,
 data: nil,
 next: &n1,
 }
}

顺序初始化必须包含全部字段，否则会出错。

type User struct {
 name string
 age int
}
u1 := User{"Tom", 20}
u2 := User{"Tom"} // Error: too few values in struct initializer

⽀持匿名结构，可⽤作结构成员或定义变量

type File struct {
 name string
 size int
 attr struct {
 perm int
 owner int
 }
}
f := File{
 name: "test.txt",
 size: 1025,
 // attr: {0755, 1}, // Error: missing type in composite literal
}
f.attr.owner = 1
f.attr.perm = 0755
var attr = struct {
 perm int
 owner int
}{2, 0755}
f.attr = attr

⽀持 "=="、"!=" 相等操作符，可⽤作 map 键类型。

type User struct {
 id int
 name string
}
m := map[User]int{
 User{1, "Tom"}: 100,
}

注： 在go语言中只要支持 ＝＝， ！＝操作符的数据结构， 就可以用做map的key， 这个比python语言更加灵活

可定义字段标签，⽤反射读取。标签是类型的组成部分。

var u1 struct { name string "username" }
var u2 struct { name string }
u2 = u1 // Error: cannot use u1 (type struct { name string "username" }) as
 // type struct { name string } in assignment

空结构 "节省" 内存，⽐如⽤来实现 set 数据结构，或者实现没有 "状态" 只有⽅法的 "静 态类"。

var null struct{}
set := make(map[string]struct{})
set["a"] = null

匿名字段不过是⼀种语法糖，从根本上说，就是⼀个与成员类型同名 (不含包名) 的字段。 被匿名嵌⼊的可以是任何类型，当然也包括指针。

type User struct {
 name string
}
type Manager struct {
 User
 title string
}
m := Manager{
 User: User{"Tom"}, // 匿名字段的显式字段名，和类型名相同。
 title: "Administrator",
}

可以像普通字段那样访问匿名字段成员，编译器从外向内逐级查找所有层次的匿名字段， 直到发现目标或出错。

type Resource struct {
 id int
}
type User struct {
 Resource
 name string
}
type Manager struct {
 User
 title string
}
var m Manager
m.id = 1
m.name = "Jack"
m.title = "Administrator"

外层同名字段会遮蔽嵌⼊字段成员，相同层次的同名字段也会让编译器⽆所适从。解决⽅ 法是使⽤显式字段名。

type Resource struct {
 id int
 name string
}
type Classify struct {
 id int
}
type User struct {
 Resource // Resource.id 与 Classify.id 处于同⼀层次。
 Classify
 name string // 遮蔽 Resource.name。
}
u := User{ 
Resource{1, "people"},
 Classify{100},
 "Jack",
}
println(u.name) // User.name: Jack
println(u.Resource.name) // people
// println(u.id) // Error: ambiguous selector u.id
println(u.Classify.id) // 100

不能同时嵌⼊某⼀类型和其指针类型，因为它们名字相同。

type Resource struct {
 id int
}
type User struct {
 *Resource
 // Resource // Error: duplicate field Resource
 name string
}
u := User{
 &Resource{1},
 "Administrator",
}
println(u.id)
println(u.Resource.id)

⾯向对象三⼤特征⾥，Go 仅⽀持封装，尽管匿名字段的内存布局和⾏为类似继承。没有 class 关键字，没有继承、多态等等。

type User struct {
 id int
 name string
}
type Manager struct {
 User
 title string
 }
m := Manager{User{1, "Tom"}, "Administrator"}
// var u User = m // Error: cannot use m (type Manager) as type User in assignment
 // 没有继承，⾃然也不会有多态。
var u User = m.User // 同类型拷⻉。

内存布局和 C struct 相同，没有任何附加的 object 信息。

 可⽤ unsafe 包相关函数输出内存地址信息。 m : 0x2102271b0, size: 40, align: 8 m.id : 0x2102271b0, offset: 0 m.name : 0x2102271b8, offset: 8 m.title: 0x2102271c8, offset: 24

不可变数据