请用 JavaScript 实现一个 LRU (Least Recently Used) 缓存淘汰算法。

各位好，我是今天的讲师，很高兴能和大家聊聊LRU缓存，这可是面试常客，也是实际应用中提升性能的一大利器。今天咱们就来一起扒一扒它的实现原理，并用JavaScript把它安排得明明白白。

一、什么是LRU？为什么要用它？

首先，咱们得搞清楚LRU是啥。LRU，全称 Least Recently Used，顾名思义，就是“最近最少使用”。 也就是说，当缓存满了，我们需要淘汰掉那些最近最少被访问的数据，留下那些“香饽饽”。

想象一下，你是一个图书管理员，书架容量有限。如果有人借了一本很旧的书，但最近总有人来查阅，那你就不能轻易把它扔掉。但如果有一本书已经很久没人碰了，那就可以考虑把它清理出去，给新书腾地方。

这就是LRU的核心思想。

那么，为什么要用LRU呢？ 简单来说，是为了提升性能。

• 缓存加速： 将经常访问的数据放在缓存里，下次再访问时直接从缓存取，速度比从数据库或者硬盘读取快得多。
• 减少资源消耗： 减少对数据库或其他存储介质的访问，减轻服务器压力。
• 提高用户体验： 更快的响应速度，提升用户体验。

二、LRU的实现思路

实现LRU的关键在于：

1. 记录访问顺序： 我们需要一种方法来记录每个数据被访问的时间顺序。
2. 快速查找： 能够快速找到缓存中的数据。
3. 快速淘汰： 当缓存满时，能够快速找到并淘汰掉最久未使用的那个数据。

为了满足这些要求，通常会结合以下两种数据结构：

• 哈希表（HashMap/Object）： 用于快速查找缓存中的数据，时间复杂度为 O(1)。
• 双向链表（Doubly Linked List）： 用于维护数据的访问顺序。链表的头部表示最近访问的数据，尾部表示最久未访问的数据。

三、JavaScript实现LRU缓存

接下来，咱们用JavaScript来实现一个LRU缓存。

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity; // 缓存容量
    this.cache = {}; // 哈希表，用于存储键值对
    this.head = null; // 链表头部
    this.tail = null; // 链表尾部
    this.size = 0; // 当前缓存大小
  }

  // 内部类，表示链表节点
  Node(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }

  // 从缓存中获取数据
  get(key) {
    if (this.cache[key]) {
      const node = this.cache[key];
      this.moveToHead(node); // 将节点移动到链表头部
      return node.value;
    } else {
      return -1; // 表示缓存未命中
    }
  }

  // 将数据放入缓存
  put(key, value) {
    if (this.cache[key]) {
      // 缓存已存在，更新值，并将节点移动到链表头部
      const node = this.cache[key];
      node.value = value;
      this.moveToHead(node);
    } else {
      // 缓存不存在，创建新节点，并添加到链表头部
      const newNode = new this.Node(key, value);
      this.cache[key] = newNode;
      this.addToHead(newNode);
      this.size++;

      if (this.size > this.capacity) {
        // 缓存已满，淘汰链表尾部节点
        this.removeTail();
      }
    }
  }

  // 将节点移动到链表头部
  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() {
    if (!this.tail) {
      return; // 链表为空，无需移除
    }

    const tailNode = this.tail;
    delete this.cache[tailNode.key]; // 从哈希表中移除
    this.removeNode(tailNode); // 从链表中移除
    this.size--;
  }

  // 打印缓存信息 (用于调试)
  printCache() {
      let current = this.head;
      let output = "";
      while(current) {
          output += `(${current.key}: ${current.value}) <-> `;
          current = current.next;
      }
      output += "NULL";
      console.log("Cache: ", output);
      console.log("Size: ", this.size);
  }
}

// 示例用法
const lruCache = new LRUCache(3); // 容量为3

lruCache.put(1, 'A');
lruCache.printCache(); // Cache:  (1: A) <-> NULL  Size:  1

lruCache.put(2, 'B');
lruCache.printCache(); // Cache:  (2: B) <-> (1: A) <-> NULL  Size:  2

lruCache.put(3, 'C');
lruCache.printCache(); // Cache:  (3: C) <-> (2: B) <-> (1: A) <-> NULL  Size:  3

console.log(lruCache.get(2)); // B
lruCache.printCache(); // Cache:  (2: B) <-> (3: C) <-> (1: A) <-> NULL  Size:  3

lruCache.put(4, 'D');
lruCache.printCache(); // Cache:  (4: D) <-> (2: B) <-> (3: C) <-> NULL  Size:  3  (1被淘汰了)

console.log(lruCache.get(1)); // -1 (未命中)
lruCache.printCache(); // Cache:  (4: D) <-> (2: B) <-> (3: C) <-> NULL  Size:  3

lruCache.put(2, 'B2');
lruCache.printCache(); // Cache:  (2: B2) <-> (4: D) <-> (3: C) <-> NULL  Size:  3

lruCache.put(5, 'E');
lruCache.printCache(); // Cache:  (5: E) <-> (2: B2) <-> (4: D) <-> NULL  Size:  3  (3被淘汰了)

