读书使人进步。
数据结构
位掩码 (Bitmask)
将多个布尔标志打包到一个整数中,通过位运算实现常数时间的集合操作。
最小堆 / 优先队列 (Min Heap)
存储在数组中的二叉树,最小元素始终在根节点,支持 O(1) 查看和 O(log n) 插入/删除。
环形缓冲区 (Ring Buffer)
固定大小的缓冲区通过模运算实现循环,提供常数时间的入队出队且无需内存分配。
Trie 前缀树 (Trie / Prefix Tree)
在树中存储字符串,每条边代表一个字符——共享前缀共享节点,实现按键长度 O(k) 查找。
跳表 (Skip List)
概率有序数据结构,O(log n) 搜索、插入和删除——比平衡树更简单,性能相当。
布隆过滤器 (Bloom Filter)
以 O(k) 时间测试集合成员资格,零漏判——代价是可调的误判率。
LRU 缓存 (LRU Cache)
缓存满时淘汰最近最少使用的条目——用哈希表加双向链表实现 O(1) 的 get 和 put。
B+ 树 (B+ Tree)
自平衡多路树,高扇出——内部节点负责路由,叶节点存储数据,所有叶节点通过链表相连以支持高效范围扫描。
标签联合体 (Tagged Union / Variant)
将类型标签与值联合体配对存储,使一个变量安全地持有不同类型,通过标签分发行为。
Merkle 树 (Merkle Tree)
对叶子节点做哈希,然后逐层向上哈希配对——以 O(log n) 的代价验证任意叶子的完整性,无需重新哈希整个数据集。
合并迭代器 (Merge Iterator / K-Way Merge)
使用最小堆将 K 个有序流合并为一个有序输出——跨多个数据源创建”统一视图”的通用方法。
并发
信号量 / 有界并发 (Semaphore)
通过维护计数器限制并发操作数量——工作前获取,完成后释放,达到上限时阻塞。
Actor 模型
每个 Actor 拥有一个信箱并按顺序处理消息——没有共享状态,没有锁,仅通过消息传递实现安全并发。
工作窃取 (Work Stealing)
空闲线程从繁忙线程的队列中窃取任务——无需中央协调即可动态均衡负载。
MVCC 多版本并发控制
为每个值保留多个带时间戳的版本,读者永远不阻塞写者——每个事务看到一致的快照,无需加锁。
协作调度 (Cooperative Scheduling)
将长时间运行的任务拆分为小块,在每块之间让出控制权,以保持系统响应。
双缓冲 (Double Buffering)
维护两份状态副本,在它们之间原子切换,让读取方始终看到一致的快照。
背压 / 流控 (Backpressure)
当消费者跟不上时减慢生产者——用有界缓冲区和需求信号防止资源耗尽。
事件循环 / 反应器 (Event Loop / Reactor)
单线程循环通过 epoll/kqueue 多路复用 I/O,将就绪事件分发给回调——无需线程即可处理数千连接。
逻辑时钟 / Epoch (Logical Clock)
单调递增的计数器,无需物理时钟即可排序事件——实现一致性快照和过期检测。
系统
熔断器 (Circuit Breaker)
通过跟踪错误次数自动跳闸——快速失败,而不是堆积超时等待。
限流器 / 令牌桶 (Rate Limiter)
通过维护一个按固定速率补充的令牌桶来控制吞吐量——每次操作消耗一个令牌,桶空时拒绝请求。
指数退避重试 (Retry with Backoff)
操作失败时以指数增长的延迟重试,加随机抖动避免惊群效应。
预写日志 (Write-Ahead Log)
在应用变更前先将每个变更记录到持久存储——重放日志即可从崩溃中恢复,零数据丢失。
批处理 (Batch Processing)
累积单个操作并作为一组执行,将每次操作的开销分摊到整个批次。
一致性哈希 (Consistent Hashing)
将键分布到虚拟环上的节点,添加或移除节点时只重映射约 1/n 的键。
依赖图 (Dependency Graph)
将依赖关系建模为有向无环图,拓扑排序确定合法执行顺序——在死锁前检测循环。
中间件 / 管道链 (Middleware / Pipeline Chain)
组合处理器,每个包裹下一个——前处理、调用 next、后处理——形成双向管道。
注册表 / 自注册 (Registry)
组件按名称将自身注册到全局查找表——消费者在运行时发现实现,无需硬编码依赖。
脏标记 (Dirty Flag)
在变更时将对象标记为”脏”,延迟昂贵的重计算直到值真正被需要时再执行,然后清除标记。
LSM 树 (Log-Structured Merge Tree)
将写入缓冲在内存中,刷写到磁盘的有序文件,后台合并文件——用读放大换取快速写入。
检查点 (Checkpointing)
定期快照一致性状态,使恢复只需从检查点开始重放——而不是从时间的起点。
内存
对象池 (Object Pool)
预分配一组可复用对象,避免热路径上重复分配和垃圾回收的开销。
对象池 (Object Pool)
共享相同的不可变对象而非创建重复实例,用查找开销换取大量内存节省。
Arena 分配器 (Arena Allocator)
在预分配区域中通过移动指针分配对象——不再需要时一次性释放所有内存。
空闲链表 (Free List)
维护一个已释放槽位的链表,使分配和释放都是 O(1)——复用内存而无需调用系统分配器。
写时复制 (Copy-on-Write)
通过引用共享数据,直到有人修改时才创建私有副本——为读多写少的场景节省内存和分配开销。
引用计数 (Reference Counting)
通过原子计数器追踪所有者,归零时自动清理——无需垃圾回收的确定性资源生命周期管理。
墓碑 / 延迟删除 (Tombstone)
用墓碑标记代替直接删除条目——后台进程稍后回收空间。
驻留 / 符号表 (Interning / Symbol Table)
通过规范化查找表去重不可变值——用 O(1) 的指针比较替代 O(n) 的内容比较。
行为型
状态机 (State Machine)
将实体的生命周期建模为一组状态和显式转换,让不可能的状态不可表达,每次状态变更可审计。
观察者 / 发布-订阅 (Observer / Pub-Sub)
让对象订阅事件并在事件发生时收到通知,实现生产者与消费者的解耦——发送方不需要知道谁在监听。
迭代器 / 惰性求值 (Iterator)
逐个处理序列中的元素而不实例化整个集合,通过可组合的转换实现零中间分配。
差异/补丁 (Diff / Patch)
比较两个序列,计算将一个转换为另一个所需的最小操作集(插入、删除、移动)。
虚函数表 / 操作分发 (Vtable / Ops Dispatch)
将函数指针组合到结构体中实现运行时多态——接口、trait 和虚方法背后的手动基础。
访问者 / 树遍历器 (Visitor / Tree Walker)
将树遍历与操作解耦,通过分发到类型特定的回调——使新操作无需修改树结构。
参考链接
- Battle-Tested Patterns,by totoro-jam.