Golang 基本数据结构 Slice 与 Map 的底层实现

Question

数组，切片

Go 语言数组在初始化之后大小就无法改变，数组在内存中都是一连串的内存空间。当一个数组变量被赋值或者被传递的时候，实际上会复制整个数组。如果数组较大的话，数组的赋值也会有较大的开销。

但我们更常用的数据结构是切片，切片的结构：

type SliceHeader struct {
    Data uintptr
    Len  int
    Cap  int
}

Data 是一片连续的内存空间，这片内存空间可以用于存储切片中的全部元素，所以我们可以将切片理解成一片连续的内存空间加上长度与容量的标识。

append 的扩容策略：

1. 如果期望容量大于当前容量的两倍就会使用期望容量；
2. 如果当前切片的长度小于 1024 就会将容量翻倍；
3. 如果当前切片的长度大于 1024 就会每次增加 25% 的容量，直到新容量大于期望容量；

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

var class_to_size = [_NumSizeClasses]uint16{
    0,
    8,
    16,
    32,
    48,
    64,
    80,
    ...,
}

扩容后最终会返回一个新的切片，其中包含了新的数组指针、大小和容量。

举个例子：

var arr []int64
arr = append(arr, 1, 2, 3, 4, 5)

当我们执行上述代码时，会触发 runtime.growslice 函数扩容 arr 切片并传入期望的新容量 5，这时期望分配的内存大小为 40 字节；不过因为切片中的元素大小等于 sys.PtrSize，所以运行时会调用 runtime.roundupsize 向上取整内存的大小到 48 字节，所以新切片的容量为 48 / 8 = 6。

• slice预先分配内存（指定cap）可以提升性能，但使用index赋值而非append性能甚至更好
• slice 的一些trick操作：https://ueokande.github.io/go-slice-tricks/
• 使用 for ... range迭代slice时，在循环开始前仅会计算一次迭代次数，在迭代过程中修改slice不会影响迭代次数

关于slice，推荐golang的官方博客：slice原理介绍

哈希表

数据结构：拉链法的哈希表

初始化、增加、修改、删除、访问

• map添加key会自动扩容，但删除key不会自动缩容（小心OOM）
• map的值其实是指针，因为makemap返回的实际上是一个hmap的指针，传map传的是指针，所以修改会影响整个map
• 对map进行迭代时，如果在迭代过程中删除了还未迭代到的键值对，则该键值对不会被迭代到；如果在迭代过程中新增键值对，那么该键值对有可能被迭代，也有可能不被迭代

字符串

字符串实际上是一片连续的内存空间，是一个只读的字节数组，如果要修改，可以先转成 []byte 之后修改再转回 string。

当进行字符串拼接时，多数情况下都会进行拷贝；当进行 []byte 的类型转换时（比如json解析和序列化），也会进行内存拷贝，当字符串比较长时，是一个需要考虑的代码性能问题。

方法

Go 语言中，通过在结构体内置匿名的成员来实现继承：

import "image/color"

type Point struct{ X, Y float64 }

type ColoredPoint struct {
    Point
    Color color.RGBA
}

通过嵌入匿名的成员，我们不仅可以继承匿名成员的内部成员，而且可以继承匿名成员类型所对应的方法。

结构体的匿名成员：可以直接访问叶子属性而不需要给出完整的路径

内置变量类型冷知识

插入一个内容，是我从Go语言圣经里看到的，和常用的变量类型有关，个人觉得算冷知识：

• int 型的大小是 32 或者 64bit，和编译器有关
• 浮点数到整数的转换将丢失任何小数部分，然后向数轴零方向截断
• 一个 float32 类型的浮点数可以提供大约6个十进制数的精度，而float64则可以提供约15个十进制数的精度；通常应该优先使用float64类型，因为float32类型的累计计算误差很容易扩散，并且float32 能精确表示的正整数并不是很大（译注：因为float32的有效bit位只有23个，其它的bit位用于指数和符号；当整数大于23bit能表达的范围时，float32的表示将出现误差）
• 在 `` 形式的字符串中，没有转义操作