前端必会的面试高频算法：LRU 缓存淘汰算法

序言

之前的面试中，面试官问了我这样一个问题。如果你首次进入一个页面，每看一条博客都会记入缓存中，下次就可直接读取缓存而不用重新请求。那么假设存储缓存的容器最大容量是100条，你如何设计一个算法来保证缓存达到容量后，淘汰最早记入容器的缓存数据。

当时我的第一反应是每次存入容器的时候赋予一个标识，时间戳或是序号来标记存入的顺序，但是这么做不论是读取缓存还是替换等操作都需要遍历，开销太大，于是我想到了一种比较可行的方法，队列。

队列

队列是一种常见的数据结构，有着先进先出的特性，在队列的一头进行插入操作，另一头删除。对于我们的题目来说，队列无疑是一种行得通的方法。在开始之前，我们先整理一下思路和需要实现的重点。

1. 需要实现存入数据（put）和查询数据（get）方法
2. 插入新数据时如果超过队列容量，删除最早进入的数据
3. 查询队列中存在的数据后，把该数据 push 到队列开头

那么我们就开始实现代码吧：

// 队列
const List = [];

class Node {
  constructor(key, value) {
    this.key = key;
    this.value = value;
  }
}

class cacheList {
  constructor (capacity) {
    // 容量，限定队列的长度
    this.capacity = capacity;
  }

  isFull() {
    return List.length === this.capacity;
  }

  isNodeInList(key) {
    for (let i = 0; i < List.length; i++) {
      if (List[i].key === key) {
        return List[i];
      }
    }
    return false;
  }

  remove(key) {
    for (let i = 0; i < List.length; i++) {
      if (List[i].key === key) {
        const node = List.splice(i, 1);
        return node[0];
      }
    }
  }

  put(key, value) {
    // 先判断节点是否存在，如果存在直接更新节点的value
    if (this.isNodeInList(key)) {
	  // 更新后把原节点删除，移到队列头部
      const node = this.remove(key);
      node.value = value;
      List.unshift(node);
    } else {
      if (this.isFull()) {
	    // 超出队列容量，删除尾部节点
        List.pop();
      }
      List.unshift(new Node(key, value));
    }
  }

  get(key) {
    if (this.isNodeInList(key)) {
	  // 移动节点到队列头部
      const node = this.remove(key);;
      this.put(key, node.value);
    } else {
	  return -1;
	}
  }
}

到这里算是实现了基本功能，但是算法嘛肯定不能只为了完成任务，我们可以看到有些可以优化的地方。比如我们查询数据是否存在于队列中时，需要去遍历队列。同样，删除节点时也需要先遍历到节点所在的位置，这也意味着我们的 put 和 get 操作的时间复杂度都在 O(opacity)。那么我们来想想更好的方法吧。

hashMap + 双向链表

对于我们每次查询节点位置都需要遍历的情况，我们可以通过 hashMap 来映射节点，这样可以方便我们找出节点的位置。

而双向链表则按照我们对于缓存的使用顺序，靠近头部的节点为最新的，靠近尾部的节点是待淘汰的。（提问：为什么要用双向链表，单向链表无法满足嘛？）

这样一来，我们的思路就可以优化成：通过 hashMap 找出节点在双向链表中的位置，然后通过修改 prev 和 next 来移动节点的位置。那么 put 和 get 操作都可以将时间复杂度优化到 O(1)，话不多说，写代码：

// 双向链表
class DoubleLinkedListNode {
  constructor(key, value) {
      this.key = key;
      this.value = value;
      this.prev = null;
      this.next = null;
  }
}

class LRUCache {
  constructor (capacity) {
    this.capacity = capacity;
    this.hashMap = {};
	// 这里需要添加一个头尾假节点，可简化插入和删除操作代码，不需要再特别对头尾节点进行特殊处理
    this.fakeHead = new DoubleLinkedListNode(null, null);
    this.fakeTail = new DoubleLinkedListNode(null, null);
    this.fakeHead.next = this.fakeTail;
    this.fakeTail.prev = this.fakeHead;
  }

  isFull() {
    return Object.keys(this.hashMap).length === this.capacity;
  }

  remove(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
    node.prev = null;
    node.next = null;
    return node;
  }

  add(node) {
    const firstNode = this.fakeHead.next;
    node.prev = this.fakeHead;
    node.next = firstNode;
    firstNode.prev = node;
    this.fakeHead.next = node;
  }

  put(key, value) {
    if (this.hashMap[key]) {
      const node = this.hashMap[key];
      node.value = value;
      this.add(this.remove(node));
    } else {
      if (this.isFull()) {
        const lastNode = this.fakeTail.prev;
        delete this.hashMap[lastNode.key];
        this.remove(lastNode);
      }
      const node = new DoubleLinkedListNode(key, value);
      this.hashMap[key] = node;
      this.add(node);
    }
  }

  get(key) {
    if (this.hashMap[key]) {
      const node = this.hashMap[key];
      this.add(this.remove(node));
      return node.value;
    } else {
      return -1;
    }
  }
}

可以看到，我们不需要再通过遍历来找到节点的位置，移动节点也方便了很多。继续回到刚才提到的问题，为什么不能使用单链表呢？当你要移动节点至链表头部或删除节点时，你需要把当前节点的上一个节点的 next（node.prev.next） 设置为当前节点的 next (node.next)，如果时单向链表，你需要通过遍历才能找到当前节点的上一个节点，又增加了时间上的花销。

不过在这里还有一个值得一提的小问题，hashMap 是 java 中的数据类型，是有数组 + 链表组成的，而 hashMap 的 get 操作的时间复杂度只是在理想状态下为 O(1)。而上述我们使用 JS 的对象模拟 hashMap 的实现，所以我们可以忽略这个小问题。