#独家

详细解析LRU算法的原理和实现方法

LRU算法原理

LRU缓存使用一个存储数据的结构（通常是哈希表和双向链表的结合），在缓存空间达到上限时，删除最久未被使用的数据。

步骤总结：

1. 访问数据：  当数据被访问时，我们将数据移动到缓存结构的前端，表示它是最近使用的数据。
2. 缓存满时：  当缓存满时，我们移除尾部的数据，这些数据是最久未使用的。

LRU算法实现方法

实现LRU算法的方法主要有：数组实现、哈希表+双向链表、使用Map数据结构，下面分别来看下这些方法的实现和各自的优缺点。

数组实现

我们可以使用一个数组来存储缓存的键值对，每次访问数据时，将其移动到数组的开头。当缓存满时，我们就移除数组的最后一个元素（即最久未使用的元素）。

class LRUCacheArray {
  private capacity: number;
  private cache: [number, number][];

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = [];
  }

  get(key: number): number {
    const index = this.cache.findIndex(([k]) => k === key);
    if (index === -1) return -1; // 如果没有找到
    const value = this.cache[index][1];
    this.cache.splice(index, 1); // 删除旧的数据
    this.cache.unshift([key, value]); // 将数据放到最前面
    return value;
  }

  put(key: number, value: number): void {
    const index = this.cache.findIndex(([k]) => k === key);
    if (index !== -1) {
      this.cache.splice(index, 1); // 删除旧的数据
    }
    this.cache.unshift([key, value]); // 将新数据放到最前面
    if (this.cache.length > this.capacity) {
      this.cache.pop(); // 如果缓存超出容量，移除最后一个元素
    }
  }
}

使用如下:

// 创建一个容量为 3 的缓存
const lruCache = new LRUCacheArray(3);

// 放入键值对
lruCache.put(1, 1); // 缓存: [ [1, 1] ]
lruCache.put(2, 2); // 缓存: [ [2, 2], [1, 1] ]
lruCache.put(3, 3); // 缓存: [ [3, 3], [2, 2], [1, 1] ]

// 访问一个存在的键
console.log(lruCache.get(2)); // 输出: 2, 缓存更新为 [ [2, 2], [3, 3], [1, 1] ]

// 添加一个新的键值对，导致最久未使用的键 1 被移除
lruCache.put(4, 4); // 缓存: [ [4, 4], [2, 2], [3, 3] ]

// 尝试获取被移除的键
console.log(lruCache.get(1)); // 输出: -1 (因为键 1 被移除)

// 访问一个存在的键
console.log(lruCache.get(3)); // 输出: 3, 缓存更新为 [ [3, 3], [4, 4], [2, 2] ]

// 添加一个新的键值对，导致最久未使用的键 2 被移除
lruCache.put(5, 5); // 缓存: [ [5, 5], [3, 3], [4, 4] ]

// 尝试获取被移除的键
console.log(lruCache.get(2)); // 输出: -1 (因为键 2 被移除)

以上代码首先我们定义了2个私有属性，如下:

• capacity：缓存的最大容量。表示最多存储多少个键值对。
• cache：一个数组，存储缓存中的数据，每个元素是一个 [key, value] 数组。key 是缓存的键，value 是对应的值。

然后在构造函数中，我们初始化了该2个值，紧接着，我们实现了对数据操作的get和put方法，其中get方法用于根据key来查找元素，找到该元素后，我们首先会根据索引值来删除旧的数据，然后将数据添加到数组的最前面，也就是将元素的位置移动到最前面，put方法和get方法同理，都是找到元素后，根据索引值删除该元素旧的位置，然后添加到新的位置，不过put方法还会判断缓存的元素是否超过了给定的容量，如果超过了给定容量，则会删除最后一个元素。

优缺点：

以上算法有如下优缺点：

• 优点：  实现简单，代码易于理解。
• 缺点：  查找、删除和插入操作的时间复杂度较高，最坏情况下是O(n)。

哈希表 + 双向链表实现

