go底层数据结构原理

数组

数组是一个定长的顺序表，内存上元素地址是连续的。

• 初始化（不考虑逃逸分析）

  初始化有两种方式：[...]{1,2,3,4}或[4]{1,2,3,4}。这两种方式初始化的方式仅仅只是语法糖而已，在SSA中间代码生成的时候，其实是一样的处理逻辑。

  1. 数组元素个数<=4个时，那么数组就会直接在栈上分配；
  2. 数组元素个数>4个时，那么就会在静态存储区初始化，然后拷贝回栈中；

• 访问和赋值

  不论是访问操作还是赋值操作，首先就是确定索引。

  对于常量索引，代码编译期间就可以判定是否越界；而对于变量索引，需要在运行时中插入检测函数检测是否越界。通过这两种方式，可以保证数组访问不会越界，一旦越界会报错。

切片

切片相比数组，具备自扩容特点，不同的是切片是在数组之上进一步封装。在运行时中的结构如下：

1
2
3
4
5

type SliceHeader struct {
	Data uintptr // 指向底层数组的指针
	Len  int // 当前切片长度
	Cap  int // 切片的容量，也就是底层数组大小
}

• 切片的特点：

  1. 封装：这样封装之后，底层数组的扩容、缩容等操作对于上层可以做到无感，也就是上层不需要关心扩容缩容的问题，由切片来实现。

  2. 运行时确定：与数组不同，是在编译期间就决定好结构了，读写位置是在编译期间就固定的；但是切片在运行时可能由于先前分配的容量不够，触发切片底层数组扩缩容，结构会发生改变。

• 初始化

  初始化有三种方式：

  1 2 3 4 5 6 7 8 9 10

  // 通过下标的方式获得数组或者切片的一部分； arr := [3]int{1, 2, 3} slice := arr[:] // 使用字面量初始化新的切片； slice:=[]int{1, 2, 3} // 使用关键字 make 创建切片： slice:=make([]int,3) slice[0]=1 slice[1]=2 slice[2]=3

  1. 其中第二种初始化方式在编译期间都会被展开成arr[:]和方式一一样的处理逻辑；
  2. 如果是第三种初始化方式，会在运行时对传入参数进行进一步检查和操作
     • 是否cap>=len
     • 切片如果发生了逃逸或者需要的内存过大，就在堆上进行分配
     • 切片如果没有发生逃逸或者需要的内存较小，make函数会在编译阶段变成和前面两种方式一样地处理逻辑，也就是分配到栈上。

• 访问元素

  1. 获取len、cap和访问切片中的元素

     len(slice) 或者 cap(slice) 在一些情况下会直接替换成切片的长度或者容量，不需要在运行时获取；除了获取切片的长度和容量之外，访问切片中元素使用的 OINDEX 操作也会在SSA中间代码生成期间转换成对地址的直接访问

  2. range切片也会被转化成更简单的for循环

• 追加和扩容

  1. 追加

     append有两种方式：一种是覆盖原变量slice=append(slice,1,2,3)，另一种是不覆盖回原变量append(slice,1,2,3)。

     后者如果底层数组发生扩容，那么slice指向就会失效了.

     如果我们选择覆盖原有的变量，就不需要担心切片发生拷贝影响性能，因为 Go 语言编译器已经对这种常见的情况做出了优化。

  2. 扩容

     在分配内存空间之前需要先确定新的切片容量，运行时根据切片的当前容量选择不同的策略进行扩容：

     1. 如果期望容量大于当前容量的两倍就会使用期望容量；

     2. 如果当前切片的长度小于 1024 就会将容量翻倍；

     3. 如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

        上述代码片段仅会确定切片的大致容量，下面还需要根据切片中的元素大小对齐内存，当数组中元素所占的字节大小为 1、8 或者 2 的倍数时，运行时会使用如下所示的代码对齐内存

  尽量避免大切片的扩容或复制时发生的大规模内存拷贝。

哈希表

哈希表是一种数据结构，具备O(1)级别的读写性能。但是设计一个优秀的哈希表，需要解决两个关键点：哈希冲突和哈希函数。

• 初始化

  两种初始化方式：字面量map[string]int{"1":11}和make(map[string]int,1)

  这两种初始化方式仅仅只是语法糖，最后都会转化为对runtime.makemap调用，这个函数主要干了：

  1. 计算哈希占用的内存是否溢出或者超出能分配的最大值；
  2. 调用 runtime.fastrand 获取一个随机的哈希种子；
  3. 根据传入的 hint 计算出需要的最小需要的桶的数量；
  4. 使用 runtime.makeBucketArray 创建用于保存桶的数组；
     • 当桶的数量小于 2^4^ 时，由于数据较少、使用溢出桶的可能性较低，会省略创建的过程以减少额外开销；
     • 当桶的数量多于 2^4^ 时，会额外创建 2^B^−2^4^ 个溢出桶；

