LRU (Least Recently Used) 缓存实现及原理讲解
LRU (Least Recently Used) 是一种常见的缓存淘汰策略，它会优先淘汰最近最少使用的数据。下面我将用JavaScript实现一个LRU类，并详细讲解其原理。
LRU实现
class LRUCache {constructor(capacity) {this.capacity = capacity; // 缓存容量this.cache = new Map(); // 使用Map存储键值对}get(key) {if (!this.cache.has(key)) {return -1; // 如果键不存在，返回-1}// 获取值const value = this.cache.get(key);// 删除旧的键值对this.cache.delete(key);// 重新设置键值对，这样它会位于Map的末尾（表示最近使用）this.cache.set(key, value);return value;}put(key, value) {if (this.cache.has(key)) {// 如果键已存在，先删除旧的this.cache.delete(key);} else if (this.cache.size >= this.capacity) {// 如果缓存已满，删除最久未使用的键（Map的第一个键）// Map.keys()返回一个迭代器，next().value获取第一个键const oldestKey = this.cache.keys().next().value;this.cache.delete(oldestKey);}// 设置新的键值对this.cache.set(key, value);}
}使用示例
const lru = new LRUCache(2); // 容量为2lru.put(1, 1); // 缓存是 {1=1}
lru.put(2, 2); // 缓存是 {1=1, 2=2}
console.log(lru.get(1)); // 返回 1
lru.put(3, 3); // 该操作会使得键2作废，缓存是 {1=1, 3=3}
console.log(lru.get(2)); // 返回 -1 (未找到)
lru.put(4, 4); // 该操作会使得键1作废，缓存是 {4=4, 3=3}
console.log(lru.get(1)); // 返回 -1 (未找到)
console.log(lru.get(3)); // 返回 3
console.log(lru.get(4)); // 返回 4原理讲解
1. 数据结构选择
我们使用JavaScript的Map对象来实现LRU缓存，因为：
Map保持了键值对的插入顺序Map的查找、插入和删除操作都是O(1)时间复杂度Map可以直接获取第一个键（最久未使用）和最后一个键（最近使用）
2. 核心思想
LRU的核心思想是"最近最少使用"：
当访问一个键时，将它移动到"最近使用"的位置（Map的末尾）
当插入新键且缓存已满时，淘汰"最久未使用"的键（Map的第一个键）
3. 操作细节
get(key)操作：
检查键是否存在
如果存在，先删除该键值对，再重新插入（这样它会位于Map末尾）
返回对应的值
put(key, value)操作：
检查键是否已存在
如果存在，先删除旧的键值对
如果键不存在且缓存已满，删除最久未使用的键（Map的第一个键）
插入新的键值对（这会自动放在Map末尾）
4. 时间复杂度
get操作：O(1) - Map的查找和删除操作都是O(1)
put操作：O(1) - Map的查找、删除和插入操作都是O(1)
5. 为什么Map保持顺序
在JavaScript中，Map对象会记住键值对的原始插入顺序。当我们迭代Map时，键值对会按照插入顺序返回。这使得我们可以利用这个特性来实现LRU策略：
最近访问的键会被移动到Map末尾
最久未访问的键自然就位于Map开头
变体与优化
对于更复杂的场景，可以考虑：
使用双向链表+哈希表实现（更高效的内存管理）
实现TTL（Time To Live）过期机制
添加统计功能，记录缓存命中率
这个实现简洁明了地展示了LRU的核心思想，适合大多数前端应用场景。如果需要更高性能的实现，可以考虑更复杂的数据结构组合。