手写 LRU Cache

LRU（Least Recently Used）缓存淘汰最久未被访问的数据。面试通常要求 get、put 都达到平均 O(1)。

Map 实现

JavaScript 的 Map 会维护插入顺序。访问键时先删除再插入，即可把它移动到“最新”位置。

class LRUCache {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new RangeError('capacity must be a positive integer');
    }
    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);
    this.cache.set(key, value);

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

其中：

this.cache.keys().next().value

可以拆成三步理解：

this.cache.keys() 返回一个只遍历 key 的迭代器。Map 会按照插入顺序保存 key。
.next() 取出迭代器的第一个元素，返回形如 { value, done } 的对象。
.value 取出真正的 key。

因此，如果缓存中的 key 顺序是：

['a', 'b', 'c']

那么：

this.cache.keys().next().value; // 'a'

在这个 LRU 实现中，最久未使用的 key 始终位于 Map 的最前面，所以可以用它完成淘汰。Map 为空时，next().value 会是 undefined，但这里因为外层已经判断了 this.cache.size > this.capacity，正常情况下不会出现空 Map 淘汰。

const cache = new LRUCache(2);
cache.put('a', 1);
cache.put('b', 2);
cache.get('a');
cache.put('c', 3); // 淘汰 b

console.log(cache.get('b')); // -1
console.log(cache.get('a')); // 1

复杂度与经典实现

get、put：平均 O(1)。
空间：O(capacity)。

不依赖有序 Map 时，经典答案是哈希表加双向链表：哈希表负责定位节点，双向链表负责在 O(1) 内删除和移动节点，链表尾部保存最久未使用项。单链表无法在 O(1) 内删除任意节点，因为还需寻找前驱。

生产缓存通常还需要 TTL、容量统计和淘汰回调。LRU 只按最近访问淘汰，不保证命中率最优，也不适合对象体积差异极大的缓存。

带 TTL 的 LRU Cache

TTL（Time To Live）表示缓存项的存活时间。下面的实现约定：

ttl 使用毫秒表示，从 put 写入或更新时开始计时。
get 命中过期数据时，先删除数据，再返回 -1。
get 命中未过期数据时，会刷新 LRU 顺序，但不会刷新 TTL。
采用惰性删除：只有访问到过期数据，或主动调用 clearExpired 时才删除过期项。

class TTLCache {
  constructor(capacity, ttl) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new RangeError('capacity must be a positive integer');
    }
    if (!Number.isFinite(ttl) || ttl <= 0) {
      throw new RangeError('ttl must be a positive number');
    }

    this.capacity = capacity;
    this.ttl = ttl;
    this.cache = new Map();
  }

  get(key) {
    const entry = this.cache.get(key);
    if (!entry) return -1;

    if (entry.expiresAt <= Date.now()) {
      this.cache.delete(key);
      return -1;
    }

    // 删除后重新插入，使 key 进入最新位置。
    this.cache.delete(key);
    this.cache.set(key, entry);
    return entry.value;
  }

  put(key, value) {
    // 更新已有 key 时，重新计算 TTL，并将它移动到最新位置。
    this.cache.delete(key);
    this.cache.set(key, {
      value,
      expiresAt: Date.now() + this.ttl,
    });

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

  delete(key) {
    return this.cache.delete(key);
  }

  clearExpired() {
    const now = Date.now();

    for (const [key, entry] of this.cache) {
      if (entry.expiresAt <= now) {
        this.cache.delete(key);
      }
    }
  }
}

使用示例：

const cache = new TTLCache(2, 1000);

cache.put('a', 1);
console.log(cache.get('a')); // 1

setTimeout(() => {
  console.log(cache.get('a')); // -1，已超过 1000ms
}, 1100);

复杂度

get、put、delete：平均 O(1)。
clearExpired：O(n)，其中 n 是当前缓存项数量。
空间：O(capacity)。