代码解释：

• LRUCache(capacity)： 构造函数，初始化缓存容量、哈希表、链表头尾节点和当前缓存大小。
• Node(key, value)： 内部类，表示链表节点，包含键、值以及指向前一个节点和后一个节点的指针。
• get(key)： 从缓存中获取数据。如果缓存命中，则将节点移动到链表头部，并返回value。如果缓存未命中，则返回 -1。
• put(key, value)： 将数据放入缓存。
  • 如果缓存已存在该键，则更新值，并将节点移动到链表头部。
  • 如果缓存不存在该键，则创建新节点，并添加到链表头部。如果缓存已满，则淘汰链表尾部节点。
• moveToHead(node)： 将节点移动到链表头部。
• removeNode(node)： 从链表中移除节点。
• addToHead(node)： 将节点添加到链表头部。
• removeTail()： 移除链表尾部节点。

四、代码细节分析

1. 哈希表的作用: 哈希表 this.cache 以键值对的形式存储数据，其中 key 是缓存的键，value 是指向链表中对应节点的指针。 这样，我们就可以通过 key 在 O(1) 的时间复杂度内找到缓存中的数据。

2. 双向链表的作用: 双向链表负责维护数据的访问顺序。 链表的头部 this.head 指向最近访问的数据，链表的尾部 this.tail 指向最久未访问的数据。

3. moveToHead(node) 的重要性: 当我们访问缓存中的数据时，需要将该节点移动到链表的头部，表示该数据最近被访问过。 这样，LRU 算法才能正确地淘汰最久未访问的数据。

4. removeTail() 的逻辑: 当缓存已满时，我们需要淘汰链表的尾部节点，也就是最久未访问的数据。 同时，我们需要从哈希表中删除该节点的键值对，保持数据一致性。

5. printCache() 方法： 这个方法主要是为了方便我们调试和观察缓存的状态。 实际生产环境中可能不需要这个方法，或者可以根据需要进行修改。

五、时间复杂度分析

• get(key)： O(1) (哈希表查找 + 链表节点移动)
• put(key, value)： O(1) (哈希表查找 + 链表节点添加/删除/移动)

六、LRU的优化方向

虽然上面的代码已经实现了一个基本的LRU缓存，但还可以进行一些优化：

• 使用ES6 Map: ES6 的 Map 对象在处理键值对时，性能通常比普通对象更好。可以使用 Map 代替 this.cache。
• 懒删除: 在 removeTail() 方法中，可以考虑懒删除，即不立即从哈希表中删除数据，而是标记为已删除，在下次访问时再进行实际删除。这样可以减少一些不必要的删除操作。
• 考虑并发场景: 如果LRU缓存在多线程或者并发环境下使用，需要考虑线程安全问题，可以使用锁或者其他并发控制机制来保证数据一致性。

七、LRU的应用场景

LRU缓存被广泛应用于各种场景：

• Web服务器： 缓存静态资源（图片、CSS、JavaScript等），减少对服务器的请求。
• 数据库： 缓存查询结果，减少数据库的访问压力。
• 操作系统： 缓存磁盘块，提高文件读写速度。
• 浏览器： 缓存网页资源，加快页面加载速度。
• 移动应用： 缓存数据，减少网络请求。

八、LRU与其他缓存算法的比较

除了LRU，还有其他一些常见的缓存算法，例如：

算法	描述	优点	缺点
LRU	最近最少使用，淘汰最久未被访问的数据。	实现简单，效果较好，能有效提高缓存命中率。	需要维护访问顺序，开销相对较大。 如果存在周期性访问的数据，LRU 可能会频繁淘汰这些数据，导致缓存命中率下降。
FIFO	先进先出，淘汰最早进入缓存的数据。	实现简单，开销小。	缓存命中率可能较低，因为最早进入缓存的数据不一定是最不常用的数据。
LFU	最不经常使用，淘汰访问频率最低的数据。	能够有效淘汰访问频率低的数据，提高缓存命中率。	实现相对复杂，需要维护访问频率。 对于某些场景，访问频率并不能完全反映数据的价值，例如，某个数据在短时间内被频繁访问，然后长期不被访问，LFU 可能会一直保留该数据，导致缓存利用率下降。
MRU	最近最多使用，淘汰最近被访问的数据。	在某些特定场景下可能有效，例如，在流媒体播放中，最近播放的视频可能很快就不会再被播放。	适用场景有限，大多数情况下效果不如 LRU。
Random	随机淘汰，随机选择一个数据进行淘汰。	实现非常简单，开销极小。	缓存命中率较低，效果不稳定。

选择哪种缓存算法，需要根据具体的应用场景进行权衡。

九、总结

今天，我们一起学习了LRU缓存算法的原理和实现，并用JavaScript实现了一个简单的LRU缓存。希望通过今天的讲解，大家能够对LRU缓存有更深入的理解，并在实际项目中灵活运用。

LRU缓存虽然是一个经典算法，但它也并非银弹。 在实际应用中，还需要根据具体的场景进行调整和优化。

好了，今天的讲座就到这里，谢谢大家！ 希望对你有所帮助。下次再见!