过期变量自动剔除需内嵌时间戳于节点结构并采用懒清理机制。每次get/put后仅从链表尾部遍历删除过期节点,遇首个未过期即止;超限时先过期清理再lru淘汰;可辅以低优先级协程定期抽检头部节点。
过期变量自动剔除不能靠定时扫描全量链表实现,否则每次 get/put 都会退化成 o(n),违背实时性要求。核心是把时间维度“内嵌”进节点结构,并配合访问驱动的轻量清理节奏。
节点必须自带时间戳
时间信息不能只存在外部哈希表或全局时钟里——链表节点移动、删除、重排序时,时间字段必须跟着走。推荐用 std::chrono::steady_clock::time_point 直接存入自定义节点结构体,确保时间与数据生命周期严格绑定。裸指针或分离存储会导致 erase 时无法判断该删哪个时间点,最终漏清或误删。
懒清理:只查尾部,删到第一个未过期为止
每次 put 或 get 操作后,检查双向链表尾部(即最久未用位置)的若干节点:
- 从尾向头遍历,逐个比对节点内嵌时间戳与当前时间
- 遇到第一个未过期节点就停止,不再继续往前扫
- 把途中所有已过期节点从链表和哈希表中一并移除
这样既避免了全链表遍历开销,又防止尾部堆积大量过期项导致缓存“虚胖”。
定向剔除保障容量硬约束
当缓存 size 超限时,LRU 剔除逻辑仍以链表尾为起点,但此时不看时间,只按访问顺序淘汰最久未用项。这个过程和过期清理正交——过期优先于容量淘汰执行,即先清掉所有已过期节点,再看是否还需按 LRU 补删。两者共用同一套双向链表结构,但触发条件和判断依据不同。
Redis 的组合策略可作工程参考
Redis 实际采用“惰性 + 定期”双路机制:访问键时惰性检查并删;后台线程定期抽样清理。这种设计对实时数据流有启发意义——你的链表处理模块也可以分两层:
- 主流程中做尾部懒清理(对应惰性)
- 另起低优先级协程,每隔几秒扫描链表头部 5% 节点做定向过期抽检(对应定期)
不强求一次清完,但保证过期项不会滞留超过数秒,兼顾响应延迟与内存水位。