哈希表用于存储数据的快速查找，双向链表用于保持数据的访问顺序。每次访问数据时，我们将数据移到双向链表的头部，保证数据的顺序性。当缓存满时，直接从双向链表的尾部移除元素。

class Node {
  key: number;
  value: number;
  prev: Node | null = null;
  next: Node | null = null;
  constructor(key: number, value: number) {
    this.key = key;
    this.value = value;
  }
}

class LRUCache {
  private capacity: number;
  private cache: Map<number, Node>;
  private head: Node;
  private tail: Node;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
    this.head = new Node(0, 0);
    this.tail = new Node(0, 0);
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  private remove(node: Node) {
    // head <-> node <-> tail
    node.prev!.next = node.next;
    node.next!.prev = node.prev;
  }

  private insert(node: Node) {
    // head <-> node1 <-> tail
    // 插入node
    // head <-> node <-> node1 <-> tail
    node.next = this.head.next;
    node.prev = this.head;
    this.head.next!.prev = node;
    this.head.next = node;
  }

  get(key: number): number {
    const node = this.cache.get(key);
    if (!node) return -1;
    this.remove(node);
    this.insert(node);
    return node.value;
  }

  put(key: number, value: number): void {
    let node = this.cache.get(key);
    if (node) {
      this.remove(node);
      node.value = value;
    } else {
      node = new Node(key, value);
      this.cache.set(key, node);
    }
    this.insert(node);

    if (this.cache.size > this.capacity) {
      const tailNode = this.tail.prev!;
      this.remove(tailNode);
      this.cache.delete(tailNode.key);
    }
  }
}

这段代码使用了 Map 来存储数据，使用双向链表来维护元素的访问顺序，从而可以在常数时间内进行插入、删除和查找操作。

1. Node 类

第一个类定义了链表节点的数据结构，分别有四个属性，如下所示:

• key：缓存的键，标识每个缓存项。
• value：缓存的值，存储对应的实际数据。
• prev：指向前一个节点的指针。
• next：指向下一个节点的指针。

Node 类主要定义了缓存中的每个元素，它通过 prev 和 next 两个指针在双向链表中保持顺序。

2. LRUCache 类

LRUCache类定义了四个私有属性，分别如下:

• capacity：缓存的最大容量，表示能存储多少个键值对。
• cache：一个 Map 用于存储缓存中的键值对，以 key 为键，Node 为值。Map 提供了常数时间复杂度的查找操作。
• head 和 tail：用于双向链表的虚拟头节点和尾节点，它们帮助简化插入和删除操作，不需要考虑链表为空的特殊情况。

3. 构造函数

其中构造函数用来初始化私有属性。

• capacity 是初始化时传入的缓存大小。
• cache 是一个 Map 用来存储缓存的键值对。
• head 和 tail 是两个虚拟节点，head 的 next 指向 tail，tail 的 prev 指向 head，它们充当了双向链表的边界，方便插入和删除操作。

4. 辅助方法：remove 和 insert

然后实现了2个辅助操作链表节点的方法，一个是删除链表节点，另一个则是将节点添加到头部，这也应对了最近添加的目的。

• remove：将一个节点从链表中移除。通过修改前后节点的指针来实现删除操作。注意，prev 和 next 是强制解包 (!) 来避免 TypeScript 的空值检查。
• insert：将一个节点插入到链表的头部。头部表示最近使用的节点。

5. get 方法

get方法和通过数组实现的get方法同理，只不过这里有点差异，那就是删除和添加节点，我们需要通过对应的辅助方法来实现。

• 功能：获取缓存中 key 对应的值。如果缓存中不存在该键，则返回 -1。
• 操作步骤：
  1. 从 cache 中查找 key 对应的节点。
  2. 如果节点不存在，返回 -1。
  3. 如果节点存在，先将其从链表中移除，再将其插入到链表的头部，表示这是最近访问的节点。
  4. 返回该节点的 value。

6. put 方法

put方法本质上原理也和通过数组实现的put方法同理，只不过就是在添加节点的时候，需要重新设置一个新的节点，删除节点后还需要更新节点的value值。

