标准答案
- LRU 的全称是 Least Recently Used，核心规则是优先淘汰最久没有被访问的数据。
- get 命中时要刷新该 key 的使用顺序。
- put 写入已存在 key 时也要刷新顺序，并更新值。
- 容量超出时删除最旧的 key。
- 高性能实现通常用哈希表加双向链表；在 JavaScript 面试简化场景里，可以用 Map 的有序特性表达核心思路。
题目解析
LRU 常见于接口缓存、图片缓存、编译缓存和页面状态缓存。它解决的不是“缓存所有东西”，而是在容量有限时保留更可能再次被用到的数据。
Map 版本的好处是表达清楚，面试中足够说明规则：删除再插入可以把一个 key 放到最新位置，Map.keys().next().value 可以拿到最旧 key。
如果场景对性能非常敏感，Map 简化版就要进一步讨论复杂度和数据结构。哈希表负责 O(1) 查找，双向链表负责 O(1) 移动节点和淘汰尾部节点。
代码示例
Map 的插入顺序可以用来实现一个简化 LRU。
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 命中后没有刷新顺序，导致常用数据仍然可能被淘汰。
- 只限制写入次数，没有在容量超出时删除最旧数据。
- 没有说明 Map 简化实现和哈希表加双向链表实现的性能差异。