算法工程索引

这条线不做教材式知识点罗列，而是把算法放回真实工程语境：默认排序怎么选、哈希表为什么快、字符串匹配如何利用 SIMD、近似数据结构在监控和推荐里怎么落地。

本页提供统一入口；当前共收录 118 篇正文。

专题入口

• 字符串匹配算法选型：KMP、BM、AC 自动机与 SIMD
• 排序专题：从 TimSort 到 parallel sort

推荐入口

• TimSort：自然 run、galloping 与从栈不变量到 Powersort 的合并策略
• pdqsort：坏分区计数、重复键分区与块分区如何改造 introsort
• 基数排序：绕开比较下界的代价，从 LSD、American flag sort 到 ska_sort
• 外部排序：从 I/O 下界到 PostgreSQL 与 GNU sort

目录

1. TimSort：自然 run、galloping 与从栈不变量到 Powersort 的合并策略
2. pdqsort：坏分区计数、重复键分区与块分区如何改造 introsort
3. 基数排序：绕开比较下界的代价，从 LSD、American flag sort 到 ska_sort
4. 外部排序：从 I/O 下界到 PostgreSQL 与 GNU sort
5. 并行排序：排序网络、并行归并、样本排序与 GPU 基数排序
6. 排序基准测试：比较次数、分支预测与输入分布
7. 哈希表内部：链式、线性探测、Robin Hood 与生产实现的取舍
8. Cuckoo Hashing：用两个位置换取最坏情况常数查找
9. Swiss Table：控制字节、分组探测与墓碑——对照 Abseil、Go 与 hashbrown 源码
10. 完美哈希：从 FKS 两级表到 gperf 与现代 MPHF
11. 素性测试与素数生成：Miller-Rabin、BPSW 与 OpenSSL/FIPS 186-5
12. 扩展欧几里得与模逆元
13. 格基规约（LLL）：后量子密码的战场
14. 有限域算术：从 AES 到 Reed-Solomon
15. 椭圆曲线算术：群论视角
16. DFA 最小化：词法分析器生成的核心
17. LR 与 LALR 解析：从理论到 yacc/bison
18. PEG 解析与 Packrat：无限前瞻的代价
19. 寄存器分配：图着色与线性扫描
20. SSA 形式与编译器优化
21. 一致性哈希：从 Karger 哈希环到 Jump、Maglev 与有界负载
22. 垃圾回收算法全景
23. 缓存无关算法：让硬件替你优化
24. 无分支编程：当 if 成为性能杀手
25. SIMD 算法设计模式
26. 随机化算法：当运气成为武器
27. 竞争分析与在线算法
28. Bloom Filter 家族：从位数组到 Ribbon，每键位数离下界还差多少
29. 密码学哈希与非密码学哈希：安全定义、迭代构造与哈希洪泛
30. XXH3 与 wyhash：SIMD 累加器和 128 位标量乘法两条提速路线
31. 红黑树与 AVL：旋转次数、树高与 Linux 内核的选择
32. B-tree 深度解剖：从磁盘 I/O 模型到 boltdb 源码
33. B+tree 与 LSM-tree：原地更新与异地更新的读、写、空间代价
34. Treap 与跳表：随机平衡的期望代价与生产参数
35. 线段树与树状数组：前缀分解、懒标记与自底向上实现
36. 持久化数据结构：路径复制、节点复制与宽分支 trie
37. van Emde Boas 树：整数前驱查询的递归结构、空间代价与下界
38. Merkle 树与认证数据结构：包含证明、一致性证明与构造陷阱
39. 后缀数组：倍增、SA-IS、LCP 与增强后缀数组
40. AC 自动机：失败链接、输出链接与转移表布局
41. BWT 与 FM-index：从 bzip2 到基因组比对
42. 编辑距离与模糊匹配：Wagner-Fischer、位并行与 Levenshtein 自动机
43. 字符串哈希：Rabin-Karp、滚动哈希与内容定义分块
44. SIMD 字节扫描：memchr 的页边界、PCMPISTRI 的代价与 JSON/CSV 的引号掩码
45. Unicode 文本算法：UTF-8 编解码与验证、规范化、字素簇与双向文本安全
46. HyperLogLog：从概率计数到 Redis 实现的基数估计
47. Count-Min Sketch：点查询误差界、保守更新与生产实现
48. t-digest：缩放函数、合并与尾部分位数误差
49. 水塘抽样：Algorithm R/L/Z、加权键与样本合并
50. MinHash 与 SimHash：近重复检测的相似度草图与候选生成
51. 频率估计与 Heavy Hitter：Misra-Gries、Space-Saving 与空间下界
52. 流式算法总论：数据流模型、频率矩下界与线性 sketch
53. KD-tree：切分规则、回溯剪枝与维度增长下的失效边界
54. 局部敏感哈希：从概率保证到多探针近邻检索
55. HNSW：分层小世界图的近似近邻搜索
56. 乘积量化与 IVF-PQ：压缩域里的近似最近邻
57. ScaNN 与 DiskANN：量化损失、Vamana 与 SSD 图检索
58. 从零实现一个向量搜索引擎
59. Dijkstra 与 A*：非负权、启发式与工程优先队列
60. Bellman-Ford 与路由协议：负环、SPFA 与距离向量收敛
61. 最小生成树：割性质、Kruskal/Prim/Borůvka 与线性时间开放问题
62. Tarjan 算法族：SCC、割点、桥的统一框架
63. 网络流与二分匹配
64. 拓扑排序：依赖解析的顺序与环
65. PageRank 与随机游走：从链接投票到工程实现
66. 图着色与寄存器分配：从 DSatur 到 Chaitin-Briggs
67. 用户态内存分配器：size class、线程缓存与碎片边界
68. 页面置换算法：从 OPT、LRU 到 ARC 与 Linux 页面回收
69. CPU 调度：CFS 的虚拟运行时间与 EEVDF 的虚拟截止期
70. I/O 调度：在寻道、队列深度与公平性之间取舍
71. 伙伴系统与 SLUB：Linux 物理页和小对象分配的边界
72. 文件系统中的树：extent、HTree 与 CoW B-tree 的代价
73. epoll 的数据结构：红黑树、就绪队列与回调机制
74. 定时器数据结构：堆、时间轮与生产系统的精度权衡
75. Join 算法：嵌套循环、排序归并与 Hybrid Hash 的代价和实现
76. 查询优化器：System R 动态规划、Cascades Memo 与基数误差
77. 数据库缓冲池替换：LRU-K、2Q 与生产级扫描保护
78. WAL 与 ARIES：pageLSN、CLR 与可重启恢复
79. LSM-tree Compaction 策略
80. MVCC 实现变体全解
81. 学习索引：当机器学习遇上数据库
82. TCP 拥塞控制：从 Reno 到 BBRv3
83. 滑动窗口与流控的算法本质
84. 限流算法：令牌桶 / 漏桶 / GCRA
85. 负载均衡算法：P2C / EWMA / 平滑加权轮询
86. 路由算法：距离向量 vs 链路状态 vs 路径向量
87. 主动队列管理：RED → CoDel → FQ-CoDel
88. 无锁队列：Michael-Scott 算法与 ABA 问题
89. 无锁栈：Treiber 栈与指数退避
90. 并发跳表：ConcurrentSkipListMap 的设计
91. Hazard Pointers：安全内存回收的优雅方案
92. Epoch-Based Reclamation：Crossbeam 的实现之道
93. RCU：Linux 内核的读侧零开销并发
94. 并发哈希表：从分段锁到无锁设计
95. MPMC Channel：Go channel 与 crossbeam-channel 的实现对比
96. Huffman 编码与 DEFLATE
97. LZ77、LZ78 与 LZW：字典从哪里来，最长匹配怎么找
98. zstd 的格式与实现：序列、FSE 表、字典与长距离匹配
99. 算术编码、Range Coder 与 ANS：分数比特的记账方式与精度损失
100. 整数压缩：varint → PForDelta → SIMD-BP128
101. 时序数据压缩：Gorilla 编码与 Delta-of-Delta
102. 列式压缩：RLE / Dictionary / FSST
103. 凸包算法：Graham Scan、Andrew 与 Chan 的进化
104. 扫描线算法：从线段交到矩形面积并
105. Voronoi 图与 Delaunay 三角剖分：对偶的力量
106. R-tree 与空间索引：PostGIS 的底层结构
107. 点定位与梯形分解
108. 最近点对与随机化几何算法
109. 树形 DP：换根、虚树与树上背包
110. 状压 DP：用位运算驯服指数空间
111. 斜率优化与凸包技巧
112. 分治优化 DP：决策单调性的力量
113. 区间 DP 与矩阵链乘
114. DP 在工业界：资源调度、广告投放与路径规划
115. 快速傅里叶变换：从多项式乘法到信号处理
116. 手把手教你用 C++ 写一个简单的 JSON 解析器
117. 正则表达式性能优化与 ReDoS 防御实战
118. 正则表达式理论：从形式语言到自动机实现

延伸阅读

• 全部系列索引
• 分布式系统百科
• 存储工程索引
• 网络工程索引