LRU 缓存

问题

请你设计并实现一个满足 LRU（最近最少使用）缓存约束的数据结构。

实现 LRUCache 类：

LRUCache(capacity: number) — 以正整数作为容量初始化 LRU 缓存
get(key: number): number — 如果关键字存在缓存中，返回值；否则返回 -1
put(key: number, value: number): void — 如果关键字已存在，变更值；不存在则插入。当容量满时，淘汰最久未使用的关键字

get 和 put 必须以 $O(1)$ 的平均时间复杂度运行。

示例：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

来源：LeetCode 146. LRU 缓存

手写实现详解另见手写 LRU 缓存

答案

方法一：双向链表 + 哈希表（标准解法）

核心思路：

哈希表： $O(1)$ 查找节点
双向链表： $O(1)$ 插入/删除节点，维护使用顺序（头部最近使用，尾部最久未使用）

LRUCache.ts
// 双向链表节点（泛型：key 和 value 类型可自定义）
class DLinkedNode<K = number, V = number> {
  key: K;
  value: V;
  prev: DLinkedNode<K, V> | null = null;
  next: DLinkedNode<K, V> | null = null;

  constructor(key: K, value: V) {
    this.key = key;
    this.value = value;
  }
}

class LRUCache<K = number, V = number> {
  private capacity: number;
  private map: Map<K, DLinkedNode<K, V>>;
  private head: DLinkedNode<K, V>;  // 虚拟头节点
  private tail: DLinkedNode<K, V>;  // 虚拟尾节点

  constructor(capacity: number) {
    this.capacity = capacity;
    this.map = new Map();

    // 创建虚拟头尾节点，简化边界处理
    this.head = new DLinkedNode<K, V>(null as K, null as V);
    this.tail = new DLinkedNode<K, V>(null as K, null as V);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: K): V | undefined {
    const node = this.map.get(key);
    if (!node) return undefined;

    // 移到头部（标记为最近使用）
    this.moveToHead(node);
    return node.value;
  }

  put(key: K, value: V): void {
    const node = this.map.get(key);

    if (node) {
      // 已存在：更新值，移到头部
      node.value = value;
      this.moveToHead(node);
    } else {
      // 不存在：创建新节点
      const newNode = new DLinkedNode(key, value);
      this.map.set(key, newNode);
      this.addToHead(newNode);

      // 超容量：淘汰尾部节点
      if (this.map.size > this.capacity) {
        const removed = this.removeTail();
        this.map.delete(removed.key);
      }
    }
  }

  // ---- 双向链表操作 ----

  /** 添加节点到头部 */
  private addToHead(node: DLinkedNode<K, V>): void {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  /** 删除指定节点 */
  private removeNode(node: DLinkedNode<K, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  /** 将节点移到头部 */
  private moveToHead(node: DLinkedNode<K, V>): void {
    this.removeNode(node);
    this.addToHead(node);
  }

  /** 删除尾部节点并返回 */
  private removeTail(): DLinkedNode<K, V> {
    const node = this.tail.prev!;
    this.removeNode(node);
    return node;
  }
}

// LeetCode 题解：默认泛型参数就是 number，直接用即可
// const cache = new LRUCache(2);      // LRUCache<number, number>

// 实际项目中可以缓存任意类型
// const cache = new LRUCache<string, User>(100);
// cache.put('user_1', { name: 'Alice', age: 30 });
// cache.get('user_1');  // User | undefined

图解：

head ↔ [最近使用] ↔ [次近使用] ↔ ... ↔ [最久未使用] ↔ tail

get(key): 找到节点 → 移到 head 后面
put(key): 新节点插入 head 后面，超容量则删 tail 前面的节点

    head ↔ A ↔ B ↔ C ↔ tail   （容量 3）

get(B):
    head ↔ B ↔ A ↔ C ↔ tail   （B 移到头部）

put(D):
    head ↔ D ↔ B ↔ A ↔ tail   （D 插入头部，C 被淘汰）

复杂度分析

时间复杂度：get 和 put 均为 $O(1)$
空间复杂度： $O(capacity)$

为什么需要双向链表？

单向链表删除节点需要先遍历找到前一个节点，是 $O(n)$ 。双向链表可以直接通过 node.prev 访问前驱， $O(1)$ 删除。

为什么节点要存 key？

当淘汰尾部节点时，需要知道它的 key 来从 Map 中删除对应条目。

方法二：利用 Map 的有序性（ES6 巧解）

ES6 的 Map 保持插入顺序！我们可以利用这个特性：

LRUCacheMap.ts
class LRUCache<K = number, V = number> {
  private capacity: number;
  private cache: Map<K, V>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key: K): V | undefined {
    if (!this.cache.has(key)) return undefined;

    // 技巧：删除后重新插入，就排到了"最新"的位置
    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);

    return value;
  }