惰性删除不会启动后台定时器，适合简单面试实现。如果要求过期数据必须在 TTL 到期的瞬间自动清除，可以为每个缓存项增加定时器，或者使用“哈希表 + 过期时间最小堆”；后者能更稳定地控制清理成本，但实现复杂度更高。

保护热 key 的分段 LRU

普通 LRU 只看“最近一次访问时间”。一个 key 即使被访问过很多次，只要一段时间没有访问，也可能和普通冷数据一样被淘汰。

可以把缓存分成两个区域：

probation：普通区，新写入的 key 先放这里。
protected：保护区，key 在普通区再次命中后晋升到这里。

淘汰时先淘汰普通区，只有普通区为空时才淘汰保护区。这样，偶尔访问一次的冷数据不会挤掉已经多次命中的热 key。

class HotKeyLRUCache {
  constructor(capacity, protectedCapacity = Math.ceil(capacity / 2)) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new RangeError('capacity must be a positive integer');
    }
    if (
      !Number.isInteger(protectedCapacity) ||
      protectedCapacity <= 0 ||
      protectedCapacity > capacity
    ) {
      throw new RangeError('protectedCapacity must be between 1 and capacity');
    }

    this.capacity = capacity;
    this.protectedCapacity = protectedCapacity;
    this.probation = new Map();
    this.protected = new Map();
  }

  get(key) {
    if (this.protected.has(key)) {
      const value = this.protected.get(key);
      this.protected.delete(key);
      this.protected.set(key, value);
      return value;
    }

    if (!this.probation.has(key)) return -1;

    const value = this.probation.get(key);
    this.probation.delete(key);
    this.promote(key, value);
    return value;
  }

  put(key, value) {
    if (this.protected.has(key)) {
      this.protected.delete(key);
      this.protected.set(key, value);
      return;
    }

    // 更新普通区中的 key 也视为一次命中，直接晋升到保护区。
    if (this.probation.has(key)) {
      this.probation.delete(key);
      this.promote(key, value);
      return;
    }

    this.probation.set(key, value);
    this.evictIfNeeded();
  }

  promote(key, value) {
    if (this.protected.size >= this.protectedCapacity) {
      const oldestProtectedKey = this.protected.keys().next().value;
      const oldestProtectedValue = this.protected.get(oldestProtectedKey);
      this.protected.delete(oldestProtectedKey);
      this.probation.set(oldestProtectedKey, oldestProtectedValue);
    }

    this.protected.set(key, value);
    this.evictIfNeeded();
  }

  evictIfNeeded() {
    while (this.probation.size + this.protected.size > this.capacity) {
      if (this.probation.size > 0) {
        const oldestKey = this.probation.keys().next().value;
        this.probation.delete(oldestKey);
      } else {
        const oldestKey = this.protected.keys().next().value;
        this.protected.delete(oldestKey);
      }
    }
  }
}

使用示例：

const cache = new HotKeyLRUCache(3, 2);

cache.put('hot', 'A');
cache.get('hot'); // hot 从普通区晋升到保护区
cache.put('cold-1', 'B');
cache.put('cold-2', 'C');
cache.put('cold-3', 'D'); // 优先淘汰普通区中的 cold-1

console.log(cache.get('hot')); // 'A'

这里的“保护”不是永久保留：保护区容量有限。当保护区已满，晋升新热 key 时，保护区中最久未访问的 key 会降级到普通区，并可能在下一次淘汰时被删除。

复杂度

get、put、晋升和淘汰：平均 O(1)。
空间：O(capacity)。

这个版本适合表达“访问频率优先、时间顺序次之”的缓存策略；如果要严格按照访问次数淘汰，则应改用 LFU，并维护访问频率和频率桶。

ON THIS PAGE

#手写 LRU Cache

#Map 实现

#复杂度与经典实现

#带 TTL 的 LRU Cache

#复杂度

#保护热 key 的分段 LRU