标准答案
- LRU 表示 Least Recently Used，容量满时淘汰最久没有被访问的数据。
- get 命中时不仅要返回值，还要刷新该 key 的使用顺序。
- put 写入已存在 key 时要更新值，并把它移动到最新位置。
- 容量超出时删除最旧的 key。
- Map 版本适合理解核心规则，高性能版本通常用哈希表加双向链表。
题目解析
LRU 常见于接口缓存、图片缓存、编译缓存和页面状态缓存。它解决的是容量有限时保留更可能再次访问的数据，而不是无限缓存。
Map 的插入顺序能表达“新旧”。删除后重新 set，就可以把一个 key 移到最新位置；Map.keys().next().value 可以拿到最旧 key。
如果面试继续要求 O(1) 移动和删除，就要从 Map 简化版升级到哈希表加双向链表：哈希表负责定位节点，链表负责维护访问顺序。
代码示例
Map 简化版可以清楚展示访问刷新和容量淘汰两个动作。
JavaScript
class LRUCache {
constructor(capacity) {
this.capacity = capacity
this.cache = new Map()
}
get(key) {
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, 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)
}
}
}常见误区
- get 命中后没有刷新顺序，导致常用数据仍然可能被淘汰。
- 只存数据不限制容量，实际上没有实现 LRU 淘汰。
- 没有说明 Map 简化版和哈希表加双向链表版本的性能差异。