lru-cache

LRU 缓存淘汰算法

摘要：LRU（Least Recently Used，近期最少使用）是一种常用的缓存淘汰算法，核心思路是当缓存满时优先淘汰最久未被访问的数据。

来源：raw/技术/LRU 算法.md

最后更新：2026-06-27

基本原理

LRU 基于"时间局部性"原理：如果一个数据最近被访问过，那么它在未来被再次访问的概率也更高。因此，缓存满时淘汰最久未被访问的数据。

实现方式

常见实现使用哈希表 + 双向链表：
- 哈希表：O(1) 时间查找数据是否存在
- 双向链表：O(1) 时间移动数据到头部或删除尾部

每次访问数据时，将其移到链表头部；缓存满时，删除链表尾部的数据。

应用场景

• CPU 缓存
• 操作系统页面置换
• 数据库缓冲池
• Web 缓存（如 Redis 的近似 LRU）

相关页面

• 快慢指针技巧——链表算法中的经典技巧
• 元胞自动机（计算理论）