• 读操作

  两种方式：读操作返回一个参数v:=map[k]；读操作返回两个参数v,ok:=map[k]。底层实现上，一个是调用了runtime.mapaccess1，而另一个是调用了runtime.mapaccess2，这两个函数的实现差不多，只是后者多了个bool返回值。

  1. 先通过哈希表设置的哈希函数和哈希种子获取当前key的哈希值；
  2. 然后再拿到桶的序号和哈希的高8位数字；（哈希高8位数字是用来和桶中的tophash比较和快速定位桶中key的地址的）
  3. 依次遍历桶中的8个tophash，如果找到tophash与key哈希后的高8位数字相等，然后就直接指针偏移到对应的key[i]并与key比较，如果相等就再偏移拿到value[i]并返回。
  4. 桶中没有，会去溢出桶里找

• 写操作

  1. 首先还是先拿到key的哈希值和桶；
  2. 然后再比较桶中的存储的 tophash和key的哈希高8位，如果相同就会直接返回目标位置的地址；
  3. 如果在桶中没找到，就去单链表结构的溢出桶里继续寻找，如果有就返回value地址；
  4. 如果还没有找到key，就会为新的键值对规划存储的内存地址，并返回value的地址；
  5. 而后续的写入是由编译期间插入的汇编代码执行的。

• 哈希扩容

  随着哈希元素的逐渐增多，特别是溢出桶的增加（溢出桶的遍历复杂度是O(n)级别的），哈希性能会逐渐恶化，我们需要扩容。扩容的条件是：

  1. 装载因子已经超过 6.5；

     这个条件引起的扩容触发的是翻倍扩容，增加桶容量。扩容是增量触发的的，并不是一次性完成的。而且扩容期间读操作会使用旧桶的数据；写操作才会触发旧桶的分流。这样可以摊销掉扩容的时间复杂度。

  2. 哈希使用了太多溢出桶；

     由这个条件引起的扩容是等量扩容sameSizeGrow：如果出现太多溢出桶，它会创建数量和旧桶一样数量的新桶保存数据，然后垃圾回收会清理老的溢出桶并释放内存。

• 删除操作

  哈希表的删除逻辑与写入逻辑很相似，只是触发哈希的删除需要使用关键字，如果在删除期间遇到了哈希表的扩容，就会分流桶中的元素，分流结束之后会找到桶中的目标元素完成键值对的删除工作。

Go 语言使用拉链法来解决哈希碰撞的问题实现了哈希表，它的访问、写入和删除等操作都在编译期间转换成了运行时的函数或者方法。哈希在每一个桶中存储键对应哈希的前 8 位，当对哈希进行操作时，这些 tophash 就成为可以帮助哈希快速遍历桶中元素的缓存。

哈希表的每个桶都只能存储 8 个键值对，一旦当前哈希的某个桶超出 8 个，新的键值对就会存储到哈希的溢出桶中。随着键值对数量的增加，溢出桶的数量和哈希的装载因子也会逐渐升高，超过一定范围就会触发扩容，扩容会将桶的数量翻倍，元素再分配的过程也是在调用写操作时增量进行的，不会造成性能的瞬时巨大抖动。

字符串

go语言字符串底层实现就是一个只读的数组结构[n]byte。字符串可以被索引，但是不能被直接修改。

