跳到主要内容

LRU 缓存

问题​

设计并实现一个 LRU（最近最少使用）缓存 机制。

答案​

LRU（Least Recently Used）是一种缓存淘汰策略：当缓存满时，删除最久未使用的数据。

核心要求​

  • get(key)：获取缓存值，若存在则更新为"最近使用"
  • put(key, value)：设置缓存值，若超出容量则淘汰最久未使用的
  • 两个操作的时间复杂度都要求 O(1)O(1)

方案一：使用 Map（ES6）​

ES6 的 Map 会保持插入顺序，可以利用这个特性实现 LRU：

class LRUCache<T> {
  private cache: Map<string, T>;
  private capacity: number;

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

  get(key: string): T | 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: string, value: T): void {
    // 如果已存在，先删除
    if (this.cache.has(key)) {
      this.cache.delete(key);
    }
    // 如果达到容量，删除最久未使用的（第一个）
    else if (this.cache.size >= this.capacity) {
      const [oldestKey] = this.cache.keys();
      this.cache.delete(oldestKey);
    }

    this.cache.set(key, value);
  }

  // 获取缓存大小
  get size(): number {
    return this.cache.size;
  }

  // 清空缓存
  clear(): void {
    this.cache.clear();
  }

  // 检查是否存在
  has(key: string): boolean {
    return this.cache.has(key);
  }
}

// 测试
const cache = new LRUCache<number>(2);
cache.put('a', 1);
cache.put('b', 2);
console.log(cache.get('a'));  // 1
cache.put('c', 3);            // 淘汰 'b'
console.log(cache.get('b'));  // undefined
console.log(cache.get('c'));  // 3

方案二：双向链表 + 哈希表（面试标准答案）​

这是面试官期望的经典实现，需要手写双向链表：

完整实现​

// 双向链表节点
class ListNode<K, V> {
  key: K;
  value: V;
  prev: ListNode<K, V> | null = null;
  next: ListNode<K, V> | null = null;

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

class LRUCacheLinkedList<V> {
  private capacity: number;
  private cache: Map<string, ListNode<string, V>>;
  private head: ListNode<string, V>;  // 哨兵头节点
  private tail: ListNode<string, V>;  // 哨兵尾节点

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

    // 初始化哨兵节点
    this.head = new ListNode<string, V>('' as string, null as unknown as V);
    this.tail = new ListNode<string, V>('' as string, null as unknown as V);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  get(key: string): V | undefined {
    const node = this.cache.get(key);
    if (!node) {
      return undefined;
    }

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

  put(key: string, value: V): void {
    const existingNode = this.cache.get(key);

    if (existingNode) {
      // 更新值并移到头部
      existingNode.value = value;
      this.moveToHead(existingNode);
    } else {
      // 创建新节点
      const newNode = new ListNode(key, value);

      // 达到容量，移除尾部节点
      if (this.cache.size >= this.capacity) {
        const tailNode = this.removeTail();
        this.cache.delete(tailNode.key);
      }

      // 添加到头部
      this.addToHead(newNode);
      this.cache.set(key, newNode);
    }
  }

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

  // 移除节点
  private removeNode(node: ListNode<string, V>): void {
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  // 移动节点到头部
  private moveToHead(node: ListNode<string, V>): void {
    this.removeNode(node);
    this.addToHead(node);
  }

  // 移除尾部节点
  private removeTail(): ListNode<string, V> {
    const tailNode = this.tail.prev!;
    this.removeNode(tailNode);
    return tailNode;
  }

  // 获取所有缓存（按使用顺序）
  entries(): Array<[string, V]> {
    const result: Array<[string, V]> = [];
    let current = this.head.next;
    while (current !== this.tail) {
      result.push([current!.key, current!.value]);
      current = current!.next;
    }
    return result;
  }
}

// 测试
const lru = new LRUCacheLinkedList<number>(3);
lru.put('a', 1);
lru.put('b', 2);
lru.put('c', 3);
console.log(lru.entries()); // [['c', 3], ['b', 2], ['a', 1]]

lru.get('a');
console.log(lru.entries()); // [['a', 1], ['c', 3], ['b', 2]]

lru.put('d', 4);            // 淘汰 'b'
console.log(lru.entries()); // [['d', 4], ['a', 1], ['c', 3]]

方案对比​

方案时间复杂度空间复杂度优点缺点
MapO(1)O(1)O(n)O(n)代码简洁，利用 Map 特性依赖 JS 引擎实现
双向链表 + 哈希表O(1)O(1)O(n)O(n)标准实现，面试首选代码较多

高级功能​

带过期时间的 LRU​

interface CacheItem<V> {
  value: V;
  expireAt: number;
}

class LRUCacheWithTTL<V> {
  private cache: Map<string, CacheItem<V>>;
  private capacity: number;
  private defaultTTL: number;

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

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

    const item = this.cache.get(key)!;

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

    // 更新为最近使用
    this.cache.delete(key);
    this.cache.set(key, item);
    return item.value;
  }

  put(key: string, value: V, ttl?: number): void {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // 先清理过期项
      this.cleanup();
      // 仍然满则删除最旧的
      if (this.cache.size >= this.capacity) {
        const [oldestKey] = this.cache.keys();
        this.cache.delete(oldestKey);
      }
    }

    this.cache.set(key, {
      value,
      expireAt: Date.now() + (ttl ?? this.defaultTTL),
    });
  }

