读书使人进步。
数据结构
位掩码 (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)
单调递增的计数器,无需物理时钟即可排序事件——实现一致性快照和过期检测。
参考链接
- Battle-Tested Patterns,by totoro-jam.