golang数据结构(数组、切片、map)

doc

golang

部分翻译自官方文档：

https://blog.golang.org/go-maps-in-action

https://blog.golang.org/slices

https://blog.golang.org/strings (新开补充)

1 数据类型概览

布尔型
- true or false
数字类型
- 整数int
- 浮点型 float32、float64
字符串类型
- go的字符串是由单个字节连接起来的
派生类型
- 数组
- 结构体
- Channel类型
- 函数类型
- 切片类型
- 接口类型
- Map类型

2 数组

数组作为存储集合数据的类型，使用场景非常多。golang的数组实现和其他语言的数组实现差别不大，通过利用一段连续的内存空间，切割成一个个的元素，每个元素按照顺序进行索引。

2.1 声明和初始化

数组的声明方式需要明确如下：

存储的数据类型，比如说int string，也可以是自定义的结构体
存储元素的数量

var test_array [5]int           //声明了一个长度为5的int型数组。
test_array = [5]int{1,2,3,4,5}  //初始化数组

当然golang中的 :=也可以直接用上，来代替上述两句，更加简洁

当我们不想指定长度时，可以采用如下方式定义数组，go会自动推导出数组长度。 test_array := [...]int{1,2,3,4,5}

当初始化时只想给部分索引值赋值的情况，可以采用如下方式定义数组。 test_array := [...]int{1:1,2:3}

2.2 数组的使用

// 取值
test_array[1]
// 修改值
test_array[1] = 10
// 循环方式1
for i := 0; i < 5; i++ {
	fmt.Printf("索引:%d,值:%d\n", i, test_array[i])
}
// 循环方式2
for i, v := range array {
	fmt.Printf("索引:%d,值:%d\n", i, v)
}
// 数组赋值
array := [5]int{1,2,3,4,5}
var array1 [5]int = array //成功
var array2 [4]int = array1 //报错
// 指针数组
array := [5]*int{1: new(int), 3:new(int)}
*array[1] = 1 // 成功
*array[2] = 1 // 报错

2.3 函数间传递数组

go语言在函数间传递变量时，总是以值的形式，而非一个指针。一个数组变量就代表了全数组。

如果数组长度极大的情况下，以数组名作为变量传递，对于内存的消耗非常严重，这种情况下，需要传递数组指针&array，但是传递数组指针的话，会存在改变原数组的情况，代码需要谨慎。

3 切片

切片可以理解为动态数组，定义和使用上更为灵活。

本质上是一个很小的对象，对数组进行了抽象，并提供相关的操作方法。

切片有三个属性字段：长度、容量和指向数组的指针。

3.1 声明和初始化

首先说明下，切片的容量是指对应底层数组的长度。长度是指切片实际存放的长度。

切片的声明和初始化有很多种方式，以代码的形式列举一下。

slice := make([]int,5) // 创建容量和长度均为5的整型切片
slice := make([]int,5,10)  // 创建容量为10，长度为5的整型切片
slice := []int{1,2,3,4,5} // 创建容量和长度均为5的整型切片
slice := []int{4:1} // 创建容量和长度均为5的整型切片，第4个下标值为1

切片也支持基于现有切片进行截取，新切片和老切片共用的是一套底层数据，当新切片或者老切片任意一个改变内容值时，整个数据都会随同变更。

3.2 切片的使用

append函数会智能的增长底层数组的容量，目前的算法是：容量小于1000个时，总是成倍的增长，一旦容量超过1000个，增长因子设为1.25，也就是说每次会增加25%的容量。

slice := []int{1, 2, 3, 4, 5}
newSlice := slice[1:3]
	
newSlice=append(newSlice,10) // 添加数字
newSlice=append(newSlice,slice...) // 添加一个切片

// 循环切片
for i,v:=range slice{
	fmt.Printf("索引:%d,值:%d\n",i,v)
}
for i := 0; i < len(slice); i++ {
	fmt.Printf("值:%d\n", slice[i])
}

3.3 函数间传递切片

切片本质上是3个字段构成的结构体类型，所以在函数间以值的方式传递的时候，占用的内存非常小，成本很低。在传递复制切片的时候，其底层数组不会被复制，也不会受影响，复制只是复制的切片本身，不涉及底层数组。

4 字典

4.1 简介

hash结构作为计算机科学界最有用的数据结构之一，提供了易于查找、添加和删除的特性。go也提供了内置的map类型。

4.2 声明和初始化

一个go的map类型格式如下：