  private cleanup(): void {
    const now = Date.now();
    for (const [key, item] of this.cache) {
      if (now > item.expireAt) {
        this.cache.delete(key);
      }
    }
  }
}

带统计的 LRU​

interface CacheStats {
  hits: number;
  misses: number;
  hitRate: number;
}

class LRUCacheWithStats<V> {
  private cache: Map<string, V>;
  private capacity: number;
  private hits: number = 0;
  private misses: number = 0;

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

  get(key: string): V | undefined {
    if (!this.cache.has(key)) {
      this.misses++;
      return undefined;
    }

    this.hits++;
    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key: string, value: V): void {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      const [oldestKey] = this.cache.keys();
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }

  getStats(): CacheStats {
    const total = this.hits + this.misses;
    return {
      hits: this.hits,
      misses: this.misses,
      hitRate: total > 0 ? this.hits / total : 0,
    };
  }

  resetStats(): void {
    this.hits = 0;
    this.misses = 0;
  }
}

LeetCode 146: LRU 缓存（标准答案）​

class LRUCacheLeetCode {
  private capacity: number;
  private cache: Map<number, number>;

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

  get(key: number): number {
    if (!this.cache.has(key)) {
      return -1;
    }
    const value = this.cache.get(key)!;
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key: number, value: number): void {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      const [firstKey] = this.cache.keys();
      this.cache.delete(firstKey);
    }
    this.cache.set(key, value);
  }
}

常见面试问题​

Q1: 为什么使用双向链表而不是单向链表？​

答案：

操作双向链表单向链表
删除节点O(1)O(1)，直接访问 prevO(n)O(n)，需要遍历找前驱
移动到头部O(1)O(1)O(n)O(n)

单向链表删除节点需要找到前驱节点，必须遍历；双向链表可直接通过 node.prev 访问。

Q2: 为什么要用哨兵节点？​

答案：

// 没有哨兵节点：需要大量边界判断
function removeNode(node: ListNode<string, number>): void {
  if (node.prev) {
    node.prev.next = node.next;
  } else {
    // node 是头节点，需要特殊处理
    this.head = node.next;
  }
  if (node.next) {
    node.next.prev = node.prev;
  } else {
    // node 是尾节点，需要特殊处理
    this.tail = node.prev;
  }
}

// 有哨兵节点：代码简洁
function removeNodeWithSentinel(node: ListNode<string, number>): void {
  node.prev!.next = node.next;
  node.next!.prev = node.prev;
}

哨兵节点避免了头尾的空指针判断，简化代码。

Q3: LRU 和 LFU 的区别？​

答案：

策略全称淘汰依据适用场景
LRULeast Recently Used最久未使用时间局部性强
LFULeast Frequently Used使用频率最低频率分布稳定
// LFU 简单实现
class LFUCache<V> {
  private cache: Map<string, { value: V; freq: number }>;
  private capacity: number;

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

  get(key: string): V | undefined {
    const item = this.cache.get(key);
    if (!item) return undefined;
    item.freq++;
    return item.value;
  }

  put(key: string, value: V): void {
    if (this.cache.has(key)) {
      const item = this.cache.get(key)!;
      item.value = value;
      item.freq++;
      return;
    }

    if (this.cache.size >= this.capacity) {
      // 找到频率最低的
      let minFreq = Infinity;
      let minKey = '';
      for (const [k, v] of this.cache) {
        if (v.freq < minFreq) {
          minFreq = v.freq;
          minKey = k;
        }
      }
      this.cache.delete(minKey);
    }

    this.cache.set(key, { value, freq: 1 });
  }
}

