🔙 Back

LRU 缓存策略

什么是 LRU

LRU 全称是 Least Recently Used，即最近最少使用。LRU 缓存是一种常见的缓存策略，它的主要思想是：如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也就越小。

在 LRU 缓存策略中，我们将最近使用的数据放在容器的前面，每当有新的数据访问时，我们就将这个新数据放在容器的前面。当容器的大小超过了缓存的最大容量时，我们就删除容器尾部的数据。

LRU Spec test case

我们先根据上面 LRU 的定义和特性，编写一些测试用例

// 测试用例
describe("LRUCache", function () {
  let cache;

  beforeEach(function () {
    cache = new LRUCache(3); // 缓存容量为3
  });

  it("should return correct value after put", function () {
    cache.put("key1", "value1");
    expect(cache.get("key1")).toEqual("value1");
  });

  it("should return -1 for non-existent values", function () {
    expect(cache.get("key1")).toEqual(-1);
  });

  it("should evict least recently used item", function () {
    cache.put("key1", "value1");
    cache.put("key2", "value2");
    cache.put("key3", "value3");
    cache.put("key4", "value4"); // 此时key1应该被剔除

    expect(cache.get("key1")).toEqual(-1);
    expect(cache.get("key2")).toEqual("value2");
    expect(cache.get("key3")).toEqual("value3");
    expect(cache.get("key4")).toEqual("value4");
  });

  it("should move recently used item to front", function () {
    cache.put("key1", "value1");
    cache.put("key2", "value2");
    cache.put("key3", "value3");
    cache.get("key1"); // key1被访问，应该被移动到最前
    cache.put("key4", "value4"); // 此时key2应该被剔除，因为它是最近最少访问的

    expect(cache.get("key1")).toEqual("value1");
    expect(cache.get("key2")).toEqual(-1);
    expect(cache.get("key3")).toEqual("value3");
    expect(cache.get("key4")).toEqual("value4");
  });
});

TS 版本的实现

实现 LRU 缓存有多种方式，其中最常见的一种方式是使用双向链表（Double Linked List）和哈希表（Hash Map）。双向链表用于存放所有的数据，其插入、删除的时间复杂度都是 O(1)。哈希表则用于记录每个数据在双向链表中的位置，使得我们能够以 O(1)的时间复杂度找到任何数据。

class ListNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.hash = {};
    this.count = 0;
    this.dummyHead = new ListNode();
    this.dummyTail = new ListNode();
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }

  get(key) {
    let node = this.hash[key];
    if (node == null) return -1;
    this.moveToHead(node);
    return node.value;
  }

  put(key, value) {
    let node = this.hash[key];
    if (node == null) {
      if (this.count == this.capacity) {
        this.removeLRUItem();
      }
      node = new ListNode(key, value);
      this.hash[key] = node;
      this.addToHead(node);
      this.count++;
    } else {
      node.value = value;
      this.moveToHead(node);
    }
  }

  moveToHead(node) {
    this.removeFromList(node);
    this.addToHead(node);
  }

  removeFromList(node) {
    let tempForPrev = node.prev;
    let tempForNext = node.next;
    tempForPrev.next = tempForNext;
    tempForNext.prev = tempForPrev;
  }

  addToHead(node) {
    node.prev = this.dummyHead;
    node.next = this.dummyHead.next;
    this.dummyHead.next.prev = node;
    this.dummyHead.next = node;
  }

  removeLRUItem() {
    let tail = this.popTail();
    delete this.hash[tail.key];
    this.count--;
  }

  popTail() {
    let tailItem = this.dummyTail.prev;
    this.removeFromList(tailItem);
    return tailItem;
  }
}

let cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
console.log(cache.get(1)); // 返回  1
cache.put(3, 3); // 该操作会使得关键字 2 作废
console.log(cache.get(2)); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得关键字 1 作废
console.log(cache.get(1)); // 返回 -1 (未找到)
console.log(cache.get(3)); // 返回  3
console.log(cache.get(4)); // 返回  4

增加命中率

在实际应用场景中，我们需要知道如何评价 LRU 的作用，可以通过一个指标来观测。这个指标就是“命中率”。

我们可以在代码中添加一些变量来跟踪缓存的命中次数和请求次数，然后使用这两个变量来计算命中率。

例如，我们可以在 LRUCache 的构造函数中添加两个变量，hits 表示命中次数，requests 表示请求次数。每次调用 get 方法时，我们都将 requests 加 1，如果缓存命中，我们将 hits 加 1。

然后，我们可以添加一个新的方法 getHitRate，返回缓存的命中率。

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.map = new Map();
    // 添加用于跟踪命中率的变量
    this.hits = 0;
    this.requests = 0;
  }

  get(key) {
    this.requests++; // 请求次数加1
    if (this.map.has(key)) {
      this.hits++; // 命中次数加1
      let value = this.map.get(key);
      this.map.delete(key);
      this.map.set(key, value);
      return value;
    }
    return -1;
  }

  put(key, value) {
    if (this.map.has(key)) {
      this.map.delete(key);
    } else if (this.map.size >= this.capacity) {
      this.map.delete(this.map.keys().next().value);
    }
    this.map.set(key, value);
  }

  // 添加新的方法，获取命中率
  getHitRate() {
    return this.requests ? this.hits / this.requests : 0;
  }
}

Map 版本的实现

JavaScript 中的 Map 数据结构确实可以用来实现 LRU（Least Recently Used）缓存算法。

使用 Map 的理由在于其内部维护了一个键值对的插入顺序。当一个已存在的键再次被 set 时，这个键会重新移动到末尾。这个特性使得我们可以利用 Map 来表示一种最近最少使用（LRU）的缓存策略。当缓存达到上限后，我们可以简单地删除 Map 中的第一个元素（最早被插入但最久未使用的元素）。

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);
    }
  }
}

然而，这种方式的性能并不是最优的，因为每次在 Map 中删除一个元素的操作都需要 O(n)的时间复杂度。如果你需要在性能更加关键的场景中实现 LRU 算法，可能需要配合其他数据结构（例如双向链表）来优化。

在 Messenger App 的应用场景

在 Messenger（即时通讯应用）中，LRU（最近最少使用）缓存策略可以有多种应用场景：

  1. 消息缓存：Messenger 应用通常需要在本地设备上缓存最近的聊天消息，以便用户可以在没有网络连接的情况下查看他们。当设备的存储空间有限时，可以使用 LRU 策略来确定哪些聊天记录需要被删除。最近最少使用的聊天记录（即用户最不可能查看的）将被优先移除。

  2. 图片和媒体文件缓存：Messenger 应用中经常会包含图片、音频、视频等媒体文件。这些文件在首次加载后，可以被缓存到本地，以便后面快速加载。然而，这些文件通常会占用大量存储空间。因此，当缓存空间不足时，可以使用 LRU 策略来决定哪些文件被移除，即最近最少使用的文件将被优先删除。

  3. 联系人列表缓存：联系人列表和用户信息通常也会被 Messenger 应用缓存。当内存不足时，可以使用 LRU 策略来决定哪些联系人或用户信息被从缓存中删除。

通过使用 LRU 缓存策略，Messenger 应用可以更有效地管理有限的存储空间，同时保证用户最关心的数据（最近和频繁使用的）始终可以被快速访问。