map[KeyType]ValueType

其中KeyType可以是任意类型，ValueType也可以是任意类型，甚至可以包括其余map

定义一个key为字符串、value为整型的map如下：

var m map[string]int

Map类型属于引用类型，类似切片和指针。上面m的值为nil，它并不指向一个初始化好的map。当我们尝试去对一个nil形式的map进行赋值时，会引起程序报错。所以必须在声明后进行初始化。

利用make函数进行map初始化如下：

m = make(map[string]int)

make函数分配并初始化一个hash结构并且返回指向其的map值。该数据结构的实现属于一个运行时的通用实现，和语言本身无关。本篇会重点讲解他的使用层面。

4.4 map的使用

// 赋值
m["route"] = 66
i := m["route"]
j := m["root"]
// 长度
n := len(m)
// 删除指定key
delete(m, "route")
// 获取指定key的value ok标识是否存在
i, ok := m["route"]
_, ok := m["route"]
// map循环
for key, value := range m {
    fmt.Println("Key:", key, "Value:", value)
}
// 初始化map
commits := map[string]int{
    "rsc": 3711,
    "r":   2138,
    "gri": 1908,
    "adg": 912,
}
// 初始化空map
m = map[string]int{}

4.5 善用零值

当map中的key不存在时会返回0值，等同于false

举个例子，一个value为布尔值的map等同于一个set集合，我们利用他的key为一个链表并打印出其值。使用这样的map形式可以实现检测list中是否有环。

type Node struct {
        Next  *Node
        Value interface{}
}
var first *Node

visited := make(map[*Node]bool)
for n := first; n != nil; n = n.Next {
	if visited[n] {
		fmt.Println("cycle detected")
		break
	}
	visited[n] = true
	fmt.Println(n.Value)
}

这里的表达式visited[n]如果为true，则表示已经被访问过了，如果为false则表示还未被访问。

再举一个应用场景，我们有一个自定义的struct，Person，里面存了人的名字和他／她的爱好，现在我们要写一个简单的小程序，把所有的people（人员）按照相同兴趣进行分类

type Person struct {
        Name  string
        Likes []string
    }
    var people []*Person

    likes := make(map[string][]*Person)
    for _, p := range people {
        for _, l := range p.Likes {
            likes[l] = append(likes[l], p)
        }
    }

利用两个go里的特征， 1, range对于非nil的map，可以进行遍历，但是如果是nil的map（也就是没有初始化的map），默认按照空的map处理，也就是不运行for循环的逻辑代码 2, append支持非nil和nil 的map，都能进行成功的append。这样，就能简化代码

打印喜欢cheese的人如下代码：

for _, p := range likes["cheese"] {
	fmt.Println(p.Name, "likes cheese.")
}

4.6 key的类型

key的类型可以是任何可比较的类型。简而言之，可比较的类型包括：

布尔值、数字类型、字符串、指针、通道、接口类型、以及包含这些类型的结构体和数组类型。重点需要关注的是，这些类型里不包括切片、map和函数，原因是这些类型无法用==来进行比较。

使用键类型为结构体的map示例如下：

type Key struct {
    Path, Country string
}
hits := make(map[Key]int)

4.7 并发

map是非线程安全的。没有明确的定义出当你同时读写是会有什么情况。当你通过多个goroutines进行map的读取和写入时，必须引入一些同步机制进行协调。一种常见的做法是使用sync.RWMutex。

下面的语句定义了一个计数器变量，它是包含了map和嵌入sync.RWMutex的匿名结构体。

var counter = struct{
    sync.RWMutex
    m map[string]int
}{m: make(map[string]int)}

从该计数器读取数据时，加上read lock如下：

counter.RLock()
n := counter.m["some_key"]
counter.RUnlock()
fmt.Println("some_key:", n)

向该计数器写入数据时，加上write lock如下：

counter.Lock()
counter.m["some_key"]++
counter.Unlock()

4.8 迭代顺序

When iterating over a map with a range loop, the iteration order is not specified and is not guaranteed to be the same from one iteration to the next.

当我们遍历map时，顺序是随机的。从Go 1.0版本开始，运行时态就已经将map的顺序置为随机态了。

当我们需要有序的key时，需要通过一个单独的数据结构来进行维护。

举例如下：

import "sort"

var m map[int]string
var keys []int
for k := range m {
    keys = append(keys, k)
}
sort.Ints(keys)
for _, k := range keys {
    fmt.Println("Key:", k, "Value:", m[k])
}