如何手写 LRU 缓存？ - AIGC面试刷题网

简化版

LRU 是“最近最少使用”淘汰策略：容量满时删除最长时间没有被访问的项。JavaScript 的 Map 按插入顺序迭代，命中时先 delete 再 set，就能把 key 移到队尾；超容时删除 map.keys().next().value 指向的队首 key。

详细版

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)
    this.cache.set(key, value)
    if (this.cache.size > this.capacity) {
      this.cache.delete(this.cache.keys().next().value)
    }
  }
}

has 不能省略，因为缓存值本身可能是 undefined。Map 方案的 get、put、淘汰平均为 O(1)；若题目要求语言无关的数据结构，则应回答“哈希表 + 双向链表”。

完整版教学

一、LRU 的顺序如何变化

容量为 2，依次操作：

操作	从最久未用到最近使用的顺序	返回值/淘汰
`put('a', 1)`	a	无
`put('b', 2)`	a → b	无
`get('a')`	b → a	1
`put('c', 3)`	a → c	淘汰 b
`get('b')`	a → c	miss

“使用”通常包括成功读取和更新写入。未命中的读取不改变顺序；同 key 更新后应成为最近使用项。

LRU 只定义“按最近访问淘汰”，没有天然包含过期时间、按字节计费、并发合并或持久化。面试时先把容量单位和 miss 返回值说清楚。

二、基于 Map 的完整面试实现

class LRUCache {
  constructor(capacity) {
    if (!Number.isInteger(capacity) || capacity < 0) {
      throw new TypeError('capacity must be a non-negative integer')
    }
    this.capacity = capacity
    this.cache = new Map()
  }

  get size() {
    return this.cache.size
  }

  has(key) {
    return this.cache.has(key)
  }

  get(key) {
    if (!this.cache.has(key)) return undefined
    const value = this.cache.get(key)
    this.touch(key, value)
    return value
  }

  put(key, value) {
    if (this.capacity === 0) return this
    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)
    }
    return this
  }

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

  clear() {
    this.cache.clear()
  }

  touch(key, value) {
    this.cache.delete(key)
    this.cache.set(key, value)
  }
}

本文允许容量为 0，此时 put 不保存任何数据。也可以要求容量必须大于 0，但要让校验与代码行为一致。

三、为什么 `delete + set` 表示最近使用

Map 迭代键值时按插入顺序。对已有 key 直接 set 只更新值，不会自动移动其顺序；先删除再插入，才会成为最后插入项。

const map = new Map([['a', 1], ['b', 2]])
map.set('a', 3)
console.log([...map.keys()]) // ['a', 'b']

map.delete('a')
map.set('a', 3)
console.log([...map.keys()]) // ['b', 'a']

队首 map.keys().next().value 是最久未使用的 key，队尾是最近使用项。淘汰时只需取第一个迭代结果，无需把所有键复制成数组。

四、miss 与 `undefined` 必须分开

如果允许缓存值为 undefined，仅看 get(key) 的返回值无法判断命中：

cache.put('answer', undefined)
cache.get('answer') // undefined，但确实命中并刷新了顺序
cache.get('missing') // undefined，未命中

所以内部必须先 has。对外可以提供独立 has，返回 { hit, value }，或使用业务不可能出现的 sentinel。LeetCode 常约定 miss 返回 -1，但通用 JavaScript 缓存不能假设所有值都是非负整数。

五、哈希表加双向链表版本的原理

Map 是 JavaScript 的简洁答案。若面试官要求不依赖有序 Map，应使用：

哈希表：key -> 链表节点，平均 O(1) 定位。
双向链表：头部表示最近使用，尾部表示最久未用。
get 命中：摘下节点并移动到头部。
put 超容：删除尾节点，并同步从哈希表删除 key。

单链表无法在只有节点引用时 O(1) 删除当前节点，因为还需要寻找前驱；双向链表保存 prev 和 next，才能常数时间摘除。哨兵头尾节点可减少空表和边界分支。

六、复杂度和生产边界

操作	Map 方案平均复杂度	说明
`get`	O(1)	查找、删除、重插
`put`	O(1)	更新并最多淘汰一次
`delete`	O(1)	Map 删除
空间	O(capacity)	不含值对象自身深层占用

规范只要求 Map 的访问性能“次线性”而非承诺某种固定内部结构，实际引擎通常提供接近常数的平均性能。面试复杂度按哈希 Map 的常见模型回答即可，同时注明平均而非严格最坏。

生产缓存还可能需要 TTL、按字节或权重限制、淘汰回调、统计命中率和并发请求去重。条目数量为 100 不代表内存可控，因为每项大小可能相差几个数量级。

七、常见误区与追问

误区：对已有 key 再 set 会自动移到 Map 末尾。 只更新不会改变原插入位置，必须先 delete 再 set。
误区：用 get(key) === undefined 判断未命中。 undefined 可能是合法缓存值，内部应使用 has。
误区：LRU 天然能处理过期数据。 LRU 按访问新旧淘汰，TTL 是另一维度，需要时间戳和过期清理策略。
追问：为什么链表必须双向？ 已有节点引用时，双向链表才能 O(1) 找到前驱并摘除节点。
追问：容量为 0 怎么处理？ 本文接受 0 且不保存数据；也可构造时拒绝，关键是合同一致。
追问：读取失败会刷新顺序吗？ 不会；只有实际命中的访问才代表该条目最近被使用。
追问：Map 版本和链表版本选哪个？ JavaScript 实战优先 Map；考察底层数据结构或其他语言时回答哈希表加双向链表。

八、加强记忆

顺序：队首最旧，队尾最新。
刷新：命中或更新时 delete + set 移到末尾。
淘汰：超容删除 keys().next().value 指向的队首 key。
命中：用 has 区分 miss 与合法的 undefined。
复杂度：哈希定位加常数次顺序操作，平均 O(1)。
边界：TTL、权重、并发和持久化都不是基础 LRU 自动提供的能力。

简化版

详细版