LRU 算法原理

Mar 14, 2025 · 1 min read · 算法

LRU（Least Recently Used）算法的核心原理是淘汰最近最少使用的数据，基于“如果一个数据最近未被访问，未来被访问的概率也较低”的假设。其实现依赖于高效的数据结构来维护访问顺序，以下是详细解析：

一、基本原理

淘汰策略
LRU优先淘汰最久未被访问的数据。例如，在缓存满时，新数据插入会触发淘汰机制，移除链表中最后一位（即最近未被使用的数据）。
局部性原理支持
程序运行过程中，数据的访问往往呈现时间局部性（近期访问的数据可能再次被访问）。LRU通过记录访问顺序，最大化利用这一特性以提高缓存命中率。

二、关键数据结构

LRU的高效实现依赖哈希表 + 双向链表的组合：

哈希表：提供O(1)时间复杂度的键值查询，快速定位数据是否存在。
双向链表：维护数据的访问顺序，头部存放最新访问的数据，尾部存放最久未访问的数据。

操作示例：

访问数据：若数据存在，将其移动到链表头部。
插入数据：
- 若存在则更新值并移动到头部；
- 若不存在且缓存已满，删除尾部数据，再插入新数据到头部。

三、应用场景

操作系统页面置换
管理物理内存与虚拟内存的页面置换，减少缺页中断。
数据库缓存
如Redis的缓存淘汰策略，提升查询效率。
Web服务缓存
高频访问的数据驻留内存，降低数据库压力。

四、优缺点分析

优点：
- 高命中率：适合局部性明显的场景。
- 实现相对简单：数据结构成熟，逻辑清晰。
缺点：
- 维护成本高：频繁移动链表节点增加开销。
- 偶发访问干扰：若某冷数据突然被访问，可能误保留。

通过结合哈希表的快速查询与链表的顺序维护，LRU在时间和空间复杂度上达到平衡，成为实际系统中广泛应用的淘汰策略。具体实现时需根据场景权衡性能与资源消耗。