一、数组

数组是由相同类型元素的集合组成的数据结构，计算机会为数组分配一块连续的内存来保存其中的元素，我们可以利用数组中元素的索引快速访问特定元素。

1.1 初始化

初始化数据组时需要指定数组的长度、类型。

arr1 := [3]int{1, 2, 3}
arr2 := [...]int{1, 2, 3}

上限推导

使用 [...]T 的形式初始化时，程序编译时会对数组的大小进行推导。

语句转换

当元素数量 >=4 时，会直接将数组元素放置在栈上，反之会将元素放置到静态区并在运行时取出。

1.2 访问和赋值

无论是在栈上还是静态存储区，数组在内存中都是一连串的内存空间，我们通过指向数组开头的指针、元素的数量以及元素类型占的空间大小表示数组。

arr := [3]int{1, 2, 3}
// 访问
fmt.PrintLn(arr[0])

// 赋值
arr[0] = 10

1.3 总结

数组是 Go 语言中重要的数据结构，我们要避免出现下标越界的情况。

二、切片

在 Go 语言中，切片类型的声明方式与数组有一些相似，不过由于切片的长度是动态的。

2.1 基本结构

Data 是指向数组的指针;
Len 是当前切片的长度；
Cap 是当前切片的容量，即 Data 数组的大小

type SliceHeader struct {
	Data uintptr
	Len  int
	Cap  int
}

Data 是一片连续的内存空间，这片内存空间可以用于存储切片中的全部元素，数组中的元素只是逻辑上的概念，底层存储其实都是连续的，所以我们可以将切片理解成一片连续的内存空间加上长度与容量的标识。

2.1 初始化

由于切片的长度是动态的，所以声明时只需要指定切片中的元素类型。初始化切片有三种方式：
1、通过下标的方式获得数组或者切片的一部分；
2、使用字面量初始化新的切片；
3、使用关键字 make 创建切片：

// 通过下标的方式获得数组或者切片的一部分
arr[0:3] or slice[0:3]

// 使用字面量初始化新的切片
slice := []int{1, 2, 3}

// 使用关键字 make 创建切片
slice := make([]int, 10)

2.2 访问和赋值

可以使用 len 和 cap 来获取切片的长度和容量，而访问和赋值与数组的操作类似：

arr := [3]int{1, 2, 3}
// 访问
fmt.PrintLn(arr[0])

// 赋值
arr[0] = 10

2.3 追加和扩容

使用 append 来追加元素：

func main() {
	arr := []int{1, 2, 3}
	fmt.Println(arr)
	arr = append(arr, 4, 5, 6)
	arr = append(arr, []int{7, 8, 9}...)
	fmt.Println(arr)
}

扩容规则

当追加元素时，切片容量不足时就会触发扩容。具体扩容规则为：
1、如果期望容量大于当前容量的两倍就会使用期望容量；
2、如果当前切片的长度小于 1024 就会将容量翻倍；
3、如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

2.4 切片拷贝

切片拷贝使用的是 copy，copy 是属于深拷贝。

三、哈希表

哈希是除了数组之外，最常见的数据结构。几乎所有的语言都会有数组和哈希表两种集合元素，有的语言将数组实现成列表，而有的语言将哈希称作字典或者映射。

3.1 数据结构

type hmap struct {
	count     int
	flags     uint8
	B         uint8
	noverflow uint16
	hash0     uint32

	buckets    unsafe.Pointer
	oldbuckets unsafe.Pointer
	nevacuate  uintptr

	extra *mapextra
}

type mapextra struct {
	overflow    *[]*bmap
	oldoverflow *[]*bmap
	nextOverflow *bmap
}

count 哈希表中的元素数量；
B 表示 buckets 数量；
hash0 是哈希种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入；
oldbuckets 扩容时用于保存之前的 buckets，大小为当前 buckets 的一半。

buckets 是一个 bmap 数组，其结构如下：

type bmap struct {
    topbits  [8]uint8
    keys     [8]keytype
    values   [8]valuetype
    pad      uintptr
    overflow uintptr
}

这个 bmap 也就是桶，每个桶的数据不会超过 8 个，超过的会被放到溢出桶，注意过多的溢出桶也会导致 哈希扩容。

3.2 初始化

hash := map[string]int{
	"1": 2,
	"3": 4,
	"5": 6,
}

// 编译时会自动转换为下面这种形式
hash := make(map[string]int, 3)
hash["1"] = 2
hash["3"] = 4
hash["5"] = 6

3.3 读写操作

常见的访问形式是通过下标访问或者遍历：

_ = hash[key]

for k, v := range hash {
    // k, v
}

数据结构的写一般指的都是增加、删除和修改，增加和修改字段都使用索引和赋值语句，而删除字典中的数据需要使用关键字 delete:

