如何使用 JavaScript 实现一个简单的 LRU (Least Recently Used) 缓存？

推荐答案

// www.javascriptcn.com code example
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map(); // 使用Map存储，保持插入顺序
  }

  get(key) {
    if (!this.cache.has(key)) {
      return -1;
    }
    const value = this.cache.get(key);
    this.cache.delete(key);
    this.cache.set(key, value); // 访问后，将 key 移到末尾，表示最近使用过
    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) {
        this.cache.delete(this.cache.keys().next().value); // 移除最久未使用的（队头）
      }
  }
}

// 使用示例
const lruCache = new LRUCache(2);
lruCache.put(1, 1);
lruCache.put(2, 2);
console.log(lruCache.get(1)); // 返回 1
lruCache.put(3, 3);    //  移除key 2
console.log(lruCache.get(2)); // 返回 -1 (未找到)
lruCache.put(4,4) //移除key 1
console.log(lruCache.get(1)); // 返回-1
console.log(lruCache.get(3)); //返回3
console.log(lruCache.get(4)); //返回4

本题详细解读

缓存策略：LRU

LRU (Least Recently Used) 是一种常见的缓存淘汰策略。其核心思想是：当缓存空间不足时，优先淘汰最近最少使用的数据，保留最近经常使用的数据。

实现思路

1. 数据结构选择:

   • 使用 Map 数据结构来存储缓存数据。 Map 可以保持插入顺序，这对于实现 LRU 策略非常重要。
   • Map 的 get, set, delete 方法时间复杂度均为 O(1)，满足高效访问要求。

2. 核心操作:

   • get(key):

     • 如果 key 存在于 Map 中：
       • 获取 key 对应的 value。
       • 将 key 从 Map 中删除。
       • 将 key 重新插入到 Map 的末尾（表示最近使用）。
       • 返回 value。
     • 如果 key 不存在，返回 -1。

   • put(key, value):

     • 如果key存在于Map中，先删除该key。
     • 将 key 和 value 插入到 Map 的末尾（表示最近使用）。
     • 如果 Map 的大小超过了 capacity，则删除 Map 中第一个元素（即最久未使用）。这里使用this.cache.keys().next().value获取队头key。

代码解析

• constructor(capacity):

  • 初始化缓存的容量 capacity 和一个 Map 实例 cache。

• get(key):

  • 检查 key 是否存在于 cache 中。
  • 如果存在，获取 value，并将其对应的 key 移动到 cache 的末尾，然后返回 value。
  • 如果不存在，返回 -1。

• put(key, value):

  • 如果key存在于Map中，先删除该key。
  • 将 key 和 value 插入到 cache 的末尾。
  • 如果缓存已满，删除 cache 中最老的（第一个） key-value 对。

为什么选择 Map？

• 保持插入顺序: Map 对象会记住键的原始插入顺序。这对于实现 LRU 策略至关重要，因为我们需要知道哪个元素是最近最少使用的。
• 高效查找: Map 对象的 get, set, delete 方法时间复杂度均为 O(1)，可以快速访问和操作缓存中的元素。
• **方便删除最早插入元素:**可以通过this.cache.keys().next().value方便的获取到最先插入的key，再通过delete删除。

时间复杂度

• get(key): O(1)
• put(key, value): O(1)

空间复杂度

• O(capacity) 缓存最多存储capacity个元素