LRU 缓存

LRU（Least Recently Used，最近最少使用）：缓存满时淘汰「最久未被使用」的数据。要求 get 和 put 的时间复杂度都是 O(1)。

思路

需要 O(1) 的查找 → 哈希表
需要 O(1) 的「调整顺序 / 删除最旧」→ 双向链表
JS 里 Map 天然保留插入顺序，可同时满足两点：最旧的在最前，最新的在最后

基于 Map 实现

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    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, value) {
    if (this.cache.has(key)) {
      // 已存在则先删除，保证重新插入后位于末尾
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // 超容量：删除最久未使用的（Map 的第一个 key）
      const oldestKey = this.cache.keys().next().value;
      this.cache.delete(oldestKey);
    }
    this.cache.set(key, value);
  }
}

const lru = new LRUCache(2);
lru.put(1, 1);
lru.put(2, 2);
lru.get(1); // 1（1 变为最近使用）
lru.put(3, 3); // 淘汰 2
lru.get(2); // -1

常见追问

为什么不用普通对象？ 普通对象无法保证键的顺序，且数字键会被转成字符串、无法 O(1) 拿到「最旧」键。
不用 Map 怎么实现？ 用「哈希表 + 自己实现的双向链表」，节点存 key/value/prev/next，get/put 时把节点移到链表头部，淘汰链表尾部。
LFU 有什么区别？ LFU 按「使用频次」淘汰，需要额外维护频次计数和频次桶。

思路​

基于 Map 实现​

常见追问​

思路

基于 Map 实现

常见追问