数组
Go 语言中的数组是一个由固定长度的相同类型元素组成的序列。
- 数组类型定义了长度和元素类型，在内存中连续存储，通过索引的方式访问。
- 数组变量属于值类型，当一个数组变量被赋值或者传递时会复制整个数组。为了避免复制数组，一般会传递指向数组的指针。
- 数组的长度是固定的，长度是数组类型的一部分。长度不同的两个数组是不可以相互赋值的，因为这两个数组属于不同的类型。
底层数据结构
Go 语言数组类型的底层数据结构定义如下，完整代码见 Github（go1.23）：
// Array contains Type fields specific to array types.
type Array struct {
Elem *Type // element type
Bound int64 // number of elements; <0 if unknown yet
}
该类型包含两个字段，分别是元素类型 Elem 和数组的大小 Bound，这两个字段共同构成了数组类型，而当前数组是否应该在堆栈中初始化也在编译期就确定了。
切片
Go 的切片是在数组之上的抽象数据类型。数组固定长度，缺少灵活性，大部分场景下会选择使用基于数组构建的切片类型，切片类型为处理同类型数据序列提供一个方便而高效的方式。
底层数据结构
Go 语言切片的底层数据结构包含三个字段，完整代码见 Github（go1.23）：
type slice struct {
array unsafe.Pointer
len int
cap int
}
array：指向底层数组类型的指针。len：切片的长度，表示切片中元素的个数。cap：切片的容量，表示切片可以容纳的最大元素个数。
切片的长度和容量可以通过内置函数 len() 和 cap() 获取。
常用操作
切片操作并不复制切片指向的元素，创建一个新的切片会复用原来切片的底层数组，因此切片操作是非常高效的。
切片的常用操作包括：
- 创建切片：使用
make函数或字面量创建。 - 索引操作：通过索引访问和修改切片中的元素。
- 切片操作：使用
slice[start:end]语法获取切片的子切片。 - 追加元素：使用
append函数向切片追加元素。 - 复制切片：使用
copy函数将一个切片的元素复制到另一个切片。 - 删除元素：通过切片操作删除元素。
扩容机制
Go 在早期版本中是按照小于 1024 时以 2 倍的方式增长，之后以 1.25 倍增长。在后续版本的迭代中优化了切片的扩容机制，具体可见该 Commit 的改动。
代码示例
package main
import (
"fmt"
"testing"
)
func testSliceLenAndCapByAppend(_ *testing.T, length, initCap int) {
nums := make([]int, 0, initCap)
oldCap := cap(nums)
capSlice := []int{oldCap}
for range length {
nums = append(nums, 1)
newCap := cap(nums)
if newCap != oldCap {
capSlice = append(capSlice, newCap)
oldCap = newCap
}
}
fmt.Println("Capacity:", capSlice)
}
func TestSliceLenAndCapByAppend_10000_0(t *testing.T) { testSliceLenAndCapByAppend(t, 10000, 0) }
func TestSliceLenAndCapByAppend_10000_1(t *testing.T) { testSliceLenAndCapByAppend(t, 10000, 1) }
func TestSliceLenAndCapByAppend_10000_3(t *testing.T) { testSliceLenAndCapByAppend(t, 10000, 3) }
func TestSliceLenAndCapByAppend_10000_5(t *testing.T) { testSliceLenAndCapByAppend(t, 10000, 5) }
func TestSliceLenAndCapByAppend_10000_7(t *testing.T) { testSliceLenAndCapByAppend(t, 10000, 7) }
func TestSliceLenAndCapByAppend_10000_11(t *testing.T) { testSliceLenAndCapByAppend(t, 10000, 11) }
go1.23 版本的执行结果：
=== RUN TestSliceLenAndCapByAppend_10000_0
Capacity: [0 1 2 4 8 16 32 64 128 256 512 848 1280 1792 2560 3408 5120 7168 9216 12288]
--- PASS: TestSliceLenAndCapByAppend_10000_0 (0.00s)
=== RUN TestSliceLenAndCapByAppend_10000_1
Capacity: [1 2 4 8 16 32 64 128 256 512 848 1280 1792 2560 3408 5120 7168 9216 12288]
--- PASS: TestSliceLenAndCapByAppend_10000_1 (0.00s)
=== RUN TestSliceLenAndCapByAppend_10000_3
Capacity: [3 6 12 24 48 96 192 384 672 1184 1696 2384 3408 5120 7168 9216 12288]
--- PASS: TestSliceLenAndCapByAppend_10000_3 (0.00s)
=== RUN TestSliceLenAndCapByAppend_10000_5
Capacity: [5 10 20 40 80 160 336 672 1184 1696 2384 3408 5120 7168 9216 12288]
--- PASS: TestSliceLenAndCapByAppend_10000_5 (0.00s)
=== RUN TestSliceLenAndCapByAppend_10000_7
Capacity: [7 14 28 56 112 224 512 848 1280 1792 2560 3408 5120 7168 9216 12288]
--- PASS: TestSliceLenAndCapByAppend_10000_7 (0.00s)
=== RUN TestSliceLenAndCapByAppend_10000_11
Capacity: [11 22 44 88 176 384 672 1184 1696 2384 3408 5120 7168 9216 12288]
--- PASS: TestSliceLenAndCapByAppend_10000_11 (0.00s)
PASS
ok command-line-arguments 0.005s
可以看出，在 1.23 版本的测试结果下，确实与早期版本的扩容机制表现不同。
性能陷阱
在已有切片的基础上进行切片，不会创建新的底层数组。因为原来的底层数组没有发生变化，内存会一直占用，直到没有变量引用该数组。因此很可能出现这么一种情况，原切片由大量的元素构成，但是我们在原切片的基础上切片，虽然只使用了很小一段，但底层数组在内存中仍然占据了大量空间，得不到释放。比较推荐的做法，使用 copy 替代切片操作。
// NOTE: 直接切片操作，不推荐，因为底层数组仍然占用内存。
func LastNumsBySlice(origin []int) []int {
return origin[len(origin)-2:]
}
// NOTE: 使用 copy 操作，推荐，因为底层数组只占用需要的空间。
func LastNumsByCopy(origin []int) []int {
result := make([]int, 2)
copy(result, origin[len(origin)-2:])
return result
}
哈希表
哈希表是计算机科学中的最重要数据结构之一，这不仅因为它 𝑂(1) 的读写性能非常优秀，还因为它提供了键值之间的映射。
哈希函数
实现哈希表的关键点在于哈希函数的选择，哈希函数的选择在很大程度上能够决定哈希表的读写性能。在理想情况下，哈希函数应该能够将不同键映射到不同的索引上，这要求哈希函数的输出范围大于输入范围，但是由于键的数量会远远大于映射的范围，所以在实际使用时，这个理想的效果是不可能实现的。
比较实际的方式是让哈希函数的结果能够尽可能的均匀分布，然后通过工程上的手段解决哈希碰撞的问题。哈希函数映射的结果一定要尽可能均匀，结果不均匀的哈希函数会带来更多的哈希冲突以及更差的读写性能。如果使用结果分布较为均匀的哈希函数，那么哈希的增删改查的时间复杂度为 𝑂(1)；但是如果哈希函数的结果分布不均匀，那么所有操作的时间复杂度可能会达到 𝑂(𝑛)。
哈希碰撞
多数的哈希函数都是不够完美的，所以仍然存在发生哈希碰撞的可能，这时就需要一些方法来解决哈希碰撞的问题，常见方法的就是『开放寻址法』和『拉链法』。
这里提到的哈希碰撞不是多个键对应的哈希完全相等，可能是多个哈希的部分相等。例如 bmap 结构中的 tophash（hashkey 的高 8 位字节）。
开放寻址法
开放寻址法是一种在哈希表中解决哈希碰撞的方法，当目标位置已被占用出现哈希冲突时候时，按照某种预定的探测序列在哈希表中寻找下一个空闲的位置，直到找到一个空槽或者搜索完整个表。
如果使用开放寻址法来实现哈希表，那么实现哈希表底层的数据结构就是数组，不过因为数组的长度有限，向哈希表写入 <key, value> 这个键值对时，按下面的方式计算写入的位置索引，如果发生了冲突，按预定的探测方法依次计算后续的位置，将键值对写入到下一个索引不为空的位置；注意数组位置写入的内容包含键和值，而不仅只存储值。
index := hash(key) % len(array)
当需要查找某个键对应的值时，会从索引的位置处开始，按照预定的探测方法计算线性探测数组，当匹配上对应目标键（使用原始的 key 而非哈希值来对比）时说明查找成功，如果遇到空内存则意味着对应键不存在于哈希表中。
常见的探测方法有线性探测、二次探测、双重哈希：
- 线性探测：
h(key, i) = (hash_function(key) + i) % table_size。i 是探测次数。- 最简单，但容易导致聚集（连续的被占用区域），使后续探测变慢。
- 二次探测：
h(key, i) = (hash_function(key) + c1 * i + c2 * i^2) % table_size。c1, c2 是常数。- 减少聚集，但可能导致二次聚集（探测序列相同的键会冲突），且不一定能探测到所有桶。
- 双重哈希：
h(key, i) = (hash1(key) + i * hash2(key)) % table_size。使用两个不同的哈希函数。- hash1 计算初始位置，hash2 计算步长。
- 这是开放寻址法中效果最好的方法之一，能有效减少聚集。
拉链法
拉链法是哈希表最常见的实现方法，哈希表的每个位置不再只存储一个键值对，而是存储一个链表的头指针，所有映射到同一个位置的键值对都存储在这个桶对应的链表中。由于存储节点的内存都是动态申请的，可以节省比较多的存储空间。
当向哈希表写入数据时，与开放寻址法使用相同的方式计算出写入的位置，再遍历该位置处关联的链表。
- 当找到与要写入键相同的键时，覆盖对应的值。
- 没有找到键相同的键时，在链表的末尾追加新的节点并写入键值对。
当读取键对应的值时，则遍历目标位置处对应的链表，查找目标键。
Go 语言哈希表的实现
Go 语言中的哈希表是通过 map 实现的，底层数据结构主要 hmap 和 bmap 两个部分组成。hmap 是哈希表的头部结构体，包含了哈希表的元数据和指向桶的指针；bmap 是桶的结构体，存储了键值对和溢出桶。完整源代码见 Github（go1.23）。
代码示例
// A header for a Go map.
type hmap struct {
// Note: the format of the hmap is also encoded in cmd/compile/internal/reflectdata/reflect.go.
// Make sure this stays in sync with the compiler's definition.
count int // # live cells == size of map. Must be first (used by len() builtin)
flags uint8
B uint8 // log_2 of # of buckets (can hold up to loadFactor * 2^B items)
noverflow uint16 // approximate number of overflow buckets; see incrnoverflow for details
hash0 uint32 // hash seed
buckets unsafe.Pointer // array of 2^B Buckets. may be nil if count==0.
oldbuckets unsafe.Pointer // previous bucket array of half the size, non-nil only when growing
nevacuate uintptr // progress counter for evacuation (buckets less than this have been evacuated)
extra *mapextra // optional fields
}
// mapextra holds fields that are not present on all maps.
type mapextra struct {
// If both key and elem do not contain pointers and are inline, then we mark bucket
// type as containing no pointers. This avoids scanning such maps.
// However, bmap.overflow is a pointer. In order to keep overflow buckets
// alive, we store pointers to all overflow buckets in hmap.extra.overflow and hmap.extra.oldoverflow.
// overflow and oldoverflow are only used if key and elem do not contain pointers.
// overflow contains overflow buckets for hmap.buckets.
// oldoverflow contains overflow buckets for hmap.oldbuckets.
// The indirection allows to store a pointer to the slice in hiter.
overflow *[]*bmap
oldoverflow *[]*bmap
// nextOverflow holds a pointer to a free overflow bucket.
nextOverflow *bmap
}
// A bucket for a Go map.
type bmap struct {
// tophash generally contains the top byte of the hash value
// for each key in this bucket. If tophash[0] < minTopHash,
// tophash[0] is a bucket evacuation state instead.
tophash [abi.MapBucketCount]uint8
// Followed by bucketCnt keys and then bucketCnt elems.
// NOTE: packing all the keys together and then all the elems together makes the
// code a bit more complicated than alternating key/elem/key/elem/... but it allows
// us to eliminate padding which would be needed for, e.g., map[int64]int8.
// Followed by an overflow pointer.
}
其中 hmap 是最核心的结构体，有以下关键字段：
B：表示当前哈希表持有的 buckets 数量的对数，也就是len(buckets) == 2^B。hash0：是哈希的种子，它能为哈希函数的结果引入随机性，这个值在创建哈希表时确定，并在调用哈希函数时作为参数传入。oldbuckets：是哈希在扩容时用于保存之前 buckets 的字段，它的大小是当前 buckets 的一半，只在扩容的过程中不为空。buckets：是哈希表的核心数据结构，存储了所有的键值对，即指向长度为 2^B 的 bmap 数组的指针。extra：是一个指向 mapextra 结构体的指针，包含了一些额外的字段，比如 overflow 和 oldoverflow，用于存储溢出桶。
bmap 是哈希表的桶结构体，定义中只有一个字段：
tophash：是一个长度为 8 的字节数组，存储了当前 bucket 中每个键的哈希值的高位部分。它用于快速判断键是否存在于桶中。
在运行期间，bmap 结构体其实不止包含 tophash 字段，因为哈希表中可能存储不同类型的键值对，而且 Go 语言也不支持泛型，所以键值对占据的内存空间大小只能在编译时进行推导。runtime.bmap 中的其他字段在运行时也都是通过计算内存地址的方式访问的，所以它的定义中就不包含这些字段。
「图片来自 Go 语言设计与实现」
Go 的 map 实现采用了拉链法的变体，通过桶 + 溢出桶的设计，在保持拉链法优点的同时，显著提高了缓存命中率，使其成为高性能的哈希表实现。
读写操作
读取
- 先通过哈希表设置的哈希函数、种子获取当前键对应的哈希。
- 再通过计算拿到该键值对所在的桶序号和哈希高位的 8 位数字。
- 依次遍历正常桶和溢出桶，先比较哈希的高 8 位和桶中存储的 tophash，再比较传入的和桶中的值以加速数据的读写。
- 当发现桶中的 tophash 与传入键的 tophash 匹配之后，再通过指针和偏移量获取哈希中存储的键 keys[index] 并与传入的 key 比较，如果两者相同就会获取目标值的指针 values[index] 并返回。
「图片来自 Go 语言设计与实现」
写入
- 计算哈希值，获取写入的键对应的哈希。
- 根据计算的哈希值和桶的数量，获取该键值对应该存储的桶序号和 tophash。
- 写入键值对到哈希表中。
- 如果该桶中没有数据，则将新的键值对添加到该桶中，并更新哈希表的计数器。
- 如果该桶中已经有数据，则需要遍历该桶中的所有键值对，如果存在相同的键，则更新该键对应的值。不存在则将插入。
- 如果该桶已满，则尝试插入到溢出桶中。若无溢出桶则新建溢出桶并插入。
- 如果哈希表的计数器超过了负载因子，则触发扩容操作。
扩容
采用渐进式搬迁策略，避免一次性迁移大量数据导致性能抖动。当『装载因子超过阈值』或者『溢出桶数量过多』时触发。
- 创建新桶数组，大小为原桶数的两倍。
- 设置 oldbuckets 指向旧桶数组，buckets 指向新桶数组。
- 标记 growing 状态，后续操作（读、写、删除）会辅助搬迁数据。
- 渐进搬迁，每次操作最多搬迁两个桶的键值对，直到所有数据迁移完成。
「图片来自 Go 语言设计与实现」
删除
- 通过哈希值找到目标桶和键的位置。
- 如果在删除期间遇到了哈希表的扩容，就会分流桶中的元素。
- 将键值对置为零值，并标记 tophash 为 empty。