TimSort 深度解剖：Python 与 Java 默认排序的精妙设计
为什么 Python 和 Java 不约而同选择了同一个排序算法？TimSort 对真实数据的哪些特征做了针对性优化，使它在工程实践中击败了教科书算法？
algorithms 分类归档
共 124 篇文章 · 返回首页
pdqsort：击败所有对手的模式自适应排序
Rust 的 sort_unstable 和 C++ Boost.Sort 背后的 pdqsort 如何做到在几乎所有数据分布上都表现优异？模式自适应意味着什么？
外部排序：当数据装不进内存
当数据量超过内存容量时，排序算法面临全新的挑战。从败者树到异步 I/O，外部排序的工程实现远比教科书描述的复杂。
并行排序：从归并网络到 GPU 双调排序
当单核性能到达瓶颈，排序如何利用多核 CPU 和 GPU 的并行能力？从排序网络的理论优雅到工业级并行排序的工程妥协。
排序基准测试：用数据说话
12 种排序算法在 7 种数据分布、4 种数据规模下的全面对比。用实测数据回答'什么时候该用什么排序'这个永恒的问题。
哈希表内部：开放寻址、链式、Robin Hood 的三国演义
Go 的 map 用的是什么哈希表？Rust 的 HashMap 呢？Python 的 dict 呢？它们分别选了三条完全不同的路线——链式哈希、Swiss Table、开放寻址。选择背后的 trade-off 远比你想象的深。
Cuckoo Hashing：最坏 O(1) 查找的优雅设计
传统哈希表的 O(1) 查找是'期望'——运气不好时，线性探测可能走 50 步。Cuckoo Hashing 给出了'确定性' O(1)：最多查 2 次（或 d 次）就知道元素在不在。这个保证对网络设备中的精确匹配至关重要。
Swiss Table：Google 的 SIMD 加速哈希表
std::unordered_map 慢在哪里？每次查找跟着指针跳来跳去，缓存全部打飞。Google 的 Swiss Table 用 SSE2 一条指令并行比较 16 个槽位，把哈希表的探测从'逐个比较'变成了'批量筛选'。这篇文章从控制字节的位级设计讲到完整 C 实现，拆解这个替换了 Google 全部 C++ 哈希表的方案。
完美哈希：从理论到 gperf 实践
编译器怎么在 O(1) 时间内判断一个标识符是不是关键字？用哈希表？但普通哈希表有冲突，最坏情况退化成链表。完美哈希给出了确定性答案：对已知的 n 个键，构造一个完全无冲突的哈希函数，查找时间严格 O(1)，空间 O(n)。这是静态字典问题的终极解法。
素性测试与工业级素数生成
RSA 的安全性始于一个问题：如何快速找到大素数？
扩展欧几里得与模逆元
一个两千年前的算法，仍然是现代密码学的基石。
格基规约（LLL）：后量子密码的战场
LLL 算法是密码分析中最强大的工具之一。
有限域算术：从 AES 到 Reed-Solomon
有限域是密码学和纠错编码共同的数学基础。
椭圆曲线算术：群论视角
椭圆曲线密码学的数学核心，比你想象的更优雅。
DFA 最小化：词法分析器生成的核心
每个正则表达式引擎背后，都有一个 DFA 最小化算法在工作。
LR 与 LALR 解析：从理论到 yacc/bison
LR 解析是编译器前端最重要的算法，没有之一。
PEG 解析与 Packrat：无限前瞻的代价
PEG 用确定性选择解决了 CFG 的歧义问题，但代价是什么？
寄存器分配：图着色与线性扫描
寄存器分配是编译器后端对程序性能影响最大的优化。
SSA 形式与编译器优化
SSA 是现代编译器 IR 的核心表示形式。从支配树到 φ 函数，理解 SSA 的构造和优化是深入编译器的必经之路。
一致性哈希：不要相信教科书版本
你在教科书上学到的一致性哈希——哈希环加虚拟节点——在生产环境中其实很糟糕。内存爆炸、负载不均、rebalance 元数据传播慢。Google 早在 2014 年就用 Jump Consistent Hash 干掉了它，2016 年又用 Maglev Hash 统治了网络负载均衡。是时候更新你的知识库了。
垃圾回收算法全景
从引用计数到并发三色标记，从分代假说到 ZGC 的亚毫秒暂停。垃圾回收是编程语言运行时中最复杂也最精妙的子系统。
缓存无关算法：让硬件替你优化
缓存无关算法不需要知道缓存的大小和行宽，却能自动在所有缓存层级上达到最优性能。这个优美的理论模型对实践有多大指导意义？
无分支编程：当 if 成为性能杀手
现代 CPU 的分支预测器已经非常精准，但当预测失败时代价高昂。无分支编程用算术和位运算消除条件跳转，在特定场景下带来数倍加速。
SIMD 算法设计模式
SIMD 不只是'把标量操作变成向量操作'那么简单。从 SoA 布局到 pshufb 查表，掌握这些设计模式才能真正释放向量化的威力。
随机化算法：当运气成为武器
随机化不是偷懒，而是一种强大的算法设计范式。从 Karger 最小割到 Schwartz-Zippel 引理，随机性让许多困难问题变得出人意料地简单。
竞争分析与在线算法
当你必须在信息不完整时做出不可撤销的决策，最坏情况下能做到多好？竞争分析给出了在线算法性能的严格数学框架。
Bloom Filter 全家族：Standard → Counting → Cuckoo → Ribbon
一个 1970 年诞生的数据结构，至今仍是现代数据库、网络设备和分布式系统的基石。从 Burton Bloom 的原始论文到 Meta 在 2021 年推出的 Ribbon Filter，这个家族用概率换空间的哲学从未过时。
密码学哈希 vs 非密码学哈希：设计哲学的分野
为什么 Python 3.3 突然把字典的哈希函数换成了 SipHash？为什么 Rust 的默认 HashMap 不用最快的 wyhash 而用 SipHash-1-3？当你的哈希表面向不可信输入时，速度最快的哈希函数可能是最危险的。
向量化哈希：xxHash3 与 wyhash 的 SIMD 实现
当你的数据以 GB/s 的速度涌入，哈希函数往往成为瓶颈。xxHash3 用 AVX2 把 8 个累加器打包成 256-bit 向量同时处理；wyhash 则用一条 128-bit 乘法做到几乎同样的吞吐。这篇文章拆解这两个顶级非密码学哈希的 SIMD 设计。
红黑树 vs AVL：Linux 内核为什么选红黑树
AVL 树的平衡更严格、查找更快，为什么 Linux 内核、Java TreeMap、C++ std::map 全都选了红黑树？这个问题的答案不在教科书里——它藏在旋转次数的精确分析和 cache line 的物理约束中。
B-tree 深度解剖：从磁盘 I/O 模型到 boltdb 源码
每一个你信赖的数据库背后，都站着一棵 B-tree。本文从磁盘物理模型出发，逐层拆解 B-tree 与 B+tree 的设计动机、节点分裂与合并的完整过程、批量加载优化、写放大计算，并深入 boltdb 源码与完整的 C 实现，最终落地到 InnoDB、PostgreSQL、SQLite 等工业级变体的工程细节。
B+tree 与 LSM-tree：两种存储引擎哲学的碰撞
数据库存储引擎的核心之争——原地更新还是追加写入？B+tree 与 LSM-tree 代表了两种截然不同的设计哲学，理解它们的取舍，就是理解现代存储系统设计的根基。
线段树与树状数组：区间问题的优雅武器
当你第一次看到 O(log n) 内完成区间求和与区间修改时，很难不为这两棵树的设计之精巧而感到震撼。线段树用递归分治将区间层层拆解，树状数组用二进制索引在数组上翩翩起舞——它们是算法竞赛与工业系统中处理区间问题的两把最优雅的武器。
持久化数据结构：函数式世界的基石
不可变性不只是一种约束，它是一种设计哲学。持久化数据结构让我们在保留所有历史版本的同时，以接近原地修改的效率进行更新——它是函数式编程、版本控制系统乃至分布式数据库背后的核心抽象。
Merkle 树与认证数据结构：从 Git 到区块链
在不可信的网络环境中，我们如何仅凭一个哈希值就能验证 TB 级数据的完整性？Merkle 树给出了一个优雅到令人惊叹的答案。
后缀数组：比后缀树更实用的选择
后缀数组用更少的内存做到了后缀树能做的几乎一切。
AC 自动机：多模式匹配与入侵检测系统
当你需要同时搜索上万个模式串，AC 自动机是唯一的答案。
BWT 与 FM-index：从 bzip2 到基因组比对
Burrows-Wheeler 变换是字符串算法中最美的发明之一。
编辑距离与模糊匹配：搜索引擎的纠错秘密
你在搜索框打错字，搜索引擎为什么还能理解你？
字符串哈希：Rabin-Karp 与滚动哈希
滚动哈希是字符串匹配中最被低估的技术。
SIMD 字符串处理进阶
用向量指令重写字符串操作，性能提升 10 倍不是梦。
Unicode 算法：UTF-8 的精妙与文本处理陷阱
大多数程序员对 Unicode 的理解停留在表面，直到他们踩坑。
HyperLogLog：用 12KB 统计十亿基数
如何用仅仅 12KB 的内存估计十亿级别的基数？从 Flajolet-Martin 的直觉到 HyperLogLog 的数学证明，概率数据结构的精妙令人叹服。
Count-Min Sketch：流式频率估计的瑞士军刀
在无限数据流中统计每个元素的出现频率，精确计数需要无限内存。Count-Min Sketch 用亚线性空间给出有理论保证的近似答案。
t-digest：分布式系统中的分位数估计
监控系统的 P99 延迟是怎么算出来的？t-digest 用巧妙的质心压缩在亚线性空间中给出准确的分位数估计，尤其在尾部保持高精度。
水塘抽样：未知大小数据流的公平抽样
面对一个不知道有多长的数据流，如何保证每个元素被等概率选中？水塘抽样用一个优雅的不变量解决了这个看似不可能的问题。
MinHash 与 SimHash：海量文本相似度检测
在数十亿网页中找出近似重复的内容，逐对比较需要天文数字的计算量。MinHash 和 SimHash 用概率方法将复杂度从 O(n^2) 降到近线性。
频率估计的理论极限：Space-Saving 与 Misra-Gries
在无限数据流中找出出现频率最高的元素，只用有限内存能做到多精确？从 Misra-Gries 的消消乐到 Space-Saving 的最优实践。
流式算法总论：亚线性空间的艺术
当数据以每秒百万条的速度涌来，你只能看一遍且内存有限。流式算法用亚线性空间在这个严苛约束下给出令人惊叹的近似答案。
KD-tree：低维空间的分治之道
在低维空间中，KD-tree 仍然是最实用的空间索引。
局部敏感哈希（LSH）：高维近邻的概率方法
当维度诅咒让精确搜索绝望时，LSH 给出了概率保证。
HNSW：图索引如何击败树索引
HNSW 是当前向量检索的事实标准算法。
乘积量化与 IVF-PQ：十亿向量的工业级检索
当向量数据集大到连 HNSW 都装不下内存，IVF-PQ 是最后一道防线。
ScaNN 与 DiskANN：两大厂的向量检索之路
Google 和 Microsoft 分别给出了向量检索的不同答案。
从零实现一个向量搜索引擎
把前几篇的算法组装起来，构建一个真正可用的向量检索系统。
Dijkstra 与 A*：从优先队列到路径规划
最短路径算法是图论中最有工程价值的分支。
Bellman-Ford 与路由协议
Bellman-Ford 不只是一个最短路算法，它是距离向量路由的灵魂。
最小生成树：Kruskal 与 Prim 的工程权衡
MST 算法的选择，本质上是边排序和优先队列之间的权衡。
Tarjan 算法族：SCC、割点、桥的统一框架
Robert Tarjan 用 DFS 统一解决了一系列图论经典问题。
网络流与二分匹配
网络流是组合优化中最优美的理论之一。
拓扑排序：依赖解析的核心
从 Make 到 Webpack，每个构建系统的核心都是拓扑排序。
PageRank 与随机游走：搜索引擎的数学基础
PageRank 不只改变了搜索引擎，它改变了我们理解网络的方式。
图着色与寄存器分配
图着色问题是 NP 完全的，但编译器每天都在解决它。
内存分配器对决：jemalloc vs tcmalloc vs mimalloc
你的服务在线上跑了三天，RSS 从 2GB 涨到了 6GB，free 显示内存快爆了，但业务量没变。你重启'修好了'，然后下周又涨回去。问题不在你的代码里——问题在 malloc 里。
页面置换算法：LRU 的谎言与 ARC 的真相
教科书说 LRU 是最好的页面置换算法。然后你在数据库上跑了一次全表扫描，热数据全被冲走了。本文从 Bélády 的最优算法出发，逐层揭示 LRU 的理论缺陷，到 CLOCK 的工程妥协，再到 ARC 的自适应智慧。
进程调度：从 CFS 到 EEVDF 的哲学演变
你把 nice 值设成了 -20，然后发现延迟反而更高了。你用 cgroup 限了 CPU，然后发现交互式 shell 卡成幻灯片。调度器不是'谁优先级高谁先跑'这么简单——它是操作系统中最复杂的博弈论。
I/O 调度：CFQ → mq-deadline → BFQ → kyber
你把数据库从 HDD 迁移到了 NVMe SSD，IOPS 涨了 100 倍——然后你发现 I/O 调度器还在用 CFQ，它正在用复杂的算法把你的 NVMe 搞慢。NVMe 时代，最好的调度器可能是'不调度'。
伙伴系统与 SLUB 分配器：Linux 物理内存管理的两层架构
你调用 kmalloc(64, GFP_KERNEL)，内核在 3 微秒内给了你 64 字节。背后是两层精密的机械：伙伴系统管理物理页面，SLUB 把页面切碎成小对象。这两层如何配合？各自解决了什么问题？
文件系统的树：从 ext4 extent tree 到 btrfs CoW B-tree
你的 ext4 文件系统上有一个 1TB 的数据库文件。内核如何在 O(log n) 时间内找到文件偏移量 847,293,510,144 对应的物理磁盘块？答案藏在 extent tree 里。
epoll 的数据结构：红黑树、就绪队列与回调机制
Nginx 用一个进程处理 10 万个并发连接，核心就是 epoll。但 epoll 的 O(1) 性能不是魔法——它用红黑树存储监控集合，用链表收集就绪事件，用回调避免轮询。三个数据结构各司其职，精妙得像一台钟表。
定时器算法：时间轮、最小堆与层级时间轮
一台繁忙的 Nginx 服务器上有 100 万个活跃连接，每个连接都有 keepalive 超时定时器。如果用最小堆管理这些定时器，每次新连接到来都要 O(log n) 插入——100 万个定时器意味着 20 次比较。时间轮用 O(1) 解决了这个问题。
Join 算法全解：Nested Loop → Hash → Sort-Merge
数据库中最昂贵的操作，可能就是 Join。
查询优化器：从 System R 到 Cascades
SQL 声明式表达背后，是一场持续五十年的搜索空间探索。
缓冲池管理算法：LRU-K → 2Q → CLOCK-Pro
每个数据库工程师都该理解的内存管理核心。
WAL 与 ARIES 恢复算法
崩溃恢复是数据库最被低估的核心能力。
LSM-tree Compaction 策略
Compaction 是 LSM-tree 的心脏，也是它最大的痛点。
MVCC 实现变体全解
MVCC 是数据库并发控制的事实标准，但每家的实现天差地别。
学习索引：当机器学习遇上数据库
Kraska 2018 年的论文像一颗炸弹，震动了整个数据库社区。
TCP 拥塞控制：从 Reno 到 BBRv3
拥塞控制是互联网能正常运转的底层原因。
滑动窗口与流控的算法本质
滑动窗口不只是一道 LeetCode 题型，它是网络协议、流控、限流的通用模式。
负载均衡算法：P2C / EWMA / 平滑加权轮询
负载均衡看似简单，实则处处是坑。
路由算法：距离向量 vs 链路状态 vs 路径向量
互联网的路由表是人类建造的最大分布式数据结构。
主动队列管理：RED → CoDel → FQ-CoDel
Bufferbloat 是互联网延迟的隐形杀手。
无锁队列：Michael-Scott 算法与 ABA 问题
当多线程争抢一把 mutex 保护的队列时，吞吐量随线程数增长反而下降——锁成了瓶颈。无锁队列用 CAS 循环取代互斥，换来真正的无阻塞并发，但也引入了 ABA 问题和内存回收的工程深渊。
无锁栈：Treiber 栈与指数退避
Treiber 栈可能是最简单的无锁数据结构——只需要一个 CAS 操作就能完成 push 和 pop。但'最简单'不意味着'没有坑'。从 ABA 问题到伪共享，从指数退避到 elimination backoff，这个看似朴素的数据结构蕴含了并发编程最核心的设计权衡。
并发跳表：ConcurrentSkipListMap 的设计
Java 的 `java.util.concurrent` 提供了 ConcurrentHashMap，却没有 ConcurrentTreeMap——取而代之的是一个基于跳表的 ConcurrentSkipListMap。为什么 Doug Lea 选择了跳表而不是红黑树？因为平衡树的旋转操作会同时修改多个节点的指针，在并发场景下几乎不可能做到无锁；而跳表天然的分层链表结构使得每次修改只涉及局部指针，为 CAS 操作提供了完美的施展空间。
Epoch-Based Reclamation：Crossbeam 的实现之道
在无锁编程的世界里，内存回收是最棘手的难题之一。Rust 的 crossbeam 库用基于纪元的回收机制，巧妙地将这一难题化解为三个整数的优雅舞蹈——本文从原理到工程实践，完整剖析这一精妙的并发内存回收技术。
RCU：Linux 内核的读侧零开销并发
Linux 内核如何在并发数据结构中实现读侧零开销？RCU 用一种违反直觉的方式回答了这个问题：让读者永远不等待，让写者承担一切代价。
并发哈希表：从分段锁到无锁设计
Java ConcurrentHashMap 从 16 段分段锁演进到 CAS+TreeBin，再到 Cliff Click 的全无锁方案——并发哈希表的二十年进化史，是一部在吞吐量与正确性之间反复拉扯的工程史诗。
MPMC Channel：Go channel 与 crossbeam-channel 的实现对比
同一个并发原语，Go 和 Rust 却走出了截然不同的道路：一个用全局互斥锁守护环形缓冲区，另一个用逐槽位 CAS 实现无锁推进。本文深入拆解 Go channel、crossbeam-channel、LMAX Disruptor 和 DPDK rte_ring 的内部结构，并给出一份完整的 C 语言有界 MPMC 队列实现。
Huffman 编码与 DEFLATE
从信息论到 gzip：最经典的压缩算法组合。
LZ77/LZ78/LZW：字典压缩的两条路线
Lempel 和 Ziv 在 1977 年开启了字典压缩的时代。
zstd 深度解剖：FSE 与字典训练
Yann Collet 的杰作：同时赢得速度和压缩率。
算术编码与 ANS：超越 Huffman
当 Huffman 的整数比特限制成为瓶颈，算术编码打破了这道墙。
整数压缩：varint → PForDelta → SIMD-BP128
搜索引擎的倒排索引压缩，是整数压缩最大的战场。
时序数据压缩：Gorilla 编码与 Delta-of-Delta
Facebook 的 Gorilla 论文改变了时序数据库的压缩格局。
凸包算法：Graham Scan、Andrew 与 Chan 的进化
从 Graham Scan 的极角排序到 Chan 算法的 output-sensitive 最优性，凸包问题展示了计算几何算法设计的精妙思维。
扫描线算法：从线段交到矩形面积并
扫描线是计算几何中最通用的算法范式——用一条虚拟的线从左到右扫过平面，将二维问题降维为一维动态问题。
Voronoi 图与 Delaunay 三角剖分：对偶的力量
Voronoi 图和 Delaunay 三角剖分是计算几何中最优美的对偶结构。从最近邻查询到有限元网格生成，它们的应用无处不在。
R-tree 与空间索引：PostGIS 的底层结构
地理信息系统如何在数百万个多边形中快速找到附近的餐厅？R-tree 用层级化的边界矩形将空间搜索从暴力扫描变为对数级查询。
点定位与梯形分解
给定一个被线段划分的平面，如何快速确定一个查询点落在哪个区域？梯形分解用随机增量法构建 O(log n) 查询的优雅结构。
最近点对与随机化几何算法
在 n 个点中找最近的一对，暴力需要 O(n^2)。分治法将其优化到 O(n log n)，而 Rabin 的随机化方法更进一步达到期望 O(n)。
树形 DP：换根、虚树与树上背包
树形 DP 是动态规划中最优美的分支之一。换根技巧将复杂度从 O(n^2) 降到 O(n)，虚树将多次查询的总复杂度压缩到关键点规模。
状压 DP：用位运算驯服指数空间
当问题的状态空间是集合的幂集时，位运算提供了优雅的压缩表示。从 TSP 到 SOS，状压 DP 是处理 NP-hard 问题精确解的核心武器。
斜率优化与凸包技巧
当 DP 转移方程可以写成线性形式，凸包技巧将 O(n^2) 优化到 O(n log n) 甚至 O(n)。这是竞赛和工业优化中最强大的 DP 加速手段之一。
分治优化 DP：决策单调性的力量
当 DP 的最优决策点具有单调性时，分治技巧可以将 O(n^2) 优化到 O(n log n)。四边形不等式是识别这种结构的关键数学工具。
区间 DP 与矩阵链乘
区间 DP 是处理'在区间上做最优决策'问题的通用框架。从矩阵链乘到 RNA 折叠，它的应用远比教科书展示的更广泛。
DP 在工业界：资源调度、广告投放与路径规划
动态规划不只是算法竞赛的工具。从广告预算分配到 GPS 轨迹匹配，DP 的思想在工业系统中以各种形式默默运行着。
快速傅里叶变换：从多项式乘法到信号处理
FFT 是 20 世纪最重要的算法之一，没有之一。
基数排序：打破比较下界的正确姿势
比较排序有 O(n log n) 的理论下界，基数排序如何绕过这个限制？它在什么场景下真正有优势，又为什么没有成为通用排序的首选？
列式压缩：RLE / Dictionary / FSST
列式存储的压缩率优势，本质上是数据局部性的胜利。
限流算法：令牌桶 / 漏桶 / GCRA
限流是分布式系统的第一道防线。
Van Emde Boas 树：当 O(log log n) 不只是理论
打破 O(log n) 的壁垒——深入 Van Emde Boas 树的递归宇宙分裂、O(log log U) 全操作复杂度、以及它在操作系统调度器中的真实回响
Treap 与跳表：随机化的力量
当我们放弃对确定性平衡的执念，转而拥抱随机化，会发现一些最优雅的数据结构——Treap 用一个随机优先级就消除了旋转的痛苦，跳表用抛硬币就实现了对数级查找。这不是妥协，而是对概率论最精彩的工程应用。
Hazard Pointers：安全内存回收的优雅方案
在无锁数据结构中，你不能简单地 free() 一块内存——因为另一个线程可能正在读取它。Hazard Pointers 是解决这个问题的经典方案。
记录历史：持久化数据结构
持久化数据结构原理与实现：探索 undo/redo、MVCC、Git 等系统背后的数据结构设计模式
关于二分查找算法
二分查找算法详解：原理、实现、变种及常见错误分析，O(log n) 时间复杂度的高效搜索算法
如何计算高频页面
Heavy Hitters 算法：如何高效计算高频数据项，在流式数据处理和热门页面统计中的应用
手把手教你用 C++ 写一个简单的 JSON 解析器
从零开始实现一个基于有限状态机（FSM）的 JSON 解析器。不依赖第三方库，深入理解词法分析与语法分析的核心思想。
字符串匹配算法: kmp和bm算法
字符串匹配算法深度解析：KMP 和 Boyer-Moore 算法原理、实现与性能对比
正则表达式性能优化与 ReDOS 防御实战
深入探讨正则表达式的回溯机制导致的性能问题，详解 ReDOS 攻击原理与防御策略，并分享生产环境中的真实排查案例。
正则表达式
正则表达式原理与实现：从理论到实践，深入理解正则表达式引擎的工作机制
SIMD 加速字符串查找（strchr / strstr）系统指南
面向工程实践的SIMD字符串查找优化完全指南：SSE2/AVX2/AVX-512并行比较原理，位掩码技巧，跨块与页边界安全处理，strchr/strstr高性能实现，包含完整代码示例和性能陷阱分析
交互式演示：NFA 引擎是如何工作的
通过交互式动画，直观演示非确定性有限自动机（NFA）匹配字符串的步进过程，揭示正则引擎的内部奥秘。