知多一点 LRU 缓存算法

hello~亲爱的观众老爷们大家好~最近沉迷 GraphQL 无法自拔，使用的过程中接触到不少的缓存机制，LRU 算法是比较常用的一种，因而对此产生了兴趣。正好之前刷 LeetCode 时完成了这答题，查阅了相关资料后翻看当初的实现，才知道之前是多蠢~因而有了这篇文章，记录下这个算法的思路。

本文主要介绍 LRU 缓存算法相关，并提供一个实现的思路。除了让大家知多一点 LRU 算法之外，希望整个解决问题的思路，能帮助各位在其他相似的场景中解决问题~以下是正文：

LRU 算法是什么

LRU 算法是缓存淘汰算法的一种，而 LRU 是 Least Recently Used 三个单词的缩写。简单地说，由于 内存空间有限，需要根据某种策略淘汰不那么重要的数据，用以释放内存。LRU 的策略是最早操作过的数据放最后，最晚操作过的放开始，按操作时间逆序，如果达到上限，则淘汰末尾的项。

整个 LRU 算法有一定的复杂度，扩展起来可以增添许多功能，生产环境中建议直接使用成熟的库，如 lru-cache 。而接下来将带来一个简单的实现，也是这个算法实现的骨架。

既然是算法，那必须先定义待解决的问题，此处参考 LeetCode 上的146. LRU缓存机制。

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。 写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

实现当然要完美，因而需要实现进阶的要求~

LRU 算法实现思路

算法其实可以拆分为三个方面去考虑，分别是获取、写入与淘汰。先考虑最简单的一方面：获取。

如需要在 O(1) 的时间复杂度中完成获取操作，那哈希表是一个很好的选择。JavaScript 的实现十分简单，使用对象即可，如果 key 不是简单类型，可以使用 Map 实现。按算法需要解决问题的场景，此处使用对象即可:

var LRUCache = function(capacity) {
  ...
  this.map = {};
  ...
};
复制代码

既然使用了哈希表，获取数据自然也能是 O(1)。

最麻烦是淘汰。尽管在哈希表中删除数据，时间复杂度也是常数，但我们无法得知该删除哪项。那修改哈希表中存储的 value ，从直接存储 value 改为存储一个对象，除了相关的值之外，再加上修改时间，这是否可行？

尽管有了时间，但淘汰是发生在合适呢？它发生在写入新数据之时，一旦需要淘汰数据，则需要遍历整个哈希表以获取最早操作的那一项。获取操作不再是 O(1) 时间复杂度。此路不通~

纯哈希表是完成不了这需求的，那么空间换时间怎样~用额外的变量，记录最早操作的那一项，需要淘汰时直接淘汰该项。接近一点目标，但仍然不行。考虑这个场景，先操作 A ，再操作 B ，最后再操作 A 。如需要淘汰一项，那需要淘汰的是 B ，然而变量记录的是 A ，不符合需求。

那不记录一项，用数组记录全部的项怎样，每次操作某项数据，就将这一项从数组中取出，再 push 进数组。再接近一点目标，但为了找到这一项，需要遍历数组，时间复杂度是 O(n)。

尽管上述的路达不到目标，但还是有收获：

• 需要使用哈希表；
• 淘汰数据的时间复杂度必须是 O(1)，因而需要额外的数据结构；
• 需要一种在 O(1) 时间复杂度，完成插入与删除操作的数据结构。

有没有这样的数据结构呢？有，那就是双向链表！链表在插入与删除操作上，都是 O(1) 时间的复杂度，但查找某个元素比较麻烦，是 O(n) 。然而哈希表的存在弥补了缺陷，查找元素的简直轻而易举！只要修改哈希表，将存储的值设为链表节点即可。

LRU 算法实现

有了思路，实现起来就相当简单了，此处直接贴一下全部代码：

const LRUCache = function(capacity) {
  this.map = {};
  this.size = 0;
  this.maxSize = capacity;
  // 链表的头
  this.head = {
    prev: null,
    next: null
  };
  // 链表的尾
  this.tail = {
    prev: this.head,
    next: null
  };
  this.head.next = this.tail;
};

LRUCache.prototype.get = function(key) {
  if (this.map[key] !== undefined) {
    // 将对应的节点抽出并设为链表的首项并返回对应的值
    const node = this.extractNode(this.map[key]);
    this.insertNodeToHead(node);
    return this.map[key].val;
  } else {
    return -1;
  }
};

LRUCache.prototype.put = function(key, value) {
  let node;
  if (this.map[key]) {
    // 如若该项存在，则抽取出来并设置为对应的值
    node = this.extractNode(this.map[key]);
    node.val = value;
  } else {
    // 如该项不存在，那就创造一个新节点
    node = {
      prev: null,
      next: null,
      val: value,
      key,
    };
    this.map[key] = node;
    this.size++;
  }
  // 将节点设为链表的首项
  this.insertNodeToHead(node);
  if (this.size > this.maxSize) {
    // 超过限制则删除最后一项
    const delNode = this.tail.prev;
    const delKey = delNode.key;
    this.extractNode(delNode);
    this.size--;
    delete this.map[delKey];
  }
};

// 插入节点到链表首项
LRUCache.prototype.insertNodeToHead = function(node) {
  const head = this.head;
  const oldFirstNode = this.head.next;
  node.prev = head;
  head.next = node;
  node.next = oldFirstNode;
  oldFirstNode.prev = node;
  return node;
}

// 从链表中抽取节点
LRUCache.prototype.extractNode = function(node) {
  const before = node.prev;
  const after = node.next;
  before.next = after;
  after.prev = before;
  node.prev = null;
  node.next = null;
  return node;
}
复制代码

重要的地方都加了注释，根据上面的思路，相信你一定明白上面的代码~可以看到，整个实现没有循环，因而所有操作的时间复杂度均可视为 O(1)。

小结

以上就是本文的全部内容啦！其实 LRU 算法还有其他实现方法，只是这种方法清晰易懂，效率也高，因而选用了这种思路。上面的代码也并非完美，比如没将操作链表相关的代码独立出去，但为了易于理解及节省篇幅，就跳过了。

事实上，前端是比较少用到算法和数据结构的，但不代表它们没有用。在之前的解题中，我就是使用数组 排序 的方法完成这道题，效率是相当低下。熟悉数据结构，有意识地在实际场景中使用它们，除了能解决问题之外，个人也会得到很大的提升。

以上是个人的一点浅见，感谢各位看官大人看到这里。知易行难，希望本文对你有所帮助~谢谢！