一种高效的缓存淘汰策略，基于"时间局部性"原理，
在有限的空间内保留最具价值的数据。
LRU (Least Recently Used)，中文意为“最近最少使用”。 它的核心思想非常朴素且直观：如果数据最近被访问过，那么将来被访问的几率也更高。
当缓存空间已满，需要淘汰旧数据以腾出空间给新数据时，LRU 策略会选择最久未被访问的数据进行淘汰。 这种策略广泛应用于操作系统、数据库和各类应用层缓存中。
为了实现高效的 LRU 算法，我们需要在 O(1) 的时间复杂度内完成数据的查找、插入和删除。 通常采用 哈希表 (HashMap) + 双向链表 (Doubly Linked List) 的组合结构。
当访问 Key 为 X 的数据时：
当插入 Key 为 X，Value 为 V 的数据时：
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| Get(key) | O(1) | 哈希表直接定位节点，链表操作为常数时间 |
| Put(key, value) | O(1) | 哈希表插入/更新 + 链表头部插入 |
| Delete(key) | O(1) | 哈希表删除 + 链表节点移除 |
| 空间复杂度 | O(n) | n 为缓存容量，需存储 n 个节点及哈希表映射 |
哈希表的作用
双向链表的作用
// 双向链表节点类
class ListNode {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
// LRU 缓存类
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.size = 0;
this.cache = new Map(); // 哈希表，O(1) 查找
// 虚拟头尾节点，简化边界处理
this.head = new ListNode();
this.tail = new ListNode();
this.head.next = this.tail;
this.tail.prev = this.head;
}
// 将节点移到链表头部（表示最近使用）
_moveToHead(node) {
this._removeNode(node);
this._addNodeToHead(node);
}
// 从链表中移除节点
_removeNode(node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
// 在链表头部添加节点
_addNodeToHead(node) {
node.next = this.head.next;
node.prev = this.head;
this.head.next.prev = node;
this.head.next = node;
}
// 移除链表尾部节点（最久未使用）
_removeTail() {
const tailNode = this.tail.prev;
this._removeNode(tailNode);
return tailNode;
}
// 获取数据
get(key) {
const node = this.cache.get(key);
if (!node) return -1;
// 将访问的节点移到链表头部
this._moveToHead(node);
return node.value;
}
// 插入或更新数据
put(key, value) {
const node = this.cache.get(key);
if (!node) {
// 创建新节点
const newNode = new ListNode(key, value);
this.cache.set(key, newNode);
this._addNodeToHead(newNode);
this.size++;
// 检查是否超出容量
if (this.size > this.capacity) {
// 移除最久未使用的节点
const tailNode = this._removeTail();
this.cache.delete(tailNode.key);
this.size--;
}
} else {
// 更新现有节点的值，并移到头部
node.value = value;
this._moveToHead(node);
}
}
}
// 使用示例
const cache = new LRUCache(2);
cache.put(1, 1); // 缓存是 {1=1}
cache.put(2, 2); // 缓存是 {1=1, 2=2}
cache.get(1); // 返回 1，缓存变为 {2=2, 1=1}
cache.put(3, 3); // 淘汰 key 2，缓存变为 {1=1, 3=3}
cache.get(2); // 返回 -1（未找到）
cache.put(4, 4); // 淘汰 key 1，缓存变为 {3=3, 4=4}
cache.get(1); // 返回 -1（未找到）
cache.get(3); // 返回 3，缓存变为 {4=4, 3=3}
cache.get(4); // 返回 4，缓存变为 {3=3, 4=4}
class LRUCache:
def __init__(self, capacity: int):
from collections import OrderedDict
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
# 将访问的键移到最前面
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
# 更新值并移到最前面
self.cache.move_to_end(key)
self.cache[key] = value
# 检查容量
if len(self.cache) > self.capacity:
# 移除最早的项
self.cache.popitem(last=False)
# 使用示例
cache = LRUCache(2)
cache.put(1, 1) # 缓存是 {1: 1}
cache.put(2, 2) # 缓存是 {1: 1, 2: 2}
cache.get(1) # 返回 1，缓存变为 {2: 2, 1: 1}
cache.put(3, 3) # 淘汰 key 2，缓存变为 {1: 1, 3: 3}
cache.get(2) # 返回 -1（未找到）
cache.put(4, 4) # 淘汰 key 1，缓存变为 {3: 3, 4: 4}
cache.get(1) # 返回 -1（未找到）
cache.get(3) # 返回 3，缓存变为 {4: 4, 3: 3}
cache.get(4) # 返回 4，缓存变为 {3: 3, 4: 4}
import java.util.HashMap;
import java.util.Map;
public class LRUCache {
// 双向链表节点
private class Node {
int key, value;
Node prev, next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private int capacity;
private Map<Integer, Node> cache;
private Node head, tail; // 虚拟头尾节点
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap<>();
// 初始化虚拟头尾节点
head = new Node(0, 0);
tail = new Node(0, 0);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) return -1;
// 将节点移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
if (node == null) {
// 创建新节点
Node newNode = new Node(key, value);
cache.put(key, newNode);
addToHead(newNode);
// 检查容量
if (cache.size() > capacity) {
Node tailNode = removeTail();
cache.remove(tailNode.key);
}
} else {
// 更新值并移到头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(Node node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(Node node) {
removeNode(node);
addToHead(node);
}
private Node removeTail() {
Node res = tail.prev;
removeNode(res);
return res;
}
}
package main
import "container/list"
type LRUCache struct {
capacity int
cache map[int]*list.Element
list *list.List
}
type entry struct {
key, value int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
capacity: capacity,
cache: make(map[int]*list.Element),
list: list.New(),
}
}
func (c *LRUCache) Get(key int) int {
if elem, ok := c.cache[key]; ok {
// 移动到链表头部
c.list.MoveToFront(elem)
return elem.Value.(*entry).value
}
return -1
}
func (c *LRUCache) Put(key, value int) {
if elem, ok := c.cache[key]; ok {
// 更新值并移到头部
elem.Value.(*entry).value = value
c.list.MoveToFront(elem)
return
}
// 检查容量
if c.list.Len() >= c.capacity {
// 移除最久未使用的元素
oldest := c.list.Back()
if oldest != nil {
c.list.Remove(oldest)
delete(c.cache, oldest.Value.(*entry).key)
}
}
// 添加新元素
elem := c.list.PushFront(&entry{key, value})
c.cache[key] = elem
}
#include <unordered_map>
#include <list>
class LRUCache {
private:
int capacity;
std::list<std::pair<int, int>> cache; // {key, value}
std::unordered_map<int, std::list<std::pair<int, int>>::iterator> map;
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto it = map.find(key);
if (it == map.end()) return -1;
// 将节点移到头部
cache.splice(cache.begin(), cache, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = map.find(key);
if (it != map.end()) {
// 更新值并移到头部
it->second->second = value;
cache.splice(cache.begin(), cache, it->second);
return;
}
// 检查容量
if (cache.size() >= capacity) {
// 移除尾部元素
auto last = cache.back();
map.erase(last.first);
cache.pop_back();
}
// 添加到头部
cache.emplace_front(key, value);
map[key] = cache.begin();
}
};
Redis 采用近似 LRU 算法，而非精确 LRU：
maxmemory-samples 控制采样数量# Redis 配置示例 maxmemory 256mb maxmemory-policy allkeys-lru maxmemory-samples 10
InnoDB 采用改进的 LRU 算法：
innodb_old_blocks_pct 默认 37%-- 查看 Buffer Pool 状态 SHOW ENGINE INNODB STATUS; SHOW VARIABLES LIKE 'innodb_buffer%';
Linux 内核的页面缓存使用双链表 LRU设计：
| 策略 | 淘汰依据 | 时间复杂度 | 适用场景 | 缺陷 |
|---|---|---|---|---|
| LRU | 最近最少使用 | O(1) | 通用缓存场景 | 缓存污染问题 |
| LFU | 访问频率最低 | O(log n) | 访问模式稳定 | 冷启动问题、历史数据难以淘汰 |
| FIFO | 先进先出 | O(1) | 简单队列缓存 | 不考虑访问频率，效率低 |
| Random | 随机淘汰 | O(1) | 无明显访问规律 | 命中率不稳定 |
| TTL | 过期时间 | O(1) | 有时效性的数据 | 需设置合理过期时间 |
| ARC | 自适应 LRU+LFU | O(1) | 复杂访问模式 | 实现复杂、专利限制 |
为了克服 LRU 算法的一些局限性，出现了多种改进版本：
基于访问次数，当数据被访问 K 次后才被加入缓存，有效避免了缓存污染问题。
使用两个队列（FIFO 和 LRU），结合了两种策略的优点，减少了突发访问对缓存的影响。
基于访问频率，淘汰访问次数最少的数据，适合访问模式稳定的场景。
一种近似 LRU 算法，使用时钟指针和访问位，减少了链表操作的开销。
自适应缓存算法，动态调整 LRU 和 LFU 的权重，根据实际访问模式自动优化。
将缓存分为多个段，只有长期存活的数据才能进入核心段，提高了缓存利用率。
单用哈希表：无法维护元素的访问顺序，无法判断哪个是最久未使用的。
单用链表：查找需要 O(n) 遍历，无法满足 O(1) 的时间要求。
组合使用：哈希表实现 O(1) 查找，双向链表实现 O(1) 的插入/删除/移动。两者互补，缺一不可。
删除链表中间节点时，需要修改前驱节点的 next 指针。
单向链表：必须从头遍历找到前驱节点，时间复杂度 O(n)。
双向链表：节点自带 prev 指针，直接访问前驱节点，时间复杂度 O(1)。
当缓存满需要淘汰尾部节点时，需要同时从哈希表中删除对应的键值对。
如果节点中不存储 Key，我们就无法知道应该删除哈希表中的哪个条目。
因此节点必须同时存储 key 和 value，这是一个容易忽略的细节。
方案一：全局锁 - 使用 synchronized 或 ReentrantLock 保护所有操作，简单但并发性能差。
方案二：读写锁 - 读操作共享锁，写操作独占锁，适合读多写少场景。
方案三：分段锁 - 将缓存分成多个段，每段独立加锁，提高并发度（类似 ConcurrentHashMap）。
方案四：CAS + 无锁链表 - 使用原子操作实现无锁结构，复杂度高但性能最优。
选择 LRU：访问模式有时间局部性、数据热度变化快、实现简单优先。
选择 LFU：访问模式稳定、部分数据长期高频访问、能接受冷启动问题。
实际应用：Redis 4.0+ 引入了 LFU，可根据业务场景在 LRU 和 LFU 间切换。
LRU-K：数据被访问 K 次后才进入缓存，过滤一次性访问。
2Q 算法：使用两个队列，新数据先入 FIFO 队列，再次访问时才进入 LRU 队列。
分区 LRU：类似 MySQL InnoDB，将缓存分为热区和冷区，新数据先入冷区。