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); // 容量为2

lru.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)操作：

1. 检查键是否存在

2. 如果存在，先删除该键值对，再重新插入（这样它会位于Map末尾）

3. 返回对应的值

put(key, value)操作：

1. 检查键是否已存在

   • 如果存在，先删除旧的键值对

2. 如果键不存在且缓存已满，删除最久未使用的键（Map的第一个键）

3. 插入新的键值对（这会自动放在Map末尾）

4. 时间复杂度

• get操作：O(1) - Map的查找和删除操作都是O(1)

• put操作：O(1) - Map的查找、删除和插入操作都是O(1)

5. 为什么Map保持顺序

在JavaScript中，Map对象会记住键值对的原始插入顺序。当我们迭代Map时，键值对会按照插入顺序返回。这使得我们可以利用这个特性来实现LRU策略：

• 最近访问的键会被移动到Map末尾

• 最久未访问的键自然就位于Map开头

变体与优化

对于更复杂的场景，可以考虑：

1. 使用双向链表+哈希表实现（更高效的内存管理）

2. 实现TTL（Time To Live）过期机制

3. 添加统计功能，记录缓存命中率

这个实现简洁明了地展示了LRU的核心思想，适合大多数前端应用场景。如果需要更高性能的实现，可以考虑更复杂的数据结构组合。