LRU (Least Recently Used，最近最少使用) 缓存是我们在前端开发和后端架构设计中经常遇到的一种高效数据管理策略。你是否想过，为什么浏览器的“后退”按钮能如此流畅，或者像 Redis 这样的数据库能如此迅速地处理热点数据？这背后往往都有 LRU 的影子。简单来说，它是一种在空间有限时，通过淘汰“最久未被使用”的数据来为新数据腾出空间的算法。
在这篇文章中，我们将深入探讨 LRU 缓存的核心原理。我们不会只停留在理论层面，而是会一起动手，使用 JavaScript 从零开始实现它。我们将从最基础的数据结构入手，逐步优化，直到构建出一个时间复杂度为 O(1) 的高性能缓存系统。无论你是正在准备算法面试，还是希望在实际项目中优化应用性能，这篇文章都将为你提供实用的见解和代码范例。
目录
LRU 缓存的核心逻辑
在开始写代码之前，让我们先达成一个共识：LRU 的本质是什么？假设我们有一个容量为 3 的背包（缓存），和一堆物品（数据请求）。
- 读取: 当你拿出背包里的某个物品使用时，它是“最近被使用”的。为了记住这一点，我们需要把它标记为最“热”门。
- 写入: 当我们要往背包里放新物品，但背包已经满了时，我们必须扔掉那个最“冷”门（最久没被拿出来过）的物品，然后把新物品放进去。
为了实现这两个操作，我们需要一种能够快速表示“优先级”或“时间顺序”的机制。让我们看看在 JavaScript 中有哪些实现路径。
方法一：结合 Map 和双向链表（O(1) 标准解法）
这是实现 LRU 缓存最经典、也是面试中最期望看到的“标准答案”。为什么选择这种组合？让我们来拆解一下：
- 哈希表: 我们需要通过 Key 快速找到 Value。JavaScript 的
Map或普通对象都能提供 O(1) 的查找速度。但是，单纯的 Map 并不能告诉我们哪个 Key 是最近使用的，哪个是最久未使用的。 - 双向链表: 链表非常适合维护顺序。我们可以将最近访问的节点移动到链表头部，那么链表尾部的节点自然就是最久未使用的。但是，单纯遍历链表删除节点是 O(n) 的操作。
“强强联合”：我们将 INLINECODE16224745 存储指向链表节点的引用（用于 O(1) 查找），将节点本身组织成双向链表（用于 O(1) 的顺序维护）。这样，INLINECODE4eb3c62e 和 put 操作都能在常数时间内完成。
代码实现：构建节点与缓存类
首先，我们需要定义链表的节点。每个节点不仅要存值，还要存 Key（为了方便从 Map 中删除），以及前驱和后继指针。
/**
* 双向链表节点类
* 用于维护数据的访问顺序
*/
class ListNode {
constructor(key, value) {
this.key = key; // 存储 key，以便在链表节点中也能找到对应的 map 键
this.value = value;
this.prev = null;
this.next = null;
}
}
/**
* LRU 缓存类
* 使用 Map 进行快速查找，双向链表进行顺序管理
*/
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map(); // 存储 key -> Node 的映射
// 初始化双向链表的头尾哨兵节点
// 这两个节点不存储实际数据，作为边界简化链表操作逻辑
this.head = new ListNode(null, null);
this.tail = new ListNode(null, null);
this.head.next = this.tail;
this.tail.prev = this.head;
}
/**
* 私有方法：从双向链表中移除指定节点
* 时间复杂度: O(1)
*/
_remove(node) {
let prev = node.prev;
let next = node.next;
prev.next = next;
next.prev = prev;
}
/**
* 私有方法：将节点添加到链表头部（表示最近被使用）
* 时间复杂度: O(1)
*/
_add(node) {
// 插入到 head 和 head.next 之间
let next = this.head.next;
this.head.next = node;
node.prev = this.head;
node.next = next;
next.prev = node;
}
/**
* 获取数据
* 1. 如果 key 存在，通过 Map 找到节点
* 2. 将节点移到链表头部（标记为最近使用）
* 3. 返回值
*/
get(key) {
if (!this.cache.has(key)) {
return -1;
}
let node = this.cache.get(key);
// 关键步骤：访问后更新顺序，先移除再添加到头部
this._remove(node);
this._add(node);
return node.value;
}
/**
* 写入数据
* 1. 如果 key 已存在，更新值并移到头部
* 2. 如果 key 不存在，创建新节点并添加到头部
* 3. 如果超过容量，移除尾部节点（最久未使用）
*/
put(key, value) {
if (this.cache.has(key)) {
// 更新现有节点
let oldNode = this.cache.get(key);
this._remove(oldNode);
}
let newNode = new ListNode(key, value);
this._add(newNode);
this.cache.set(key, newNode);
// 检查是否超出容量，移除尾部节点
if (this.cache.size > this.capacity) {
// tail.prev 指向的就是最久未使用的节点
let lru = this.tail.prev;
this._remove(lru);
this.cache.delete(lru.key);
}
}
}
// === 实战测试 ===
console.log("--- 方法一：Map + 双向链表 ---");
const lru = new LRUCache(2); // 容量限制为 2
lru.put(1, 1);
console.log("Cache: {1:1}"); // 当前状态
lru.put(2, 2);
console.log("Cache: {1:1, 2:2}");
console.log(lru.get(1)); // 返回 1，此时 key 1 变为最近使用
// 顺序变为: [2, 1] -> 1 是最新的
lru.put(3, 3); // 该操作会使得 key 2 (最久未使用) 被淘汰
console.log(lru.get(2)); // 返回 -1 (未找到)
lru.put(4, 4); // 该操作会使得 key 1 被淘汰
console.log(lru.get(1)); // 返回 -1 (未找到)
console.log(lru.get(3)); // 返回 3
console.log(lru.get(4)); // 返回 4
输出结果
--- 方法一：Map + 双向链表 ---
Cache: {1:1}
Cache: {1:1, 2:2}
1
-1
-1
3
4
性能分析
这种结构虽然代码量稍大，但它是性能的王者。
- 时间复杂度: INLINECODE7a3af84a 和 INLINECODE1655c293 操作严格为 O(1)。无论是在 10 个数据还是 100 万个数据中，操作速度都是恒定的。
- 空间复杂度: O(capacity)，我们需要额外的空间存储指针。
方法二：利用 Map 的有序性（现代 JavaScript 最佳实践）
你可能不知道，ECMAScript 2015 (ES6) 规范中明确规定，INLINECODE958c6f75 对象会保留插入顺序。这意味着，当我们遍历 Map 时，它会按照 Key 被插入的顺序返回。更重要的是，对某个 Key 重新 INLINECODE88a6d187 值，不会改变它的位置；但如果我们先 INLINECODE2d0a18af 再 INLINECODE8e9b6ebf，它就会移动到末尾。
利用这个特性，我们可以用极简的代码实现 LRU：将 Map 的“头部”视为最久未使用，“尾部”视为最近使用。
代码实现：极简 LRU
/**
* 使用 ES6 Map 的有序性实现 LRU
* 这种方法利用了 JS 引擎底层的优化，代码极其简洁
*/
class LRUCacheSimple {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
// 核心技巧：先取值，再删除，再重新设置
// 这样会让该 key 移动到 Map 的最末尾（代表最近使用）
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);
// 如果超出容量，删除 Map 中的第一个元素（最久未使用）
// keys().next().value 可以获取迭代器的第一个元素
if (this.cache.size > this.capacity) {
const oldestKey = this.cache.keys().next().value;
this.cache.delete(oldestKey);
}
}
}
// === 实战测试 ===
console.log("
--- 方法二：Map 有序性 (推荐) ---");
const simpleLRU = new LRUCacheSimple(2);
simpleLRU.put(1, 1);
simpleLRU.put(2, 2);
console.log(simpleLRU.get(1)); // 返回 1，此时 1 被移至末尾，Map 状态: {2, 1}
simpleLRU.put(3, 3); // 移除头部 key (2)
console.log(simpleLRU.get(2)); // 返回 -1
simpleLRU.put(4, 4); // 移除头部 key (1)
console.log(simpleLRU.get(1)); // 返回 -1
console.log(simpleLRU.get(3)); // 返回 3
console.log(simpleLRU.get(4)); // 返回 4
输出结果
--- 方法二：Map 有序性 (推荐) ---
1
-1
-1
3
4
这种方法不仅代码可读性高，而且由于是直接利用引擎内置的数据结构，运行效率极高。
方法三：Map 与 数组结合（仅供理解）
除了上述两种高效方法，我们在教程或旧代码库中可能会看到使用数组来维护顺序的做法。虽然这有助于我们理解 LRU 的逻辑，但在生产环境中应当避免。
这种方法的工作原理是：
- Map: 存储键值对，提供 O(1) 的查找。
- 数组: 存储 Key 的顺序，最新的 Key 放在数组末尾。
#### 为什么不推荐？
在数组中查找特定 Key 的索引（用于更新顺序时删除旧索引）需要使用 indexOf，这是一个 O(n) 的操作。当缓存数据量达到几千或几万时，性能会急剧下降。
// 示例：概念性代码（不推荐用于生产环境）
class LRUNaive {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map();
this.order = []; // 使用数组维护顺序
}
get(key) {
if (!this.cache.has(key)) return -1;
const value = this.cache.get(key);
this._updateOrder(key); // 这里有性能隐患
return value;
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.set(key, value);
this._updateOrder(key);
} else {
if (this.cache.size >= this.capacity) {
// 移除数组第一个元素（最久未使用）
const lruKey = this.order.shift();
this.cache.delete(lruKey);
}
this.cache.set(key, value);
this.order.push(key);
}
}
_updateOrder(key) {
// O(n) 操作：查找并删除
const index = this.order.indexOf(key);
if (index > -1) {
this.order.splice(index, 1);
}
this.order.push(key);
}
}
LRU 缓存的应用场景与最佳实践
掌握了实现原理后，我们在实际项目中如何运用它呢？
1. 前端请求缓存
想象一下，你正在开发一个电商应用，用户频繁切换商品详情页。如果每次切换都重新发起 HTTP 请求，不仅浪费流量，还会导致界面闪烁。
// 实用示例：封装一个带有 LRU 缓存的 fetch 函数
class CachedFetch {
constructor(maxSize = 10) {
this.cache = new LRUCacheSimple(maxSize);
}
async request(url) {
// 检查缓存
const cachedData = this.cache.get(url);
if (cachedData !== -1) {
console.log(`[Cache Hit] Returning data for ${url}`);
return cachedData;
}
console.log(`[Cache Miss] Fetching ${url}`);
const response = await fetch(url);
const data = await response.json();
// 存入缓存，将 URL 作为 key
this.cache.put(url, data);
return data;
}
}
// 使用场景
const api = new CachedFetch(5);
// 假设用户快速点击了 5 个不同的商品，第 6 个点击会导致第 1 个商品的缓存被清除
2. 内存限制与性能权衡
LRU 缓存本质上是用空间换时间。但是，空间（内存）是有限的。如果你的应用运行在移动端或低内存设备上，设置过大的 capacity 可能会导致浏览器 Tab 崩溃（OOM）。
- 最佳实践: 根据单个数据项的大小动态设置缓存容量。例如，如果缓存的是图片对象（很大），容量设为 10-20 即可；如果缓存的是轻量级 JSON 对象，容量可以设为 100-500。
3. 过期时间 (TTL) 的结合
标准的 LRU 没有时间概念，只要数据一直被访问，它就会永远留在缓存中。但在实际业务中，我们通常希望数据在一定时间后失效。
如果你需要同时支持 LRU 和 TTL (Time To Live)，你可以考虑在存入 Value 时包裹一个元数据对象：
// 简单的 TTL 集成思路
// put(key, value) {
// const item = {
// value: value,
// expiry: Date.now() + 5000 // 5秒后过期
// };
// this.cache.put(key, item);
// }
// get(key) {
// const item = this.cache.get(key);
// if (item.expiry < Date.now()) {
// this.cache.delete(key); // 手动清理过期项
// return -1;
// }
// return item.value;
// }
注意：实现 TTL 会增加 get 操作的开销，需要权衡利弊。
总结与进阶建议
在这篇文章中，我们一起探讨了 LRU 缓存的三种实现方式，从复杂的双向链表到利用现代 JavaScript 特性的 Map 方法。
让我们回顾一下关键点：
- O(1) 性能是关键: 在面试和高性能场景中，双向链表配合 Map 是标准解法。
- JS 特性: 使用 Map 的有序性实现 LRU 是 JavaScript 开发者的“隐藏武器”，代码简洁且性能优秀。
- 避免数组陷阱: 不要在生产环境用数组维护 LRU 顺序，除非数据量极小。
作为下一步，我建议你尝试扩展这个功能：实现 LRU-K 缓存。LRU-K 不仅仅记录“最近一次访问”，而是记录“最近 K 次访问的时间”。只有访问次数达到 K 次的数据，才会被放入缓存的主要热数据区。这能有效防止“偶发性访问”挤掉“高频访问”的数据。
希望这篇文章能帮助你更好地理解数据结构背后的设计哲学。如果你在浏览器控制台里运行了这些代码，你会发现，那些枯燥的算法其实就在我们日常构建的每一个高性能应用之中。