Q4: 为什么 LRU 缓存要用双向链表 + 哈希表？只用 Map 不行吗？​

答案：

在 JavaScript 中，Map 确实维护了键的插入顺序，可以通过"删除再重新插入"的方式模拟 LRU。但这种做法依赖的是 JS 引擎的实现细节，而非语言规范对性能的保证。

只用 Map 的简版 LRU：

class SimpleLRU<V> {
  private cache: Map<string, V>;
  private capacity: number;

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

  get(key: string): V | undefined {
    if (!this.cache.has(key)) return undefined;
    const value = this.cache.get(key)!;
    // "删除再插入" 将 key 移到 Map 末尾（最近使用）
    this.cache.delete(key);
    this.cache.set(key, value);
    return value;
  }

  put(key: string, value: V): void {
    if (this.cache.has(key)) this.cache.delete(key);
    else if (this.cache.size >= this.capacity) {
      // 获取第一个 key（最久未使用）
      const [oldestKey] = this.cache.keys();
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

为什么面试中仍推荐双向链表 + 哈希表：

对比维度Map 方案双向链表 + 哈希表
get 操作delete + set（两次哈希操作）链表节点移动，O(1)O(1) 指针操作
put 淘汰keys().next() 获取最旧 key直接访问 tail.prev，O(1)O(1)
移动到头部必须删除再插入（可能触发 rehash）修改 4 个指针，无需 rehash
跨语言通用性仅 JS/TS（依赖 Map 有序特性）任何语言都可实现（C、Java、Go）
面试考察点考察 JS API 熟练度考察数据结构设计能力
面试建议
  • 先写 Map 版本展示你对 JS 的熟练度，再写双向链表版本展示数据结构功底
  • 面试官问"只用 Map 行不行"时，回答"JS 中可以，但标准做法用双向链表"，并解释原因

Q5: 如何给 LRU 缓存加上过期时间（TTL）？​

答案：

给 LRU 加 TTL（Time To Live）需要在每个缓存节点中存储过期时间戳，并在 get 时检查是否过期。过期清理策略通常有两种：惰性清理（访问时检查）和定时清理（定时器扫描）。

interface TTLCacheEntry<V> {
  value: V;
  expireAt: number; // 过期时间戳（ms）
}

class LRUWithTTL<V> {
  private cache: Map<string, TTLCacheEntry<V>>;
  private capacity: number;
  private defaultTTL: number;
  private cleanupTimer: ReturnType<typeof setInterval> | null = null;

  constructor(capacity: number, defaultTTL: number = 60_000) {
    this.capacity = capacity;
    this.cache = new Map();
    this.defaultTTL = defaultTTL;
  }

  get(key: string): 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: string, value: V, ttl?: number): void {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      this.evict();
    }

    this.cache.set(key, {
      value,
      expireAt: Date.now() + (ttl ?? this.defaultTTL),
    });
  }

  // 淘汰：优先删除已过期的，否则删除最久未使用的
  private evict(): void {
    const now = Date.now();

    // 先尝试淘汰过期项
    for (const [key, entry] of this.cache) {
      if (now > entry.expireAt) {
        this.cache.delete(key);
        return;
      }
    }

    // 没有过期项，淘汰最久未使用的（Map 中第一个）
    const [oldestKey] = this.cache.keys();
    this.cache.delete(oldestKey);
  }

  // 定时清理：启动定时器批量清除过期项
  startAutoCleanup(interval: number = 30_000): void {
    this.cleanupTimer = setInterval(() => {
      const now = Date.now();
      for (const [key, entry] of this.cache) {
        if (now > entry.expireAt) {
          this.cache.delete(key);
        }
      }
    }, interval);
  }

  stopAutoCleanup(): void {
    if (this.cleanupTimer) {
      clearInterval(this.cleanupTimer);
      this.cleanupTimer = null;
    }
  }
}

// 使用示例
const cache = new LRUWithTTL<string>(100, 5000); // 容量 100，默认 TTL 5 秒
cache.put('token', 'abc123');
cache.put('config', '{}', 60_000); // 指定 60 秒 TTL

cache.startAutoCleanup(10_000); // 每 10 秒清理一次过期项

两种清理策略的对比：

策略触发时机优点缺点
惰性清理get 时检查零额外开销，实现简单过期项可能长时间占用内存
定时清理定时器周期扫描及时释放内存扫描有 O(n)O(n) 开销，需管理定时器
最佳实践

实际项目中通常两种策略结合使用：惰性清理保证读取时的正确性，定时清理作为兜底防止内存泄漏。Redis 的过期键也采用了类似的混合策略。

Q6: LRU 和 LFU 有什么区别？各自的适用场景？​

答案：

LRU（Least Recently Used）和 LFU（Least Frequently Used）是两种最常见的缓存淘汰策略，核心区别在于淘汰依据不同。

对比维度LRULFU
全称Least Recently UsedLeast Frequently Used
淘汰依据最久没有被访问的被访问次数最少的
数据结构双向链表 + 哈希表双哈希表 + 频率链表
时间复杂度O(1)O(1) get/putO(1)O(1) get/put（需要精心设计）
实现复杂度较低较高
对突发流量敏感（新数据直接置顶）不敏感（需要多次访问才能提升）
缓存污染容易被偶发访问污染抗污染能力强

适用场景：