  put(key: K, value: V): void {
    // 如果已存在，先删除（保证重新插入后在最后面）
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }

    this.cache.set(key, value);

    // 超容量：删除最老的（Map 的第一个键）
    if (this.cache.size > this.capacity) {
      const oldestKey = this.cache.keys().next().value!;
      this.cache.delete(oldestKey);
    }
  }
}

面试建议

方法二代码简洁，适合快速写出
但面试官通常希望看到方法一（双向链表 + 哈希表），因为它展示了你对数据结构的理解
建议先写方法一，然后提一下方法二作为"JS 特有的巧解"

Map 的 delete + set 是否真的 O(1)？

V8 引擎中 Map 的 delete 和 set 操作在绝大多数情况下是 $O(1)$ 。但严格来说，这取决于引擎实现，面试时最好说明这是利用了 JS Map 的实现特性。

常见面试追问

Q1: LRU 淘汰算法有什么实际应用？

答案：

场景	说明
浏览器缓存	缓存页面资源，满了淘汰最久没访问的
Vue keep-alive	使用 LRU 策略管理缓存的组件实例
数据库缓冲池	MySQL InnoDB 的 Buffer Pool
操作系统	页面置换算法（虚拟内存管理）
Redis	`maxmemory-policy` 中的 `allkeys-lru`
前端请求缓存	缓存 API 响应，避免重复请求

Q2: LRU 和 LFU 有什么区别？

答案：

	LRU	LFU
全称	Least Recently Used	Least Frequently Used
淘汰依据	最久没被访问	被访问次数最少
适合场景	访问有时间局部性	访问有频率差异
实现复杂度	较低	较高（需要维护频次）
缺点	偶尔的批量扫描会污染缓存	新数据可能很快被淘汰

Q3: 如何实现带 TTL（过期时间）的 LRU 缓存？

答案：

class LRUCacheWithTTL<K = number, V = number> {
  private capacity: number;
  private cache: Map<K, { value: V; expireAt: number }>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key: K): V | undefined {
    const entry = this.cache.get(key);
    if (!entry) return undefined;

    // 检查是否过期
    if (Date.now() > entry.expireAt) {
      this.cache.delete(key);
      return undefined;
    }

    // 移到最新位置
    this.cache.delete(key);
    this.cache.set(key, entry);
    return entry.value;
  }

  put(key: K, value: V, ttl: number = 60000): void {
    this.cache.delete(key);
    this.cache.set(key, {
      value,
      expireAt: Date.now() + ttl,
    });

    if (this.cache.size > this.capacity) {
      const oldestKey = this.cache.keys().next().value!;
      this.cache.delete(oldestKey);
    }
  }
}

Q4: put 时容量满了，为什么要先 addToHead 再淘汰尾部？

答案：顺序其实无所谓，因为新插入的节点在头部，淘汰的是尾部的节点，不会影响新节点。但如果 capacity 为 1，你需要确保先删后加或者先加后删都能正确工作——因为新节点和旧节点不是同一个节点。

问题​

答案​

方法一：双向链表 + 哈希表（标准解法）​

方法二：利用 Map 的有序性（ES6 巧解）​

常见面试追问​

Q1: LRU 淘汰算法有什么实际应用？​

Q2: LRU 和 LFU 有什么区别？​

Q3: 如何实现带 TTL（过期时间）的 LRU 缓存？​

Q4: put 时容量满了，为什么要先 addToHead 再淘汰尾部？​

相关链接​

问题

答案