题库/手写题/题目详解
手写题答案约 5 分钟阅读

TTL 缓存与 LRU

先理解原理和示例，再练习完整口述与追问。

回答要点

容量、最近访问顺序、过期、时钟、未命中语义。

原理拆解

LRU 淘汰最久未使用项，访问和更新都可能改变最近使用顺序；TTL 根据时间过期，两者可以组合但不是同一种策略。Map 可借插入顺序实现简化 LRU，get 命中后删除再插入。缓存缺失与值为 undefined 应区分，容量、过期和清理时机要有明确约定。

示例与推演

容量 2：set A、set B、get A、set C，此时应淘汰 B 而不是 A。再测试覆盖旧键、容量为 0、过期项读取、undefined 值和时钟变化。延迟清理能减少后台计时器，但只有访问时才清理可能让未访问过期项继续占内存。

易错点

不要把高命中率当成允许无限内存增长。包含用户权限的数据需要正确缓存键与失效，否则会变成跨用户数据泄漏。

参考回答可直接练习口述

LRU 淘汰最近最少使用项，Map 的插入顺序可以表示新旧顺序：命中后删再插，超容量删最旧项。TTL 另管过期，两者不是一回事。下面 TTL 从 set 开始计时，get 不续期；set 前清理过期项，避免把仍有效数据挤掉。通过注入时钟可稳定测试，不需要实际等待。

js
class LruTtlCache {
  constructor(capacity, now = () => Date.now()) {
    if (!Number.isInteger(capacity) || capacity <= 0) {
      throw new RangeError('capacity 必须是正整数')
    }
    if (typeof now !== 'function') throw new TypeError('now 必须是函数')
    this.capacity = capacity
    this.now = now
    this.data = new Map()
  }

  get(key) {
    const item = this.data.get(key)
    if (!item) return undefined
    if (item.expiresAt <= this.now()) {
      this.data.delete(key)
      return undefined
    }
    this.data.delete(key)
    this.data.set(key, item)
    return item.value
  }

  set(key, value, ttl = Infinity) {
    if (ttl !== Infinity && (!Number.isFinite(ttl) || ttl < 0)) {
      throw new RangeError('ttl 必须是非负有限数或 Infinity')
    }
    const now = this.now()
    for (const [oldKey, item] of this.data) {
      if (item.expiresAt <= now) this.data.delete(oldKey)
    }
    this.data.delete(key)
    if (ttl === 0) return this
    this.data.set(key, {
      value,
      expiresAt: ttl === Infinity ? Infinity : now + ttl
    })
    if (this.data.size > this.capacity) {
      this.data.delete(this.data.keys().next().value)
    }
    return this
  }
}

**示例：**容量 2，依次 set(a)、set(b)、get(a)、set(c)，淘汰 b；ttl=0 立即失效，正好到期也失效。get 平均 O(1)，set 因扫过期项为 O(容量)，空间 O(容量)。get 返回 undefined 既可能未命中也可能存了 undefined，此接口不区分；需要区分时增加 has 或返回命中结构。过期采用惰性清理，没有承诺后台到时自动释放。