• 数据结构

  1 2 3 4

  type StringHeader struct { Data uintptr // 底层数组指针 Len int // 底层数组大小 }

• 字符串拼接

  1. +

     性能最差的拼接方式。由于go语言字符串是只读数据结构，拼接字符串会将字符串重新拷贝分配到新的地址上。所以+会造成字符串的大量拷贝。

  2. fmt.Sprintf

     使用反射，也会涉及到拷贝，性能较差

  3. strings.Builder

     底层切片有复用机制，而且转化为字符串时，使用了零拷贝机制。

  4. strings.Bytes

     还行

• 类型转化

  某些场景下，我们需要将string和[]byte互相转化，如果对于原结构不做任何改变的话，可以考虑使用unsafe

接口

接口也是 Go 语言中的一种类型，它能够出现在变量的定义、函数的入参和返回值中并对它们进行约束，不过 Go 语言中有两种略微不同的接口，一种是带有一组方法的接口，另一种是不带任何方法的 interface{}：Go 语言使用 runtime.iface 表示第一种接口，使用 runtime.eface 表示第二种不包含任何方法的接口 interface{}

值得注意的是：接口不是任意类型，接口也是一种类型。

• 接口零值

  接口的零值是指类型和值都要为nil才表示零值。如：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

  package main type TestStruct struct{} func NilOrNot(v interface{}) bool { return v == nil } func main() { var s *TestStruct fmt.Println(s == nil) // #=> true fmt.Println(NilOrNot(s)) // #=> false } $ go run main.go true false

• 数据结构

  1 2 3 4 5 6 7 8 9 10 11 12 13 14

  // 运行时的类型结构 type _type struct { size uintptr ptrdata uintptr hash uint32 // 快速判断类型是否相等 tflag tflag align uint8 fieldAlign uint8 kind uint8 equal func(unsafe.Pointer, unsafe.Pointer) bool gcdata *byte str nameOff ptrToThis typeOff }

  1. 空接口

     1 2 3 4

     type eface struct { // 16 字节 _type *_type // 指向底层数据类型：类型大小、hash、对齐等 data unsafe.Pointer // 指向数据的指针 }

  2. 非空接口

     1 2 3 4 5 6 7 8 9 10 11 12

     type iface struct { // 16 字节 tab *itab data unsafe.Pointer // 指向数据 } type itab struct { // 32 字节 inter *interfacetype // 指向接口类型 _type *_type // 指向真实数据类型 hash uint32 // 对_type字段中hash的拷贝，可以减少指针解引用的开销 _ [4]byte // pad fun [1]uintptr // 虽然只有一个元素，但是其实指针，指向一组固定大小的方法数组 }

• 类型转化

  无论是指针接受者还是值接受者实现转化为接口类型时，会在运行时获取接受者的类型以及数据，组装好运行时的eface或iface结构体。

• 类型断言

  断言的实质其实就是比较目标类型的hash和接口类型的hash是否相等；

• 动态派发

  动态派发（Dynamic dispatch）是在运行期间选择具体多态操作（方法或者函数）执行的过程，它是面向对象语言中的常见特性6。

  在如下所示的代码中，main 函数调用了两次 Quack 方法：

  1. 第一次以 Duck 接口类型的身份调用，调用时需要经过运行时的动态派发；
  2. 第二次以 *Cat 具体类型的身份调用，编译期就会确定调用的函数：

  1 2 3 4 5

  func main() { var c Duck = &Cat{Name: "draven"} c.Quack() // 动态派发 c.(*Cat).Quack() }

  动态派发会进行额外的指令来选择函数。使用动态派发会对程序性能造成一定影响，建议都使用指针实现，因为指针实现的动态派发成本更小一点。而且给项目带来的好处时要大于性能上的一点损失的。

通道

chan是go语言特有的数据结构，是go实现CSP并发编程模型的关键数据结构。值得注意的是，chan并不是完全无锁的结构，只是在某些关键路径上实现了无锁。

• 数据结构

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

  type hchan struct { qcount uint // 元素个数 dataqsiz uint // 循环队列的长度 buf unsafe.Pointer// 缓冲区数据指针 elemsize uint16 // 元素大小 closed uint32 elemtype *_type // 元素类型 sendx uint // 发送操作处理到的位置 recvx uint // 接收操作处理到的位置 recvq waitq // 缓冲区空间为空而阻塞的接收goroutine双向链表 sendq waitq // 缓冲区空间不足而阻塞的发送goroutine双向链表 lock mutex } type waitq struct { first *sudog last *sudog }

• 创建管道

  创建管道只能通过make(vhan int,n)的方式

  1. 如果是创建无缓冲的管道，也就是hchan.buf为nil，不会分配内存
  2. 如果是channel中存储的类型是指针，那么会直接给hchan.buf分配内存
  3. 如果是有缓冲并且基础类型不是指针的，则也会直接给hchan.buf分配内存

• 发送数据

  发送数据之前，会给chan加锁，防止并发安全问题。发送的逻辑如下：

  1. 如果hchan.recvq非空，表示有goroutine阻塞等待接收管道数据，则会取出最先陷入等待的goroutine并直接向它发送数据，并且将该goroutine标记为可运行，等待处理器调度执行；
  2. 如果hchan.recvq为空，表示没有goroutine阻塞等待接收管道数据，且缓冲区有空余空间，就会将发送数据写入hchan.buf中；
  3. 如果缓冲区已满或者没有接收者来接收数据，那么执行发送操作的goroutine就会一直阻塞下去

  调度时机：第一步并没有立即调度执行；还有就是第三步阻塞其实就是调用gopark让出处理器使用权。

• 接收数据

  接收数据之前也会给chan加锁，接收逻辑如下：

  1. 当hchan为空时，会直接挂起当前goroutine
  2. 如果当前hchan已经被关闭并且缓冲区没有数据，会直接返回
  3. 如果hchan.sendq队列存在挂起的goroutine，表示存在期待发送数据的goroutine，那么可以直接将该goroutine取出来，然后去接收数据
  4. 如果缓冲区存在数据，则去缓冲区取数据
  5. 如果缓冲区也没有数据，那么就会阻塞挂起等待，将当前goroutine加入hchan.recvq队列里等待调度器唤醒。

  调度时机：第一步挂起协程；第五步也会挂起协程

• 关闭管道

  一旦管道关闭，管道还能读取数据，但是不能写入数据，而且管道也不会发生阻塞