• 功能：将一个 key-value 对插入缓存。如果缓存已满，会移除最久未使用的元素。
• 操作步骤：
  1. 如果 key 已经存在于缓存中，先将原有的节点从链表中移除，然后更新节点的 value 值。
  2. 如果 key 不存在，创建一个新的 Node 并插入到 cache 中。
  3. 将该节点插入到链表的头部，表示它是最近使用的。
  4. 如果缓存的大小超过了 capacity，则通过 tail.prev 找到最久未使用的节点，移除它并从 cache 中删除。

调用示例

const lruCache = new LRUCache(3);

lruCache.put(1, 1); // 缓存: [1=1]
lruCache.put(2, 2); // 缓存: [2=2, 1=1]
lruCache.put(3, 3); // 缓存: [3=3, 2=2, 1=1]

console.log(lruCache.get(2)); // 输出: 2, 缓存: [2=2, 3=3, 1=1]

lruCache.put(4, 4); // 缓存: [4=4, 2=2, 3=3], 移除键 1

console.log(lruCache.get(1)); // 输出: -1 (因为键 1 被移除)
console.log(lruCache.get(3)); // 输出: 3, 缓存: [3=3, 4=4, 2=2]

优缺点：

该方法的实现优缺点如下所示:

• 优点：  通过哈希表和双向链表的结合，插入、删除、访问操作的时间复杂度都为O(1)，非常高效。
• 缺点：  实现相对复杂，需要更多的内存和操作。

使用JavaScript的Map对象

现代JavaScript提供了Map对象，它本身是有序的，并且可以在O(1)时间内进行查找、插入和删除。因此，可以利用Map对象来实现LRU缓存。

class LRUCacheMap {
  private capacity: number;
  private cache: Map<number, number>;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key: number): number {
    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: number, value: number): void {
    if (this.cache.has(key)) {
      this.cache.delete(key); // 删除旧的值
    }
    this.cache.set(key, value);
    if (this.cache.size > this.capacity) {
      // 注意这里的理解
      const firstKey = this.cache.keys().next().value; // 删除最久未使用的元素
      this.cache.delete(firstKey);
    }
  }
}

优缺点：

该方法的实现优缺点如下所示:

• 优点：  Map对象本身支持插入、删除、访问操作，使用起来简单，性能优越。
• 缺点：  只有在支持Map的环境下才能使用（现代浏览器和Node.js支持），并且Map对象不会主动清除内存。

实际应用

下面我们将基于LRU缓存算法实现一个简单的图书管理系统。在这个系统中，缓存会存储最近访问的图书信息，如果图书信息过期（或缓存满），最久未访问的图书信息将被清除。

业务场景

假设我们有一个图书库，用户可以查看图书详情。为了提高效率，我们将最近查看过的图书信息缓存起来，以减少数据库查询次数。当缓存空间满时，我们会自动清除最久未查看的图书信息。

在线示例

以上示例解释

• LRU缓存类：  使用了Map实现了LRU缓存，在每次访问时将访问过的书籍移到Map的末尾，保证缓存中最久未访问的书籍会被淘汰。
• 图书管理界面：  用户可以点击书籍，查看书籍的详细信息。每当用户查看一本书时，系统会将该书信息缓存到LRU缓存中。
• 缓存状态：  页面下方会显示当前缓存中保存的书籍数量，并且用户可以手动清除缓存。

总结

LRU缓存算法是非常高效的缓存管理策略，能够合理地淘汰最久未使用的数据。在本文中，我们首先理解了什么是LRU算法以及该算法的原理，并且我们还通过三种方式来实现了该算法，也分析了每一种实现的优点和缺点，最后，我们基于该算法实现了一个简单的实际应用小示例，算是加深对该算法的理解，在我看来，了解并吃透一个算法，最重要的办法就是将算法应用到实际应用场景当中，这样才能吃透算法原理。

我已经吃透了LRU算法的原理和实现方法，你呢？

最后感谢大家阅读本文，如果对你有所帮助，望不吝啬点赞收藏，如果本文有描述不当，欢迎批评指正，如果个人理解有误，敬请谅解。