C++ 高性能定时器
定时器是后端开发中的基础组件，广泛应用于超时控制、定时任务、心跳检测等场景。一个优秀的定时器需要支持高效插入、快速取消和准时触发，同时能管理海量定时任务。本文将深入探讨两种经典实现方案：分层时间轮和最小堆+哈希表，并通过可视化图表阐明其核心思想。
1. 基础结构：哈希表 + 双向链表
最直观的实现是使用一个双向链表按超时时间排序，并用哈希表辅助快速定位任务。
数据结构
- 双向链表：按超时时间升序排列，每个节点包含任务回调、超时时间、任务ID。
- 哈希表：以任务ID为键，存储链表节点指针。
操作复杂度
- 插入：需遍历链表找到合适位置，最坏 O(n)。
- 删除：通过哈希表找到节点，从链表中移除，O(1)。
- tick 处理：每次时钟嘀嗒检查链表头部，若超时则触发并移除，O(1) 均摊。
瓶颈
插入性能随任务数线性下降，无法支撑大规模场景。
2. 方案一：分层时间轮（按 interval 粒度分组）
为了突破插入 O(n) 的瓶颈，可以将时间划分为多个精度层次，每个层是一个环形数组（时间轮），数组每个槽挂载一个双向链表。
这相当于按超时间隔粒度分组：例如 10ms 组、100ms 组、1s 组……任务根据剩余时间放入对应层的槽中。
数据结构
- 多层时间轮：第一层精度 1ms，64 个槽；第二层精度 64ms，64 个槽；第三层精度 4096ms，以此类推。
- 哈希表：记录任务 ID 所在的层、槽及链表节点，用于 O(1) 取消。
操作流程
- 插入：根据超时时间计算所属层和槽，直接挂入对应双向链表尾部，O(1)。
- 删除：通过哈希表定位节点，从所在链表中移除，O(1)。
- tick：每 1ms 移动第一层指针，处理当前槽的全部任务；若第一层转完一圈，将第二层当前槽的任务“降级”到第一层对应槽，依次类推。均摊 O(1)。
优点
- 所有操作常数时间，与任务总数无关。
- 内存固定，适合海量短时任务（如网络连接超时）。
3. 方案二：最小堆 + 哈希表（结合二分查找思想）
另一种思路是让所有任务按超时时间全序排列，利用最小堆或平衡树实现 O(log N) 插入，并配合哈希表实现快速取消。
数据结构
- 最小堆：用数组实现的完全二叉树，堆顶始终是最近超时的任务。
- 哈希表：记录任务 ID 在堆数组中的索引，便于删除时定位。
操作复杂度
- 插入：将新任务放入堆尾，向上调整（上浮），O(log N)。
- 删除：通过哈希表找到任务在堆中的位置，用堆尾元素覆盖并向下/向上调整，O(log N)。
- tick：不断检查堆顶是否超时，若是则弹出并向下调整，O(log N) 均摊。
优点
- 实现简单，内存紧凑（数组），适合任务数适中的通用场景。
- 支持范围查询（如取所有超时时间小于当前时间的任务）。
4. 两种方案
| 维度 | 分层时间轮 | 最小堆 + 哈希表 |
|---|---|---|
| 插入时间复杂度 | O(1) | O(log N) |
| 删除时间复杂度 | O(1) | O(log N) |
| tick 处理 | O(1) 均摊 | O(log N) 均摊（需多次弹出） |
| 内存占用 | 固定数组 + 链表节点 | 动态数组（堆） + 哈希表 |
| 适用场景 | 海量短时任务（如百万级连接超时） | 任务数适中，要求简单实现 |
| 实现复杂度 | 稍复杂（需处理层级降级） | 简单（标准堆实现） |
| 时间环绕处理 | 多层自动解决 | 需用绝对时间比较，无环绕问题 |
5. 特别说明
没有万能的定时器，只有最适合场景的设计：
- 若需要管理数十万甚至百万级的短期定时任务，且对性能有极致要求，分层时间轮是首选（如 Netty、Kafka）。
- 若任务数量适中（几千以内），代码简洁性更重要，最小堆+哈希表完全够用（如 Redis、Linux 内核早前定时器）。
- 两种方案都借助哈希表实现了 O(1) 的任务取消，这是高性能定时器的关键辅助结构。