hash[key] = value
hash[key] = newValue
delete(hash, key)

访问

访问哈希中的元素都是通过索引的方式，例如：

v     := hash[key] 
v, ok := hash[key]

第一个参数表示接收的目标值，第二个参数用于判断索引是否存在。

写入

hash := map[string]string{}
hash["name"] = "stan"

写入原理：
1、首先根据传入的键通过函数计算出对应的哈希值和对应的桶
2、然后依次比较桶中（包括溢出桶）存储的 tophash 和 键的哈希值（若键已经存在，就直接返回目标位置，即键和值对应数组中的下标索引）
3、新插入的键时桶已经满了就会创建新的溢出桶或者使用已经创建好的溢出桶来保存数据（放在已有桶的末尾），同时增加 noverflow 计数器。
4、若插入的键不存在时需要规划内存地址，将键移动到内存空间，并访问其对应值的地址；若已存在时，会直接访问目标的内存地址，并将值拷贝到桶中。
5、哈希表容量不足时将会触发扩容

扩容规则

随着哈希表中元素的逐渐增加，哈希的性能会逐渐恶化，所以我们需要更多的桶和更大的内存保证哈希的读写性能，扩容的情况：
1、装载因子超过 6.5
2、哈希使用太多溢出桶

扩容方式
根据触发的条件不同可以将扩容分为等量扩容和翻倍扩容。
因为溢出桶太多导致的扩容就是等量扩容（sameSizeGrow），其目的就是防止过多的溢出桶导致内存泄漏，通过复用已有的哈希扩容机制解决该问题。

大致流程：先创建一组新桶和预创建的溢出桶，随后将原有的桶数组设置到 oldbuckets 上并将新的空桶设置到 buckets 上，溢出桶也使用了相同的逻辑更新。

数据的迁移是在 runtime.evacuate 中完成的，它会将旧桶中的数据分流到新桶中去，通过 runtime.evacDst 来保存分流的上下文数据。等量扩容时仅会初始化一个 runtime.evacDst，而翻倍扩容需要初始化两个 runtime.evacDst，例如：

当旧桶中的所有数据被分流后，将清空旧桶和旧的溢出桶。

删除

若要删除哈希表中的元素要使用 delete 关键字，这个关键字的唯一作用就是将某一个键对应的元素从哈希表中删除，无论是该键对应的值是否存在，这个内建的函数都不会返回任何的结果。

3.4 总结

哈希表在存储元素过多时会触发扩容操作，每次都会将桶的数量翻倍，扩容过程不是原子的，而是通过 runtime.growWork 增量触发的，扩容期间访问哈希表时会使用旧桶，向哈希表写入数据时会触发旧桶元素的分流。为了解决大量写入和删除造成内存泄漏问题，还引入了 sameSizeGrow 等量扩容机制，当出现较多的溢出桶时会整理哈希的内存减少空间的占用。

四、字符串

字符串是 Go 语言中的基础数据类型，虽然字符串往往被看做一个整体，但是它实际上是一片连续的内存空间，我们也可以将它理解成一个由字符组成的数组。

Go 程序编译时，遇到字符串代码时会通过 SRODATA 将其标记为只读数据。

只读只意味着字符串会分配到只读的内存空间，但是 Go 语言只是不支持直接修改 string 类型变量的内存空间，我们仍然可以通过在 string 和 []byte 类型之间反复转换实现修改这一目的。

4.1 数据结构

与切片的结构体相比，字符串只少了一个表示容量的 Cap 字段，而正是因为切片在 Go 语言的运行时表示与字符串高度相似，所以我们经常会说字符串是一个只读的切片类型。

type StringHeader struct {
	Data uintptr
	Len  int
}

因为字符串作为只读的类型，我们并不会直接向字符串直接追加元素改变其本身的内存空间，所有在字符串上的写入操作都是通过拷贝实现的。

4.2 拼接和拷贝

Go 语言拼接字符串使用 + 符号，拷贝时使用 copy 将多个字符串拷贝到目标字符串的内存空间。新的字符串是一片新的内存空间，与原来的字符串也没有任何关联，一旦需要拼接的字符串非常大，拷贝带来的性能损失是无法忽略的。

4.3 类型转换

Go 语言解析和序列化 JSON 等数据格式时，经常需要将数据在 string 和 []byte 之间来回转换，类型转换的开销并没有想象的那么小。

4.4 总结

字符串是 Go 语言中相对来说比较简单的一种数据结构，我们在这一节中详细分析了字符串与 []byte 类型的关系，从词法分析阶段理解字符串是如何被解析的，作为只读的数据类型，我们无法改变其本身的结构，但是在做拼接和类型转换等操作时一定要注意性能的损耗，遇到需要极致性能的场景一定要尽量减少类型转换的次数。

附录

参考原文《Go语言设计与实现》