  • LRU 适合：大多数 Web 应用、页面缓存、组件缓存（如 Vue keep-alive）。时间局部性强，最近用过的数据大概率还会用
  • LFU 适合：热点数据明显的场景，如 CDN 缓存、搜索热词、热门商品。高频数据不会因为偶尔没被访问就被淘汰

LFU 实现（双哈希表 + 最小频率追踪）：

class LFUCache<V> {
  private capacity: number;
  private minFreq: number = 0;
  // key → { value, freq }
  private keyMap: Map<string, { value: V; freq: number }>;
  // freq → Set<key>（同频率的 key 集合，按插入顺序）
  private freqMap: Map<number, Set<string>>;

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

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

    // 更新频率
    this.increaseFreq(key, entry);
    return entry.value;
  }

  put(key: string, value: V): void {
    if (this.capacity <= 0) return;

    const entry = this.keyMap.get(key);

    if (entry) {
      // 已存在：更新值并增加频率
      entry.value = value;
      this.increaseFreq(key, entry);
    } else {
      // 不存在：可能需要淘汰
      if (this.keyMap.size >= this.capacity) {
        this.evictMinFreq();
      }

      // 新插入的频率为 1
      const newEntry = { value, freq: 1 };
      this.keyMap.set(key, newEntry);

      if (!this.freqMap.has(1)) {
        this.freqMap.set(1, new Set());
      }
      this.freqMap.get(1)!.add(key);

      this.minFreq = 1; // 新插入的元素频率一定是最低的
    }
  }

  private increaseFreq(key: string, entry: { value: V; freq: number }): void {
    const oldFreq = entry.freq;
    const newFreq = oldFreq + 1;
    entry.freq = newFreq;

    // 从旧频率集合中移除
    const oldSet = this.freqMap.get(oldFreq)!;
    oldSet.delete(key);

    // 如果旧频率集合空了，删除它
    if (oldSet.size === 0) {
      this.freqMap.delete(oldFreq);
      // 如果淘汰的是最小频率，更新 minFreq
      if (this.minFreq === oldFreq) {
        this.minFreq = newFreq;
      }
    }

    // 加入新频率集合
    if (!this.freqMap.has(newFreq)) {
      this.freqMap.set(newFreq, new Set());
    }
    this.freqMap.get(newFreq)!.add(key);
  }

  private evictMinFreq(): void {
    const minSet = this.freqMap.get(this.minFreq)!;
    // Set 按插入顺序，第一个就是同频率中最久未使用的
    const evictKey = minSet.values().next().value as string;
    minSet.delete(evictKey);

    if (minSet.size === 0) {
      this.freqMap.delete(this.minFreq);
    }

    this.keyMap.delete(evictKey);
  }
}

// 测试
const lfu = new LFUCache<string>(3);
lfu.put('a', 'A');
lfu.put('b', 'B');
lfu.put('c', 'C');
lfu.get('a'); // freq: a=2, b=1, c=1
lfu.get('a'); // freq: a=3, b=1, c=1
lfu.get('b'); // freq: a=3, b=2, c=1
lfu.put('d', 'D'); // 淘汰 c（频率最低为 1，c 是 freq=1 中最早的）
console.log(lfu.get('c')); // undefined（已被淘汰）
console.log(lfu.get('d')); // 'D'
LFU 实现要点
  1. 双哈希表：keyMap 存储键值和频率，freqMap 按频率分组管理键集合
  2. minFreq 追踪：维护当前最小频率，淘汰时直接定位到最低频率组，保证 O(1)O(1)
  3. 同频率淘汰规则：同一频率组内按 LRU 策略淘汰最久未使用的（利用 Set 的插入顺序）

相关链接​