使用 JavaScript 实现 LFU（最少使用）和 LRU（最近最少使用）缓存策略，可以帮助你理解这两种算法的工作原理。下面是这两种缓存策略的实现示例。

总结

LRU（Least Recently Used）

LRU（最近最少使用）缓存算法基于最近使用的原则来管理缓存。以下是一个示例说明如何在 LRU 缓存中插入和访问元素：

假设给你一个数组，最大容量是 6：

• 当前数组状态：[1, 2, 3, 4, 5]
• 插入元素 6，数组变为：[1, 2, 3, 4, 5, 6]
• 使用元素 2，数组变为：[1, 3, 4, 5, 6, 2]（2 被移动到数组末尾，因为它是最近使用的）
• 插入元素 7，数组已经达到最大容量，需要淘汰最久未使用的元素（1）
• 删除元素 1，数组变为：[3, 4, 5, 6, 2, 7]

  LFU（Least Frequently Used）

  LFU（最少使用）缓存算法基于使用频率来管理缓存。以下是一个示例说明如何在 LFU 缓存中插入和访问元素：

  假设给你一个数组，最大容量是 6：

  • 当前数组状态：[1, 2, 3, 4, 5]（每个元素的使用频率为 1）
  • 插入元素 6，数组变为：[1, 2, 3, 4, 5, 6]
  • 使用元素 2，数组状态和使用频率变为：[(1,1), (2,2), (3,1), (4,1), (5,1), (6,1)]（2 的使用频率增加到 2）
  • 再次使用元素 2，数组状态和使用频率变为：[(1,1), (2,3), (3,1), (4,1), (5,1), (6,1)]（2 的使用频率增加到 3）
  • 插入元素 7，数组已经达到最大容量，需要淘汰使用频率最小的元素（使用频率为 1 的元素）
  • 删除使用频率为 1 的元素（1、3、4、5 或 6），假设删除元素 1，数组变为：[(2,3), (3,1), (4,1), (5,1), (6,1), (7,1)]

    这样，LFU 算法可以确保淘汰那些使用频率最低的元素，优先保留使用频率较高的元素。

    总结

    • LRU 算法：基于最近使用的原则管理缓存，最久未使用的元素会被淘汰。适用于需要快速访问最近使用过的元素的场景。
    • LFU 算法：基于使用频率管理缓存，使用频率最低的元素会被淘汰。适用于需要根据元素使用频率决定缓存策略的场景。

      实现 LRU 缓存策略

      LRU 缓存可以通过结合 Map 和 Doubly Linked List 实现。以下是一个 LRU 缓存的简单实现：

      class LRUCache {
          constructor(capacity) {
              this.capacity = capacity;
              this.cache = new 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);
              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);// delete the first key
              }
          }
      }
      // 测试 LRUCache
      const lruCache = new LRUCache(3);
      lruCache.put(1, 1);
      lruCache.put(2, 2);
      lruCache.put(3, 3);
      console.log(lruCache.get(1)); // 1
      lruCache.put(4, 4);
      console.log(lruCache.get(2)); // -1 (因为 key 2 已被淘汰)
      lruCache.put(5, 5);
      console.log(lruCache.get(3)); // -1 (因为 key 3 已被淘汰)
      console.log(lruCache.get(4)); // 4
      console.log(lruCache.get(5)); // 5
      

      实现 LFU 缓存策略

      LFU 缓存相对复杂一些，需要维护每个缓存项的使用频率。我们可以使用一个 Map 来存储缓存项和它们的使用频率，再使用另一个 Map 来存储每个频率对应的缓存项集合。

      class LFUCache {
          constructor(capacity) {
              this.capacity = capacity;
              this.cache = new Map();
              this.freqMap = new Map();
          }
          get(key) {
              if (!this.cache.has(key)) {
                  return -1;
              }
              const value = this.cache.get(key);
              const freq = this.freqMap.get(key) || 0;
              this.freqMap.set(key, freq + 1);
              return value;
          }
          put(key, value) {
              if (this.cache.size >= this.capacity) {
                  let minFreq = Infinity;
                  let minKey;
                  for (let [k, freq] of this.freqMap) {
                      if (freq < minFreq) {
                          minFreq = freq;
                          minKey = k;
                      }
                  }
                  this.cache.delete(minKey);
                  this.freqMap.delete(minKey);
              }
              this.cache.set(key, value);
              this.freqMap.set(key, (this.freqMap.get(key) || 0) + 1);
          }
      }
      const lfuCache = new LFUCache(3);
      lfuCache.put(1, 1);
      lfuCache.put(2, 2);
      lfuCache.put(3, 3);
      console.log(lfuCache.get(1)); // 1
      lfuCache.put(4, 4);
      console.log(lfuCache.get(2)); // -1 (因为 key 2 已被淘汰)
      lfuCache.put(5, 5);
      console.log(lfuCache.get(3)); // -1 (因为 key 3 已被淘汰)
      console.log(lfuCache.get(4)); // 4
      console.log(lfuCache.get(5)); // 5
      

      总结

      • LRU 缓存策略：根据最近使用的情况来淘汰最久未使用的项。通过 Map 结合 Doubly Linked List 实现。
      • LFU 缓存策略：根据使用频率来淘汰最少使用的项。通过两个 Map 实现，一个存储缓存项和它们的使用频率，另一个存储每个频率对应的缓存项集合。

        以上示例提供了这两种缓存策略的基本实现，可以根据具体需求进行扩展和优化。