各位靓仔靓女们，晚上好！我是你们的老朋友，今晚咱们来聊聊JavaScript中的LRU缓存，顺便用Map给它安排得明明白白。
开场白：缓存的重要性，以及LRU为何如此受欢迎
在前端的世界里，速度就是生命！想象一下，如果每次用户访问你的网站，都要重新加载所有资源，那体验简直糟糕透顶。这时候，缓存就闪亮登场了，它能把那些常用的数据临时存起来，下次再用的时候直接从缓存里拿，速度杠杠的！
缓存策略有很多种，但LRU（Least Recently Used，最近最少使用）绝对是明星级的。它的思想很简单：如果一个数据很久没被用过了，那就说明它可能不太重要了，可以优先把它踢出缓存，给新来的数据腾地方。这就像你整理房间，总是先把那些你几个月都没碰过的东西扔掉，道理是一样的。
LRU缓存的基本原理
LRU缓存的核心在于“最近使用”这个概念。我们需要记录每个数据的使用情况，以便在缓存满了的时候，找到那个“最不常用”的数据。
- 容量限制： LRU缓存都有一个容量上限，超过这个容量就需要淘汰数据。
- 数据存储： 我们需要一个数据结构来存储缓存的数据。
- 访问记录： 每次访问一个数据，都需要更新它的“最近使用”状态。
- 淘汰策略： 当缓存满了，需要根据“最近使用”状态，淘汰最不常用的数据。
为什么选择Map来实现LRU？
在JavaScript中，有很多数据结构可以用来实现LRU缓存，比如对象（Object）、数组（Array）等。但是，Map绝对是最佳选择之一，原因如下：
- 有序性：
Map会记住键值对插入的顺序，这对于维护“最近使用”的状态非常有用。我们可以把最近使用的数据放在Map的前面，最不常用的数据放在后面。 - 高性能：
Map的get、set、delete等操作的时间复杂度都是O(1)，这保证了缓存的访问速度。 - 方便的迭代：
Map提供了方便的迭代方法，可以轻松地遍历缓存中的数据。
用Map实现LRU缓存：代码实现
说了这么多，是时候上代码了。下面是一个用Map实现的LRU缓存的例子：
class LRUCache {
constructor(capacity) {
this.capacity = capacity; // 缓存容量
this.cache = new Map(); // 使用Map存储数据
}
get(key) {
if (this.cache.has(key)) {
const value = this.cache.get(key);
this.cache.delete(key); // 先删除，再添加，保证最近使用的在前面
this.cache.set(key, value);
return value;
}
return -1; // 未找到，返回-1 (或者undefined，根据需求)
}
put(key, value) {
if (this.cache.has(key)) {
this.cache.delete(key); // 如果存在，先删除
} else if (this.cache.size >= this.capacity) {
// 缓存已满，淘汰最不常用的数据
const oldestKey = this.cache.keys().next().value; // 获取第一个key，也就是最老的key
this.cache.delete(oldestKey);
}
this.cache.set(key, value); // 添加新的数据
}
}
// 使用示例
const lruCache = new LRUCache(2); // 容量为2
lruCache.put(1, 1); // 缓存：{1=1}
lruCache.put(2, 2); // 缓存：{1=1, 2=2}
console.log(lruCache.get(1)); // 返回 1，缓存：{2=2, 1=1}
lruCache.put(3, 3); // 淘汰 key 2，缓存：{1=1, 3=3}
console.log(lruCache.get(2)); // 返回 -1 (未找到)
lruCache.put(4, 4); // 淘汰 key 1，缓存：{3=3, 4=4}
console.log(lruCache.get(1)); // 返回 -1 (未找到)
console.log(lruCache.get(3)); // 返回 3，缓存：{4=4, 3=3}
console.log(lruCache.get(4)); // 返回 4，缓存：{3=3, 4=4}代码解释：
constructor(capacity)：构造函数，初始化缓存容量和Map对象。get(key)：获取缓存中的数据。如果找到了，就把这个数据移动到Map的末尾（表示最近使用过），然后返回数据；如果没找到，就返回-1。put(key, value)：添加或更新缓存中的数据。如果key已经存在，就先删除它，然后再添加到Map的末尾；如果key不存在，就判断缓存是否已满，如果满了，就淘汰掉最不常用的数据，然后再添加新的数据。
LRU缓存的优化：双向链表 + Hash表
虽然用Map实现LRU缓存已经很不错了，但还可以更进一步！我们可以使用双向链表 + Hash表来实现LRU缓存，这样可以把get和put操作的时间复杂度都降到O(1)。
- 双向链表： 用于维护数据的顺序，最近使用的放在链表头部，最不常用的放在链表尾部。
- Hash表： 用于快速查找数据，key是缓存的key，value是链表中对应节点的指针。
class LRUCacheOptimized {
constructor(capacity) {
this.capacity = capacity;
this.cache = new Map(); // Hash表，用于快速查找节点
this.head = null; // 链表头
this.tail = null; // 链表尾
}
// 链表节点类
class Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.prev = null;
this.next = null;
}
}
get(key) {
if (!this.cache.has(key)) {
return -1;
}
const node = this.cache.get(key);
this.moveToHead(node); // 移动到链表头部
return node.value;
}
put(key, value) {
if (this.cache.has(key)) {
const node = this.cache.get(key);
node.value = value; // 更新值
this.moveToHead(node); // 移动到链表头部
} else {
const node = new Node(key, value);
this.cache.set(key, node);
this.addToHead(node); // 添加到链表头部
if (this.cache.size > this.capacity) {
// 缓存已满，淘汰尾部节点
const tailNode = this.removeTail();
this.cache.delete(tailNode.key);
}
}
}
// 将节点移动到链表头部
moveToHead(node) {
this.removeNode(node);
this.addToHead(node);
}
// 删除节点
removeNode(node) {
if (node.prev) {
node.prev.next = node.next;
} else {
this.head = node.next; // 如果是头节点，更新头节点
}
if (node.next) {
node.next.prev = node.prev;
} else {
this.tail = node.prev; // 如果是尾节点，更新尾节点
}
}
// 添加节点到链表头部
addToHead(node) {
node.next = this.head;
node.prev = null;
if (this.head) {
this.head.prev = node;
}
this.head = node;
if (!this.tail) {
this.tail = node; // 如果是第一个节点，同时更新尾节点
}
}
// 移除链表尾部节点
removeTail() {
const tailNode = this.tail;
this.removeNode(tailNode);
return tailNode;
}
}
// 使用示例
const lruCacheOptimized = new LRUCacheOptimized(2);
lruCacheOptimized.put(1, 1);
lruCacheOptimized.put(2, 2);
console.log(lruCacheOptimized.get(1)); // 返回 1
lruCacheOptimized.put(3, 3);
console.log(lruCacheOptimized.get(2)); // 返回 -1
lruCacheOptimized.put(4, 4);
console.log(lruCacheOptimized.get(1)); // 返回 -1
console.log(lruCacheOptimized.get(3)); // 返回 3
console.log(lruCacheOptimized.get(4)); // 返回 4代码解释：
Node类：表示链表中的节点，包含key、value、prev（前一个节点）、next（后一个节点）等属性。head和tail：分别指向链表的头节点和尾节点。get(key)：从Hash表中查找节点，如果找到了，就把这个节点移动到链表头部，然后返回节点的值。put(key, value)：如果key已经存在，就更新节点的值，然后把节点移动到链表头部；如果key不存在，就创建一个新的节点，添加到链表头部，并把节点添加到Hash表中。如果缓存已满，就移除链表尾部的节点，并从Hash表中删除对应的key。moveToHead(node)：把节点移动到链表头部。removeNode(node)：从链表中删除节点。addToHead(node)：把节点添加到链表头部。removeTail()：移除链表尾部的节点。
LRU缓存的应用场景
LRU缓存的应用非常广泛，几乎所有需要缓存数据的场景都可以使用它。比如：
- 浏览器缓存： 浏览器会使用LRU算法来缓存网页资源，比如图片、CSS、JavaScript等。
- 数据库缓存： 数据库会使用LRU算法来缓存查询结果，提高查询速度。
- Web服务器缓存： Web服务器会使用LRU算法来缓存静态资源，减轻服务器压力。
- 前端框架： 一些前端框架也会使用LRU算法来缓存组件的状态，提高页面渲染速度。
一些需要注意的点
- 缓存容量的选择： 缓存容量的选择非常重要，太小了起不到缓存的效果，太大了又会占用过多的内存。需要根据实际情况进行权衡。
- 缓存失效策略： 除了LRU算法，还有其他的缓存失效策略，比如TTL（Time To Live，过期时间）、LFU（Least Frequently Used，最少使用）等。可以根据实际需求选择合适的策略。
- 并发问题： 如果多个线程同时访问缓存，需要考虑并发问题，可以使用锁或者其他并发控制机制来保证缓存的一致性。
总结
今天我们一起学习了JavaScript中的LRU缓存，以及如何使用Map来实现LRU算法。LRU缓存是一种非常实用的缓存策略，可以有效地提高程序的性能。掌握LRU缓存的原理和实现，对于前端开发人员来说是非常重要的。
希望今天的讲座对大家有所帮助，谢谢大家！下次再见！
表格总结
为了更清晰地总结今天的内容，这里用一个表格来对比一下两种LRU缓存的实现方式：
| 特性 | Map实现 | 双向链表 + Hash表实现 |
|---|---|---|
| 数据结构 | Map | 双向链表 + Hash表 |
| 时间复杂度 | get: O(1), put: O(1) 但包含删除再插入操作 |
get: O(1), put: O(1) |
| 空间复杂度 | O(capacity) | O(capacity) |
| 实现复杂度 | 简单 | 较复杂 |
| 适用场景 | 对性能要求不是特别高的场景 | 对性能要求非常高的场景 |
| 优点 | 代码简洁易懂，容易实现 | get和put操作都是O(1)，性能更高 |
| 缺点 | 包含删除再插入操作，会有一定的性能损耗 | 代码复杂，实现难度较高 |
总的来说，选择哪种实现方式取决于具体的应用场景和性能要求。如果对性能要求不是特别高，Map实现是一个不错的选择，因为它简单易懂，容易实现。如果对性能要求非常高，那么双向链表 + Hash表实现是更好的选择，因为它的get和put操作都是O(1)。