主题
数据结构与算法：从操作需求出发，理解每一种结构为什么存在
要保存一批数据，先问三个问题：按什么方式找，按什么顺序取，修改有多频繁。订单 ID 查详情、取当前最早到期任务、按时间扫描一段记录，看起来都是“存和取”，需要维护的关系却不同。
这篇文章把知识地图里的结构与算法逐一展开。每一项都看它维护什么不变量、怎样完成操作、适合什么场景，以及成本藏在哪里。文中的短程序用 Go 1.27.2 实际运行，完整代码和测试放在来源之后。B+ 树、红黑树、跳表和真实 LSM 引擎主要依据原论文、官方实现解释，没有把手绘结构或内存模拟说成数据库实测。
复杂度先写清口径：最坏、期望和摊还不能互换
设 n 为元素个数。讨论 O(1)、O(log n)、O(n) 时，通常先采用“一个固定大小值的读取、比较等基本操作成本有界”的模型。字符串比较可能扫描多个字节，键哈希也要处理键内容；它们的长度不能永远藏在常数里。Go map 的具体哈希与表组织可查固定实现，语言规范并不承诺任何操作永远常数时间。Go 1.27.2 map 实现说明
| 口径 | 回答的问题 | 例子 |
|---|---|---|
| 最坏情况 | 这个规模里最不利的一次或一组输入有多贵 | 普通数组中间插入可能移动 O(n) 个元素 |
| 期望时间 | 对明确的随机机制或分布取平均后多贵 | 随机层高跳表操作的期望 O(log n) |
| 摊还时间 | 一串操作的总成本，平均到每次有多贵 | 几何扩容数组尾部追加，摊还 O(1) |
| 实测耗时 | 这个实现、机器和负载下花了多久 | 必须有基准条件，不能由大 O 直接换算 |
摊还不要求“输入随机”。例如人为规定容量每次翻倍，追加 n 个元素时，扩容搬运量是一串几何级数；虽有个别追加很贵，总搬运量仍为 O(n)。这一推导对应附录 growDemo，它故意使用固定翻倍规则，不是 Go slice 的扩容规则。Go 的实际策略与容量、元素大小等实现细节有关。Go growslice、nextslicecap
go
if len(a) == cap(a) {
b := make([]int, len(a), max(1, 2*cap(a)))
copies += copy(b, a)
a = b
}
a = append(a, i)实际追加 8 次：
text
doubling: capacities=[1 2 4 8] copied=7 appended=8搬运了 0+1+2+4=7 个旧元素。其中从容量 4 扩成 8 的那一次仍要复制 4 个元素，不能因为摊还 O(1) 就说任意一次追加都没有停顿。需要限制尾延迟时，预分配或分块结构可能比只看平均成本更重要，这是由上述成本模型得到的选择建议。
先有一张操作地图
| 主要需求 | 可以先考虑 | 付出的主要代价 |
|---|---|---|
| 按下标取值、连续扫描 | 数组、动态数组 | 中间插删需搬动，扩容需分配 |
| 已知节点处频繁移入移出 | 双向链表 | 查位置慢、额外指针和分配 |
| 后进先出 / 先进先出 | 栈 / 队列 | 要管理容量与引用释放 |
| 按键查找 | 哈希表 | 碰撞、扩容；不提供排序顺序 |
| 反复取当前最小或最大 | 堆 | 其他元素仍未全局有序 |
| 内存中有序查找和范围操作 | 红黑树、跳表 | 平衡维护或随机层高、指针成本 |
| 按页组织的有序索引 | B+ 树 | 分裂、合并、并发与页管理 |
| 大量写入，允许后台整理 | LSM 存储组织 | 读、写、空间放大之间取舍 |
| 表示依赖和连通关系 | 图 | 表示方式与遍历算法必须匹配 |
| 快速排除“不在集合中” | 布隆过滤器 | 可能误判存在，不能返回原值 |
| 节点增减时少迁移一部分键 | 一致性哈希 | 不自动保证均匀、复制与故障恢复 |
| 缓存满了要淘汰谁 | LRU / LFU | 维护访问历史，策略可能不适合负载 |
下面按这些需求展开。表中“先考虑”是选择入口，不是唯一答案；实现常数、数据大小和访问模式仍需验证。
数组、链表、栈、队列：先解决位置与顺序
数组：位置可计算，所以随机访问便宜
数组把同类型元素按连续布局保存，下标对应的地址可由起点、元素大小和下标算出。动态数组在空间不足时换更大的底层存储；逻辑上是一个可增长序列，物理上仍要分配和搬运。Go slice 的长度、容量和底层数组关系由规范及运行时实现分别说明。Go 规范 Arrays、Slice types、固定扩容源码
按下标取值是 O(1) 的基本操作；保持顺序地在中间插删，后面的元素要挪动，最坏 O(n)。连续布局有利于顺序访问的局部性，这是通常选择数组作为默认起点的原因，但具体性能仍受元素大小、缓存与遍历方式影响。只知道“大 O 相同”，不足以判定链表和数组扫描一样快。
需要稳定元素地址时也要谨慎：动态数组换了底层存储，旧的引用不会自动改为指向新副本。Go 中旧切片或指针的可达对象仍按语言和 GC 规则存在，但它可能不再是你想更新的那份序列。Go 规范 append
链表：便宜的是已定位节点处的改链，不是按值查找
单向链表每个节点保存后继；双向链表额外保存前驱。插入和删除通过调整邻接指针完成，不必搬动所有后续元素。代价是按第 i 个位置查找通常要沿链走，节点分配和指针也要占空间。Go 1.27.2 container/list 实现
正在绘制图示…
查看图源代码
flowchart LR
A["A 节点"] <--> B["B 节点"]
B <--> C["C 节点"]
A -. "删除 B 后，重接前驱与后继" .-> C
图表示双向链表删除 B 的改链关系。必须先拿到 B 的节点引用；若只有值 "B"，还要把定位成本算进去。对单向链表删除一般节点，还需要它的前驱，不能照搬双向链表的接口条件。
go
l := list.New()
l.PushBack("A")
e := l.PushBack("B")
l.PushBack("C")
l.Remove(e)遍历后实际输出：
text
list after removing known B=[A C]Go container/list 提供 PushFront、PushBack、Remove、MoveToFront 等入口。链表适合把已知节点移到头尾，例如后面的 LRU；单纯装一批小整数顺序扫描，不能仅因为“插删 O(1)”就选它。container/list
栈和队列是访问规则，可以由不同结构实现
栈规定后进先出，适合表达式处理、深度优先遍历和需要恢复上一步的过程。用 slice 末尾入栈、出栈很直接；追加的扩容成本仍是前述摊还成本。队列规定先进先出，适合 BFS、按到达顺序处理任务；它不要求底层必须是链表。数组型栈与队列的作者原著说明
go
stack := []int{1, 2, 3}
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
queue := []int{1, 2, 3}
head := 0
first := queue[head]
queue[head] = 0
head++text
stack pop=3 remaining=[1 2]
queue pop=1 remaining=[2 3]这里的队列使用递增头下标，没有每次删除首元素后移动剩余数据，因此单次出队只做常数步。代价是旧底层数组仍被持有；长期队列应考虑环形缓冲、适当收缩或分块。若元素含指针，已出队槽位应清零，避免无意延长引用对象的生命。入队出队都还要定义空队列和容量上限的处理方式。Go 规范 Slice expressions、clear
环形队列用头位置和元素数区分空与满，索引走到末尾再回到起点。固定容量可以限制内存，满时就必须明确拒绝、阻塞还是丢弃；不能只画一个环而不定义背压。本文短例只演示 FIFO，没有实现并发队列。
哈希表与堆：一个按键找，一个按优先级取
哈希表：哈希值先缩小范围，最后仍要判断键相等
哈希函数把键映射到较小的定位信息。不同键可能碰撞；冲突可以通过同桶链或数组保存，也可以用开放寻址寻找其他槽位。查询必须比较键本身，不能把“哈希相同”当成“键相同”。Go 1.27.2 使用的 Swiss Table 风格实现有组、控制字节和探测规则，这是特定实现，不是所有哈希表都一样。Go map 固定版本设计说明
用故意简单的 x % 4 演示碰撞：
go
buckets := make([][]int, 4)
for _, x := range []int{1, 5, 9} {
buckets[x%4] = append(buckets[x%4], x)
}text
toy hash bucket[1]=[1 5 9] contains5=true contains13=false13 也会映射到桶 1，但扫描并比较键后仍判定不存在。这个例子不是 Go map 的内部结构，只用来隔离“碰撞与相等”的区别。
在散列足够均匀、负载因子受控的模型下，查找插入可达到期望常数成本；碰撞严重时，链式结构可能扫描 O(n) 个键。扩容还需要重建或迁移定位信息，增量扩容只是把工作分散，不能把工作量消除。键越长，哈希和相等比较越不应当作零成本。Go map 源码的 Lookup、Growth 说明
哈希表适合 ID 到对象的索引，不适合天然地回答“比这个键大的下十条”。Go map 的迭代顺序也没有稳定保证，做有序输出时需要另外排序。Go 规范 Range clauses
堆：只维护父子关系，就足够快速取极值
最小二叉堆维护“父节点不大于孩子”的不变量，用完全二叉树形状保证高度为 O(log n)。底层可以是数组，位置 i 的孩子是 2*i+1、2*i+2。根一定最小，两个子树之间却没有全局排序关系。container/heap 不变量与实现
插入时先放到末尾，再向上交换直到不变量恢复；删除最小值时把末尾移到根，再向下调整。每次只沿树高移动，Push、Pop 是 O(log n)，看根是 O(1)。heap.Init 自底向上整理，总代价 O(n)，不需要逐个 Push 的 O(n log n)：底层大量节点只需调整很短的距离。Go heap.Init、Push、Pop
go
h := &intHeap{4, 1, 3, 2}
heap.Init(h)
for h.Len() > 0 {
ordered = append(ordered, heap.Pop(h).(int))
}text
heap pop=[1 2 3 4]注意要调用包函数 heap.Pop(h)；接口方法 h.Pop() 只负责从底层末尾取元素，调整堆是包函数的职责。优先队列适合调度截止时间、最短路径候选、Top-K 等。维护大小为 k 的最小堆可筛出最大的 k 个值，处理 n 个值的比较级成本为 O(n log k)；这依赖“只保留 k 个候选”的策略，不是完整排序。
有序索引的四条路线：B+ 树、红黑树、跳表、LSM
这些结构都能用于有序数据，但不能统称为四种“普通内存树”。跳表是多层链表，LSM 是跨内存与存储组件的组织方式；选择依据也不只是谁的查找复杂度更漂亮。
| 结构 | 主要不变量或组织方式 | 强项 | 主要成本 |
|---|---|---|---|
| B+ 树 | 内部节点分隔键，叶子保存记录或引用并有序连接 | 少层级的页访问、范围扫描 | 页分裂合并、并发协调 |
| 红黑树 | 二叉搜索顺序 + 颜色约束 | 有序操作有最坏 O(log n) 高度界 | 指针、旋转和颜色修复 |
| 跳表 | 每层有序，高层是低层子序列 | 查改逻辑较直观、范围访问自然 | 随机性、额外前向指针，只有期望界 |
| LSM | 更新先积累，再批量生成和合并有序组件 | 写入批处理 | 读放大、写放大、空间放大、后台整理 |
B+ 树：让一次页访问带回更多分支信息
普通二叉树每个节点最多分两路，放在外部存储时可能需要很多次不同页访问。B+ 树让一个内部页容纳多个分隔键和孩子引用，以更高分支数降低高度；所有数据项或指向记录的引用在叶层，叶子有序，常通过相邻链接支持范围扫描。数据库的实际 B-tree 家族还会加入并发、页右链等机制。PostgreSQL 18.0 nbtree README：结构与 Lehman–Yao 变体
正在绘制图示…
查看图源代码
flowchart TB
R["内部节点：分隔键 20、40"] -->|小于 20| L1["叶子：5、10"]
R -->|20 到 40 之前| L2["叶子：20、30"]
R -->|大于等于 40| L3["叶子：40、50"]
L1 -. "叶子后继" .-> L2
L2 -. "叶子后继" .-> L3
查询 30，先在根决定去中间叶子，再在叶中找键。查询 [8,45]，先找到起点所在叶子，之后沿叶链取 10、20、30、40，不必每取一个键都从根重新找。图里的键与页容量是人工示例，没有创建 PostgreSQL 索引。
插入导致叶子装不下时，需要分裂并在父节点增加分隔键；父节点也满时可以向上传播。删除后如何借位、合并或延迟回收则依实现策略。不能只记“查找 O(log n)”而漏掉这些写入和并发成本。同一 README 的 page splits、deletion 部分
在页容量和非根节点占用率有界的外存模型下，高分支数使定位页数接近 O(log_B n)，B 表示页能容纳的量级；范围查询还要付出实际扫描叶页和输出记录的成本。它适合磁盘有序索引，不意味着任意场景下都比内存哈希表快。B 树家族的原始页组织思想见 Bayer、McCreight，1972。
红黑树：限制最长路径，换来最坏情况的有序操作
先有二叉搜索树的不变量：左子树键小于当前键，右子树键大于当前键，重复键如何处理由接口另定。普通搜索树若按递增键逐个插入，可能退化为长链。红黑树通过颜色和局部重排限制这种退化。Guibas、Sedgewick 原论文 §1
常见定义要求：节点红或黑；根和空叶视为黑；红节点不能再有红孩子；从同一节点到各空叶路径上黑节点数相同。由“相同黑高度”和“红不能连续”可推出最长路径至多是最短路径的两倍，进而得到 O(log n) 高度。插入删除可能破坏颜色规则，通过旋转与变色恢复，同时保持搜索顺序。Linux rbtree 官方说明
正在绘制图示…
查看图源代码
flowchart TB
A["20 黑"] --> B["10 黑"]
A --> C["30 黑"]
B --> D["5 红"]
B --> E["15 红"]
C --> F["25 红"]
C --> G["35 红"]
图省略空黑叶。它帮助检查黑高度和红邻接规则，不是说每一棵红黑树都必须长这样，更不是每层颜色都必须交替。保持最坏界的代价是更新实现复杂、每个节点有链接与颜色信息；顺序扫描的局部性通常不如紧凑数组，需要结合真实布局测量。
红黑树适合需要有序查找、前驱后继和动态更新的内存索引。它不因为“平衡”就自动线程安全，比较函数、节点生命期和并发控制仍是调用方或具体库的责任。Linux rbtree 使用与 locking 说明
跳表：在有序链表上增加稀疏的快速通道
底层包含全部键，高层只保留其中一部分。查询从最高层开始，向右走到再走就会越过目标的位置，再降一层；到最低层时确认下一个节点是不是目标。插入先记录各层前驱，再随机选择新节点高度，把它接入这些层。Pugh《A Skip List Cookbook》§2
正在绘制图示…
查看图源代码
flowchart LR
H2["最高层头"] --> K20["20"] --> K50["50"]
H1["中层头"] --> J10["10"] --> J20["20"] --> J40["40"] --> J50["50"]
H0["底层头"] --> I10["10"] --> I20["20"] --> I30["30"] --> I40["40"] --> I50["50"]
K20 -. "降一层" .-> J20
J20 -. "降一层" .-> I20
找 30 时，高层先走到 20，看到 50 会越过；降到中层，40 仍会越过；再降到底层，找到 30。图中相同数字是同一逻辑节点的不同层前向指针，画成分层只是为了说明路径。
若每次继续升层的概率是固定 p，例如 1/2，足够合适的随机层高使搜索、插入、删除具有期望 O(log n) 时间。某一次很差的层高排列仍可能导致 O(n) 路径，所以它与红黑树的最坏界不同。层数上限、随机数质量和规模都需要实现选择。Pugh §2.1、§2.2
顺着最低层即可做范围扫描；更新的局部接链也让某些并发实现更容易组织。但“使用跳表”不自动意味着无锁，额外指针也会占内存。本文没有编造随机跳表的基准或测试其概率尾部。
LSM：把散乱写入改成分批整理，成本移到后面
LSM 的基本思想是先在较小的可写组件里积累更新，再批量合并到更大的有序组件。现代 LevelDB 风格实现常见日志、内存表、不可变有序文件和后台 compaction；这些具体部件属于实现路线，不能说 1996 年的原论文逐项规定了所有现代 SSTable 设计。O'Neil 等原论文 §2—3、LevelDB 1.23 doc/impl.md
正在绘制图示…
查看图源代码
flowchart TB
W["更新请求"] --> LOG["日志：按配置参与恢复保证"]
W --> M["可写内存表"]
M -->|冻结与 flush| S0["新的有序文件"]
S0 --> C["compaction：合并有序输入、处理版本与删除标记"]
SOLD["较旧有序文件"] --> C
C --> SNEW["新的有序输出文件"]
R["查询"] --> M
R --> S0
R --> SOLD
写入不必每条都立即随机改很多旧页，但查询要考虑同一键的多个版本，后台合并又会重新读写数据。讨论性能必须同时说清三个成本：读一个键要查多少地方，写入一份逻辑数据最终改写多少字节，以及为旧版本和合并临时输出保留多少空间。它们不是同一个“放大”。LevelDB 1.23 Compaction、Performance
删除一般也要写一个 tombstone，表示“这个版本开始键已删除”。如果把它当作不存在而继续查询旧层，就会让旧值复活。附录用“新层优先”的极小内存模型说明这件事：
go
layers := [][]record{
{{"A", 0, true}, {"B", 2, false}}, // 较新：A 的删除标记
{{"A", 1, false}}, // 较旧：A 的值
}
v, found := lookup(layers, "A")text
LSM newest tombstone: A=0 found=false这个模型按层线性扫描，不能据此声称实现了真实 LSM 的查询复杂度。实际合并时，也不能见到 tombstone 就立即丢弃：必须确认更旧的值不会在未参与合并的层或有效快照中仍被需要。LevelDB 的版本序号与 compaction 判断就是为这些条件服务。LevelDB 1.23 DBImpl::DoCompactionWork
LSM 适合写入多、允许后台整理的存储场景。积压的 compaction 可能占 I/O、增加读成本甚至限制新写入；因此“写优化”不是“不再为写付代价”。本文没有启动 LevelDB 或任何数据库。
图：先选存法，再选遍历目标
图由顶点与边描述关系。调用依赖可以用有向边，道路或连通关系可以用无向边，距离或成本则是边权。先说清是否有向、是否有权、是否允许环，后面才能选算法。Boost Graph 官方概念与邻接结构
| 表示 | 空间量级 | 适合的操作 |
|---|---|---|
| 邻接表 | O(V+E) | 稀疏图，遍历某个点的邻居 |
| 邻接矩阵 | O(V²) | 稠密图，快速检查某一对顶点是否有边 |
V 是顶点数、E 是边数。无向图用邻接表时通常把一条边存两次，量级仍相同。不要因为矩阵查边直接就认定整体算法一定更快，稀疏图的大部分格子会是空的。Boost 邻接表示文档
BFS 用 FIFO 队列，先处理距离起点近的一层，再处理下一层，因此可求无权图或等权边图的最少边数。发现节点时就标记，避免重复入队；邻接表条件下，初始化和扫描成本为 O(V+E)。Boost BFS：算法与 Complexity
正在绘制图示…
查看图源代码
flowchart LR
A["0：起点"] --> B["1：距离 1"]
A --> C["2：距离 1"]
B --> D["3：距离 2"]
C --> D
E["4：不可达"]
go
for head := 0; head < len(q); head++ {
u := q[head]
for _, v := range g[u] {
if d[v] < 0 {
d[v] = d[u] + 1
q = append(q, v)
}
}
}text
BFS distance=[0 1 1 2 -1]DFS 则沿一条路径深入，走不下去再返回，适合遍历、环与依赖分析；递归实现需要考虑最大深度，显式栈可以让资源边界更直接。带权最短路径不能简单使用上面的 BFS：Dijkstra 通过优先队列反复选择当前距离最小的候选，需要非负边权。依赖拓扑排序又要求有向无环图，发现环应报告而不是硬造一个顺序。Boost DFS、Dijkstra、拓扑排序
附录 BFS 为已校验的小图：起点必须有效，所有邻接点都在 [0,len(g)) 内。接收不可信图数据时应先校验这些条件；测试通过不意味着它能安全接受任意输入。
排序：次序之外，还要选稳定性和额外空间
稳定排序保留“比较结果相等”的元素的原先相对顺序。它与结果是否有序是两项独立要求；排序是否原地，又是另一项要求。Go slices.SortStableFunc
| 常见方法 | 怎样推进 | 主要时间口径 | 额外空间与边界 |
|---|---|---|---|
| 插入排序 | 把下一个元素插入已排好前缀 | 最坏 O(n²)，已近有序时常有优势 | 常见实现 O(1) 辅助空间，可稳定 |
| 归并排序 | 两半分别有序后线性合并 | O(n log n) | 常见数组实现需 O(n) 活跃辅助空间，可稳定 |
| 快速排序 | 按枢轴分区后处理两边 | 合理随机模型下期望 O(n log n)，朴素最坏 O(n²) | 需要控制坏分区与递归深度，通常不稳定 |
| 堆排序 | 建堆，反复把极值放到最终位置 | 最坏 O(n log n) | 常见原地实现 O(1) 辅助空间，不稳定 |
这些是常见算法实现口径，不是所有同名变体都相同。Go 1.27.2 排序源码中可直接找到插入排序、堆排序以及带坏分区处理的 pdqsort，不能把标准库说成无保护的最简单快排。Go 固定 slices/zsortordered.go
插入排序在处理第 i 个元素前，前缀已经有序；把较大的元素后移，直到找到插入点。不变量简单，短数组的维护开销低，但逆序大数组会不断长距离搬动。快排则希望每次分区有效缩小问题；枢轴长期落在一端时，递归会退化，所以生产库需要策略保护。
归并排序的关键是“两边都已经有序”。比较两边当前最小项，取较小的加入结果；相等时先取左边，就可维持稳定性。附录实现如下条件：
go
if l[i] <= r[j] {
out = append(out, l[i])
i++
} else {
out = append(out, r[j])
j++
}text
merge sort=[1 1 2 3 4]每层合并总共处理 n 个元素，有 O(log n) 层，因此 O(n log n)；附录是清晰优先的递归分配实现，活跃辅助数据可为 O(n)，整个运行的累计分配量并不因此只分配 n 个元素。需要优化分配时可复用缓冲区，不能只看峰值空间忽略分配流量。
稳定性的实测更直观：输入 A:2, B:1, C:2，按分数稳定排序：
go
slices.SortStableFunc(ps, func(a, b person) int {
return cmp.Compare(a.score, b.score)
})text
stable sort=[{B 1} {A 2} {C 2}]A、C 同分，原来 A 在前，排序后仍如此。非稳定排序某一次也可能恰好保留这个顺序，不能用一个例子证明它具有稳定保证。比较器必须满足相应有序关系，整数比较宜用 cmp.Compare，避免简单相减溢出破坏顺序。slices.SortFunc 比较器约定
二分与双指针：能丢掉哪些候选，必须说得出理由
二分查找：维护“答案仍在这个区间里”
二分不只用来找相等值，更常用来找第一个满足单调条件的位置。下面求有序数组里第一个 a[i] >= x 的下标，也叫 lower bound。维持半开区间 [l,r)，每次排除必然不可能成为答案的一半。Go sort.Search 文档和固定实现
go
l, r := 0, len(a)
for l < r {
m := l + (r-l)/2
if a[m] < x { l = m + 1 } else { r = m }
}
return l对 [1,2,2,4] 的实际结果：
text
lower_bound 2=1 3=3 5=4找 2 得到第一个 2；找 3 返回插入位置 3，那里是 4；找 5 返回 len(a)。所以“返回合法下标”与“找到目标”是两件事，需要再检查 i<len(a) && a[i]==x。每轮区间缩小，比较次数为 O(log n)；若输入未排序，单调性不存在，证明也就失效。
附录用固定随机种子生成多组有序数组，把自写结果与 sort.SearchInts 对照，包含空数组、重复值、缺失值和两端越界。这样的测试能覆盖边界，但证明核心仍是不变量，不是“随机跑过就肯定对”。
双指针：每一步移动都要有可排除性
对递增数组找两数和，用一个指针在左、一个在右。和偏小，固定左值再换更小的右值只会更小，因此可以排除这个左值，左指针前进；和偏大则对称地减小右指针。两边总共最多移动 O(n) 次。这个推导只适用于具有相应有序关系的问题，不能直接套在无序数组上；附录代码实现了这条不变量。
go
s := a[l] + a[r]
if s == target { return a[l], a[r], true }
if s < target { l++ } else { r-- }输入 [1,2,4,7]、目标 9：
text
pair sum 9=2+7 found=true本例使用小整数，和不会溢出。任意 int 输入需要安全处理加法，否则比较方向可能错误。若为了使用双指针先排序，排序成本也要计算进去；若还要返回原始下标，还要保留位置映射。
同向双指针常用于去重和滑动窗口，但窗口题还需说明何时能安全收缩。例如仅凭当前和太大就缩小窗口，需要合适的非负性等条件；含负数时这个判断未必成立。“两个下标”只是代码形状，正确性来自可以排除候选的理由。
动态规划与回溯：一个合并重复子问题，一个探索选择
动态规划：先定义状态，再写转移
动态规划把原问题拆成会重复出现的子问题，保存结果，按依赖顺序计算。最重要的动作不是“建一个 dp 数组”，而是明确数组每个位置究竟表示什么，以及为什么这些状态足以决定后续结果。动态规划的原始框架见 Bellman，1952；下面的具体转移由问题定义和附录代码直接推导。
以无限次使用正整数面额，凑出金额 A 的最少硬币数为例，定义 dp[v] 为凑出 v 的最少枚数：dp[0]=0；其他初始为不可达。最后一枚若是 c，前面必须凑出 v-c，所以在所有合法 c 中取 dp[v-c]+1 的最小值。
go
for v := 1; v <= amount; v++ {
d[v] = amount + 1
for _, c := range coins {
if c <= v { d[v] = min(d[v], d[v-c]+1) }
}
}text
min coins [1 3 4], amount=6: 2结果是 3+3。每次优先选最大面额的贪心会走成 4+1+1，因此这个面额集合不能靠那条贪心规则保证最优。DP 用状态保存“较小金额已经计算出的最优结果”，避免每条选择路径重新求一次。
这里有 A 个金额状态、每个最多看 k 个面额，时间 O(Ak)、空间 O(A)。这是按数值 A 的复杂度，不是按 A 的二进制位数，因此属于伪多项式量级。大金额直接分配 amount+1 个 int 可能不可接受。附录只演示小金额，要求面额正、金额有界且 amount+1 不溢出；实际接口应先限制输入和预算。
改成“每种硬币只能用一次”，状态或遍历顺序就要重新设计。若还要返回具体组合，需要记录选择或回溯转移；不能把一个最小计数直接当成完整方案。
回溯：做选择、递归、恢复现场
回溯适合枚举或约束搜索。每一步选一个候选，把它加入当前状态；深入后再撤销，让下一条分支从正确的状态出发。剪枝的条件必须证明后续不可能形成有效答案，不能因为“看起来希望不大”就跳过。选择与恢复是回溯的关键机制，复杂问题中的高效恢复见 Knuth《Dancing Links》。
对互异元素 [1,2] 求所有子集，每个位置有“不选”和“选”两条分支：
go
if i == len(a) {
result = append(result, slices.Clone(path))
return
}
visit(i + 1) // 不选
path = append(path, a[i])
visit(i + 1) // 选
path = path[:len(path)-1] // 恢复text
subsets [1 2]=[[] [2] [1] [1 2]]叶子处必须复制 path，否则不同答案可能共享被后续修改的底层数组。输入有重复元素时，这个算法按位置枚举，会得到值相同的子集，需要另定去重规则。Go slices.Clone
n 个互异元素有 2ⁿ 个子集；把每个子集复制出来，总输出规模是 O(n·2ⁿ)，不能靠记忆化把“显式列出全部结果”压成多项式输出。除结果外，递归与当前路径只需 O(n) 级空间。动态规划适合重用同一状态的结果，回溯适合保留不同选择路径；两者可以结合，但必须先说清要求是计数、最优值，还是列出全部方案。
布隆过滤器：用一点误判，换紧凑的“不存在”判断
标准布隆过滤器维护 m 个 bit。插入一个键，计算 k 个位置并置 1；查询时，只要任何位置是 0，就判定未加入；所有位置都是 1，只能回答“可能存在”。同一 bit 可能由多个键设置，所以它不能保存原值，也不能区分是谁设置了这个 bit。Bloom 原论文、LevelDB 1.23 Bloom 实现
正在绘制图示…
查看图源代码
flowchart LR
K["待查键"] --> H["计算 k 个 bit 位置"]
H --> T{"是否发现 0？"}
T -->|是| N["在正确维护前提下：未加入"]
T -->|否| M["可能存在：仍查真实数据源"]
附录故意用 8 个 bit 和两个极简单的位置函数，插入数字 1 后，9 会落到同样位置：
go
func (b *toyBloom) add(x uint) {
*b |= 1 << (x % 8)
*b |= 1 << ((3*x + 1) % 8)
}text
toy bloom: bits=00010010 inserted1=true absent9=true absent2=false1 真加入过，查询为 true；9 没加入却也为 true，是假阳性；2 查询为 false，可以排除。这个小模型的哈希明显相关，故意制造碰撞，不能拿它的结果去验证独立均匀哈希模型的误判公式。
在经典独立均匀散列近似下，放入 n 个键后，一个 bit 仍为 0 的概率约为 e^(-kn/m)，于是误判率近似 (1-e^(-kn/m))^k。这是模型推导，实际哈希、重复键、位数与占用会影响结果；给定 n、m 时常用的理论选择为 k≈(m/n)ln2。更多 bit 会减少误判，更多哈希并非永远更好，因为查询成本和置 1 密度同时增长。Bloom 1970、LevelDB 参数选择与位检查
“无假阴性”还带前提：插入必须完成，插入和查询规则一致，bit 没被错误清除，结构没有损坏或并发丢更新。不能直接删除一个键对应的 bit，否则可能清掉别的键也需要的位；支持删除要考虑计数型过滤器等变体。它适合放在昂贵查询前减少必定无效的访问，却不能代替最终存在性确认或权限校验。
一致性哈希：减少成员变化时的重映射，不负责搬运数据
简单 hash(key) % N 在 N 改变时，会让许多键的目标一起变化。一致性哈希的一种经典实现把节点和键映射到同一环上，键归属顺时针遇到的第一个节点。加入一个节点时，它只接管其前驱与自身之间的一段键区间。Karger 等，1997，consistent hashing 部分
附录用人工指定的位置排除哈希函数影响：原有 A=20、B=60、C=90，新增 D=40。查找用二分找不小于键位置的第一个节点，超过末尾则回到环头：
go
i := sort.Search(len(r), func(i int) bool { return r[i].pos >= key })
if i == len(r) { i = 0 }
return r[i].nodetext
ring key=10: A -> A
ring key=30: B -> D
ring key=70: C -> C
ring key=95: A -> A只有示例中的 30 改了目标。完整测试遍历 0 到 99，检查发生变更的键都归于新节点 D，没有声称这个人造环具有均匀分布。
真实部署常给每个物理节点分配多个虚拟节点，以平滑随机区间大小并表达权重，但虚拟节点会增加路由表和维护成本，也无法消除某个键本身特别热的问题。即使哈希位置均匀，字节量和请求量也可能不均匀。同一原论文关于 balance、spread 与 load 的定义
还必须定义成员视图、故障检测、复制和数据迁移。一致性哈希只给出目标映射，节点消失后不会自动把它的数据复制到新归属者；不同客户端看到不同成员集合时，也可能路由到不同节点。副本和一致性协议是下一层问题。
LRU 与 LFU：同一段访问记录，会留下不同的缓存
LRU：最近没用过的先淘汰
LRU 维护最近使用顺序。常见精确实现是哈希表定位节点、双向链表维护顺序：命中后移到头部，插入也放头部，满了删除尾部。哈希定位按期望常数计、链表改链为常数步，因此 Get、Put 可达到常见的平均或摊还 O(1) 口径，不能把底层哈希表最坏成本抹掉。Go 链表固定实现、LFU 原论文对 LRU 结构的比较
正在绘制图示…
查看图源代码
flowchart LR
M["map：键到链表节点"] --> A["头部：最近使用 C"]
M --> B["B"]
M --> D["尾部：最久未用 A"]
A <--> B
B <--> D
核心命中操作很短：
go
e, ok := c.items[k]
if !ok { return 0, false }
c.order.MoveToFront(e)
return e.Value.(entry).value, true需要维护的不变量是 map 与链表一一对应，长度不超过容量，每个键只有一个节点。更新旧键要修改原节点并移动，不能重复加节点。命中读也会改顺序，因此这个 Get 不是只读操作。
LRU 适合近期访问有局部性的负载；一次大规模顺序扫描可能把原先热点逐出。这是策略局限，不是数据结构实现错误。并发使用要同步 map 和链表的整体修改，不能只给其中一个加锁。
LFU：用得少的先淘汰，但旧热点可能留下太久
LFU 维护访问频次，淘汰最低频键；频次相同时必须再规定规则，例如在同频中按 LRU 淘汰。朴素做法遍历全部键找最小值，淘汰为 O(n)；用最小堆可做到 O(log n) 更新与淘汰；频次桶加双向链表等结构可以把特定 LFU 操作组织成常数步，仍依赖哈希定位模型和频次管理条件。Matani、Shah、Mitra §4—5
在常数步结构里，键指向自己的条目，条目关联频次桶；一次访问把条目从频次 f 的桶移到 f+1 的桶，空桶及时摘掉，最低频桶可直接定位。实现复杂度高于只维护一条 LRU 链，需要额外关注桶生命期、并发、计数溢出和频次老化。
附录选择一个 O(n) 淘汰的 LFU 参考模拟器，目的是把策略结果做清楚，没有冒充 O(1) LFU 实现。新键频次为 1，命中和更新都加 1，同频按最久访问淘汰。容量为 2，执行：放 A、B → 访问 A 三次 → 访问 B 一次 → 放 C。实际结果：
text
LRU newest-first=[C B] LFU sorted-keys=[A C]LRU 淘汰 A，因为最后一次访问的是 B；LFU 淘汰 B，因为 A 的累计频次更高。两者没有一个在所有负载上都更优：LRU 适应近期变化，LFU 能保留累计热点，但不老化的计数可能让已经过时的热点长期占位。
两份示例缓存都非并发安全，也没有 TTL、字节容量、持久化或后台清理。生产缓存还需决定“容量按条数还是字节”“过期和淘汰谁先发生”“更新是否计一次访问”。只说用了 LRU/LFU，还远远不够描述实际行为。
选择时，把不变量和失败条件一起写下来
选一个结构后，最值得写进代码旁边的通常是以下内容：
- 输入前提：是否已经排序、是否允许重复、图顶点是否合法、金额和数量上限是多少。
- 核心不变量：堆的父子序、二分区间、缓存 map 与链表的一致性、LSM 新旧版本顺序。
- 成本口径：最坏、期望还是摊还；统计的是元素次数、字节、页访问还是实测时间。
- 资源边界：扩容峰值、递归深度、结果集大小、后台整理和并发访问。
本文的代码刻意保留简单模型，让这些关系看得见。能把“为什么这一步能删掉一半候选”“为什么旧值不能重新出现”说清，比背下一个复杂度表更接近真正会用。
依据与验证范围
主要一手依据如下，具体结论旁已链接相应章节或固定源码：
- Go 1.27.2：语言规范；
runtime/slice.go、internal/runtime/maps/map.go、container/list/list.go、container/heap/heap.go、sort/search.go、slices/zsortordered.go；slices.SortStableFunc、slices.Clone文档。本机同版本源码和go doc已核对，远端页面可用性不决定本机源码验证是否成立。 - Bayer、McCreight，1972，Organization and Maintenance of Large Ordered Indexes，DOI 10.1007/BF00288683；PostgreSQL
REL_18_0的 nbtree README 用于具体页结构、分裂与回收实现。 - Guibas、Sedgewick，1978，A Dichromatic Framework for Balanced Trees；Linux 内核 rbtree 官方手册。
- Pugh，A Skip List Cookbook，1989，1990 修订，§2 搜索、插删和随机层高。引用的是报告正文日期，不是大学仓储系统后来的收录日期。
- O'Neil 等，1996，The Log-Structured Merge-Tree；LevelDB 1.23 的
doc/impl.md、db/db_impl.cc、util/bloom.cc。 - Boost Graph Library 1.87 官方手册：邻接表、邻接矩阵、BFS、DFS、Dijkstra、拓扑排序。
- Bellman，1952，On the Theory of Dynamic Programming，DOI 10.1073/pnas.38.8.716；Knuth，2000，Dancing Links。
- Bloom，1970，Space/Time Trade-offs in Hash Coding with Allowable Errors，DOI 10.1145/362686.362692。
- Karger 等，1997，Consistent Hashing and Random Trees；Matani、Shah、Mitra，An O(1) Algorithm for Implementing the LFU Cache Eviction Scheme，arXiv:2110.11602v1。
- 补充阅读为 Pat Morin 本人发布的 Open Data Structures 第 2 章，帮助比较数组型栈与队列；本文成本推导也可直接对照附录操作。
实际运行了附录全部程序，go test -race -v .、go vet . 通过。测试包含二分与标准库对照、归并与标准库对照、不可达金额、空输入、子集副本、BFS 不可达点、缓存更新/容量零/频次并列、布隆已插入检查、一致性哈希新增节点移动范围、tombstone 阻止旧值复活。
没有执行 B+ 树、红黑树、跳表或数据库的完整实现；没有用有限样本验证大 O 定理、布隆概率公式或一致性哈希均匀性；没有做性能基准。本文复杂度来自算法与明确模型，输出来自具体小程序，两者证据范围不同。
完整可复现代码与测试
环境为 Go 1.27.2、Linux/amd64，不依赖第三方包。保存以下三个文件在同一目录：
sh
go version
go run .
go test -race -v .
go vet .程序前提：pairSum 接收已排序且加法不溢出的数据；minCoins 使用小的非负金额与正面额，实际服务需先限制金额和分配预算；bfs 接收已校验的合法图；toyBloom 只演示碰撞，不能用于安全或实际概率估计；LRU、LFU 都只能由一个调用方串行使用或在外部加完整同步；LSM 模拟器只是新层优先的逻辑模型。
go.mod
go
module example.com/foundations/algorithms
go 1.27.0main.go
代码块 · 371 行 · 点击收起 / 展开
go
package main
import (
"cmp"
"container/heap"
"container/list"
"fmt"
"io"
"os"
"slices"
"sort"
)
func lowerBound(a []int, x int) int {
l, r := 0, len(a)
for l < r {
m := l + (r-l)/2
if a[m] < x {
l = m + 1
} else {
r = m
}
}
return l
}
// The teaching input keeps sums inside int range.
func pairSum(a []int, target int) (int, int, bool) {
l, r := 0, len(a)-1
for l < r {
s := a[l] + a[r]
if s == target {
return a[l], a[r], true
}
if s < target {
l++
} else {
r--
}
}
return 0, 0, false
}
func minCoins(coins []int, amount int) int {
if amount < 0 {
return -1
}
for _, c := range coins {
if c <= 0 {
panic("coin must be positive")
}
}
d := make([]int, amount+1)
for v := 1; v <= amount; v++ {
d[v] = amount + 1
for _, c := range coins {
if c <= v {
d[v] = min(d[v], d[v-c]+1)
}
}
}
if d[amount] > amount {
return -1
}
return d[amount]
}
func subsets(a []int) [][]int {
result := [][]int{}
path := []int{}
var visit func(int)
visit = func(i int) {
if i == len(a) {
result = append(result, slices.Clone(path))
return
}
visit(i + 1)
path = append(path, a[i])
visit(i + 1)
path = path[:len(path)-1]
}
visit(0)
return result
}
func bfs(g [][]int, start int) []int {
d := make([]int, len(g))
for i := range d {
d[i] = -1
}
d[start] = 0
q := []int{start}
for head := 0; head < len(q); head++ {
u := q[head]
for _, v := range g[u] {
if d[v] < 0 {
d[v] = d[u] + 1
q = append(q, v)
}
}
}
return d
}
func mergeSort(a []int) []int {
if len(a) < 2 {
return slices.Clone(a)
}
m := len(a) / 2
l, r := mergeSort(a[:m]), mergeSort(a[m:])
out := make([]int, 0, len(a))
i, j := 0, 0
for i < len(l) && j < len(r) {
if l[i] <= r[j] {
out = append(out, l[i])
i++
} else {
out = append(out, r[j])
j++
}
}
out = append(out, l[i:]...)
return append(out, r[j:]...)
}
// growDemo uses a deliberately fixed doubling rule, not Go append's growth policy.
func growDemo(n int) (int, []int) {
a := []int{}
copies := 0
events := []int{}
for i := 0; i < n; i++ {
if len(a) == cap(a) {
capacity := max(1, 2*cap(a))
b := make([]int, len(a), capacity)
copies += copy(b, a)
a = b
events = append(events, capacity)
}
a = append(a, i)
}
return copies, events
}
type intHeap []int
func (h intHeap) Len() int { return len(h) }
func (h intHeap) Less(i, j int) bool { return h[i] < h[j] }
func (h intHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *intHeap) Push(v any) { *h = append(*h, v.(int)) }
func (h *intHeap) Pop() any { a := *h; n := len(a); v := a[n-1]; *h = a[:n-1]; return v }
type entry struct {
key string
value int
}
type lru struct {
capacity int
order *list.List
items map[string]*list.Element
}
func newLRU(capacity int) *lru {
if capacity < 0 {
panic("negative capacity")
}
return &lru{capacity, list.New(), make(map[string]*list.Element)}
}
func (c *lru) get(k string) (int, bool) {
e, ok := c.items[k]
if !ok {
return 0, false
}
c.order.MoveToFront(e)
return e.Value.(entry).value, true
}
func (c *lru) put(k string, v int) {
if c.capacity == 0 {
return
}
if e := c.items[k]; e != nil {
e.Value = entry{k, v}
c.order.MoveToFront(e)
return
}
c.items[k] = c.order.PushFront(entry{k, v})
if c.order.Len() > c.capacity {
e := c.order.Back()
delete(c.items, e.Value.(entry).key)
c.order.Remove(e)
}
}
func (c *lru) keys() []string {
out := []string{}
for e := c.order.Front(); e != nil; e = e.Next() {
out = append(out, e.Value.(entry).key)
}
return out
}
// This LFU reference simulator scans all entries at eviction: O(n), intentionally.
// It gives the policy a simple executable oracle, not an O(1) implementation.
type lfEntry struct{ value, freq, tick int }
type lfu struct {
capacity, tick int
items map[string]lfEntry
}
func newLFU(n int) *lfu {
if n < 0 {
panic("negative capacity")
}
return &lfu{capacity: n, items: map[string]lfEntry{}}
}
func (c *lfu) get(k string) (int, bool) {
v, ok := c.items[k]
if !ok {
return 0, false
}
c.tick++
v.freq++
v.tick = c.tick
c.items[k] = v
return v.value, true
}
func (c *lfu) put(k string, value int) {
if c.capacity == 0 {
return
}
if v, ok := c.items[k]; ok {
c.tick++
v.value = value
v.freq++
v.tick = c.tick
c.items[k] = v
return
}
if len(c.items) == c.capacity {
victim := ""
first := true
var best lfEntry
for k, v := range c.items {
if first || v.freq < best.freq || (v.freq == best.freq && v.tick < best.tick) {
victim, best, first = k, v, false
}
}
delete(c.items, victim)
}
c.tick++
c.items[k] = lfEntry{value, 1, c.tick}
}
func (c *lfu) keys() []string {
keys := []string{}
for k := range c.items {
keys = append(keys, k)
}
slices.Sort(keys)
return keys
}
type toyBloom uint8
func (b *toyBloom) add(x uint) { *b |= 1 << (x % 8); *b |= 1 << ((3*x + 1) % 8) }
func (b toyBloom) maybe(x uint) bool { return b&(1<<(x%8)) != 0 && b&(1<<((3*x+1)%8)) != 0 }
type ringPoint struct {
pos int
node string
}
func owner(r []ringPoint, key int) string {
if len(r) == 0 {
panic("empty ring")
}
i := sort.Search(len(r), func(i int) bool { return r[i].pos >= key })
if i == len(r) {
i = 0
}
return r[i].node
}
type record struct {
key string
value int
deleted bool
}
// Newest layer first, already sorted within each layer; lookup is linear in this toy.
func lookup(layers [][]record, k string) (int, bool) {
for _, layer := range layers {
for _, r := range layer {
if r.key == k {
return r.value, !r.deleted
}
}
}
return 0, false
}
func run(w io.Writer) {
copies, events := growDemo(8)
fmt.Fprintf(w, "doubling: capacities=%v copied=%d appended=8\n", events, copies)
l := list.New()
l.PushBack("A")
e := l.PushBack("B")
l.PushBack("C")
l.Remove(e)
values := []any{}
for e = l.Front(); e != nil; e = e.Next() {
values = append(values, e.Value)
}
fmt.Fprintf(w, "list after removing known B=%v\n", values)
stack := []int{1, 2, 3}
top := stack[len(stack)-1]
stack = stack[:len(stack)-1]
fmt.Fprintf(w, "stack pop=%d remaining=%v\n", top, stack)
queue := []int{1, 2, 3}
head := 0
first := queue[head]
queue[head] = 0
head++
fmt.Fprintf(w, "queue pop=%d remaining=%v\n", first, queue[head:])
buckets := make([][]int, 4)
for _, x := range []int{1, 5, 9} {
buckets[x%4] = append(buckets[x%4], x)
}
fmt.Fprintf(w, "toy hash bucket[1]=%v contains5=%t contains13=%t\n", buckets[1], slices.Contains(buckets[1], 5), slices.Contains(buckets[1], 13))
h := &intHeap{4, 1, 3, 2}
heap.Init(h)
ordered := []int{}
for h.Len() > 0 {
ordered = append(ordered, heap.Pop(h).(int))
}
fmt.Fprintf(w, "heap pop=%v\n", ordered)
fmt.Fprintf(w, "merge sort=%v\n", mergeSort([]int{4, 1, 3, 1, 2}))
type person struct {
name string
score int
}
ps := []person{{"A", 2}, {"B", 1}, {"C", 2}}
slices.SortStableFunc(ps, func(a, b person) int { return cmp.Compare(a.score, b.score) })
fmt.Fprintf(w, "stable sort=%v\n", ps)
a := []int{1, 2, 2, 4}
fmt.Fprintf(w, "lower_bound 2=%d 3=%d 5=%d\n", lowerBound(a, 2), lowerBound(a, 3), lowerBound(a, 5))
x, y, ok := pairSum([]int{1, 2, 4, 7}, 9)
fmt.Fprintf(w, "pair sum 9=%d+%d found=%t\n", x, y, ok)
fmt.Fprintf(w, "min coins [1 3 4], amount=6: %d\n", minCoins([]int{1, 3, 4}, 6))
fmt.Fprintf(w, "subsets [1 2]=%v\n", subsets([]int{1, 2}))
fmt.Fprintf(w, "BFS distance=%v\n", bfs([][]int{{1, 2}, {3}, {3}, {}, {}}, 0))
var b toyBloom
b.add(1)
fmt.Fprintf(w, "toy bloom: bits=%08b inserted1=%t absent9=%t absent2=%t\n", b, b.maybe(1), b.maybe(9), b.maybe(2))
old := []ringPoint{{20, "A"}, {60, "B"}, {90, "C"}}
added := []ringPoint{{20, "A"}, {40, "D"}, {60, "B"}, {90, "C"}}
for _, key := range []int{10, 30, 70, 95} {
fmt.Fprintf(w, "ring key=%d: %s -> %s\n", key, owner(old, key), owner(added, key))
}
lr, lf := newLRU(2), newLFU(2)
for _, c := range []interface{ put(string, int) }{lr, lf} {
c.put("A", 1)
c.put("B", 2)
}
for range 3 {
lr.get("A")
lf.get("A")
}
lr.get("B")
lf.get("B")
lr.put("C", 3)
lf.put("C", 3)
fmt.Fprintf(w, "LRU newest-first=%v LFU sorted-keys=%v\n", lr.keys(), lf.keys())
layers := [][]record{{{"A", 0, true}, {"B", 2, false}}, {{"A", 1, false}}}
v, found := lookup(layers, "A")
fmt.Fprintf(w, "LSM newest tombstone: A=%d found=%t\n", v, found)
}
func main() { run(os.Stdout) }main_test.go
代码块 · 110 行 · 点击收起 / 展开
go
package main
import (
"math/rand/v2"
"slices"
"sort"
"testing"
)
func TestLowerBound(t *testing.T) {
r := rand.New(rand.NewPCG(7, 11))
for n := 0; n < 80; n++ {
a := make([]int, n)
for i := range a {
a[i] = r.IntN(20) - 10
}
slices.Sort(a)
for x := -12; x <= 12; x++ {
got := lowerBound(a, x)
want := sort.SearchInts(a, x)
if got != want {
t.Fatalf("%v %d got %d want %d", a, x, got, want)
}
}
}
}
func TestMergeSort(t *testing.T) {
r := rand.New(rand.NewPCG(9, 13))
for n := 0; n < 100; n++ {
a := make([]int, n)
for i := range a {
a[i] = r.IntN(20)
}
want := slices.Clone(a)
slices.Sort(want)
if got := mergeSort(a); !slices.Equal(got, want) {
t.Fatal(got, want)
}
}
}
func TestAlgorithms(t *testing.T) {
if minCoins([]int{1, 3, 4}, 6) != 2 || minCoins([]int{2}, 3) != -1 || minCoins([]int{2}, 0) != 0 {
t.Fatal("coin cases")
}
if len(subsets([]int{1, 2, 3})) != 8 {
t.Fatal("subsets")
}
s := subsets([]int{1, 2})
s[3][0] = 99
if s[2][0] != 1 {
t.Fatal("paths alias")
}
if _, _, ok := pairSum([]int{}, 1); ok {
t.Fatal("empty pair")
}
if !slices.Equal(bfs([][]int{{1}, {0}, {}}, 0), []int{0, 1, -1}) {
t.Fatal("BFS")
}
}
func TestCache(t *testing.T) {
c := newLRU(2)
c.put("A", 1)
c.put("B", 2)
c.get("A")
c.put("C", 3)
if _, ok := c.get("B"); ok {
t.Fatal("LRU wrong eviction")
}
c.put("A", 9)
if v, ok := c.get("A"); !ok || v != 9 {
t.Fatal("update")
}
z := newLRU(0)
z.put("A", 1)
if len(z.items) != 0 {
t.Fatal("zero capacity")
}
f := newLFU(2)
f.put("A", 1)
f.put("B", 2)
f.put("C", 3)
if _, ok := f.get("A"); ok {
t.Fatal("LFU tie rule")
}
f.get("B")
f.put("D", 4)
if _, ok := f.get("C"); ok {
t.Fatal("LFU frequency")
}
}
func TestBloomRingLSM(t *testing.T) {
var b toyBloom
for x := uint(0); x < 8; x++ {
b.add(x)
if !b.maybe(x) {
t.Fatal("false negative")
}
}
old := []ringPoint{{20, "A"}, {60, "B"}, {90, "C"}}
added := []ringPoint{{20, "A"}, {40, "D"}, {60, "B"}, {90, "C"}}
for k := 0; k < 100; k++ {
if owner(old, k) != owner(added, k) && owner(added, k) != "D" {
t.Fatal("unrelated movement")
}
}
v, ok := lookup([][]record{{{"A", 0, true}}, {{"A", 1, false}}}, "A")
if ok || v != 0 {
t.Fatal("tombstone ignored")
}
}