设计一个 LRU 缓存算法-146.LRU 缓存

什么是 LRU

LRU（Least Recently Used），即最近最少使用，它是一种缓存淘汰策略。用于管理缓存中的数据。它基于一个简单的原则：当缓存空间达到限制时，会优先淘汰最近最少使用的数据项，以腾出空间存储新的数据。

在 LRU 缓存中，数据项通常以键值对的形式存储，每当一个数据项被访问（读取或写入）时，它就被移到队列的前面，表示最近使用过。当需要淘汰数据时，队列末尾的数据项会被删除，因为它们是最近最少使用的。

像 Vue 的 keep-alive 就用到了这个缓存策略。

题目描述

这题在LeetCode 上有原题，146. LRU 缓存，这里摘抄了题目描述：

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

输入：

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

解题思路

在解题思路中，有一种比较简单的思路，就是采用Map +迭代器进行解题。但如果我将讲这个的话就没意义了，这里采用了更原始的解法：双向链表+Map。更偏向于对数据结构的考查，要是面试写出来也是加分的。

疑问1：为什么采用双向链表？而不是数组？

答：链表的插入和删除的时间复杂度是O(1)，但是数组插入和删除的时间复杂度是O(n)，至于为什么要用双向链表而不是单链表，原因是方便定位前一个节点，也就是方便插入和删除

疑问2：为什么还要用Map？不用行吗？

答：虽然链表的插入和删除的时间复杂度是O(1)，但是要删除节点之前还需要一个节点查找操作，链表的查找操作时间复杂度是O(n)，我需要利用Map做映射，从而把查找链表节点的时间复杂度降到O(1)。原则还是用空间换时间。

简单说一下get 和put的核心思路：

• get：通过key从map中查找缓存的节点
  • map 中找不到，return -1
  • map 中找到
    • 需要从双向链表中删除该节点，并把该节点移动到双向链表的头部
    • return 这个节点
• put：通过 key 从 map 中查找该节点
  • map 中找到
    • 更新 node.value 值；从链表中移除该节点；并把该节点插入到链表头部
  • map 中找不到，说明是新节点
    • 判断容量大小，超出容量，删除链表尾部节点，从 map 中删除，count--
    • 创建一个新节点，存入 map，并把该节点插入到链表头部，count++

双向链表设计

• [key, value] 为一组值
• prev：前驱节点
• next：后驱节点

class DLinkedNode {
  public key: number;
  public value: number;
  public prev: DLinkedNode; // 前驱
  public next: DLinkedNode; // 后驱
  constructor(key: number, value: number, prev: DLinkedNode = null, next: DLinkedNode = null) {
    this.key = key;
    this.value = value;
    this.prev = prev;
    this.next = next;
  }
}

LRU 类设计

属性：

• capacity: number：容量
• count: number：记录当前节点个数
• map: Map<number, DLinkedNode>：用来记录缓存中的节点，方便查找
• dummyHead: DLinkedNode：虚拟头结点，双向链表的一部分，方便在头部进行插入/删除操作
• dummyTail: DLinkedNode ：虚拟尾结点，双向链表的一部分，方便在尾部进行插入/删除操作

方法：

• constructor ：构造函数，主要做初始化容量、链表
• get(key: number): number：核心方法，查找缓存
• put(key: number, value: number): void：核心方法，设置缓存
• removeFromList(node: DLinkedNode): DLinkedNode：从链表中删除该节点，返回删除的节点
• addToHead(node: DLinkedNode): void：把一个节点添加到链表头部（注意：这里说的不是添加到虚拟头结点前面）
• popTail(): DLinkedNode：删除链表中尾结点（注意：不是删除虚拟尾结点）

这里贴一下整个代码，代码写了很多注释，内容太多，就不方便讲了。

class LRUCache {
  private capacity: number;
  private map: Map<number, DLinkedNode>;
  private dummyHead: DLinkedNode;
  private dummyTail: DLinkedNode;
  private count: number;

  constructor(capacity: number) {
    this.capacity = capacity;
    this.count = 0;
    this.map = new Map();

    // 建立两个虚拟头尾节点，方便操作
    this.dummyHead = new DLinkedNode(-Infinity, -1); // 虚拟头结点
    this.dummyTail = new DLinkedNode(Infinity, -1); // 虚拟尾节点
    this.dummyHead.next = this.dummyTail;
    this.dummyTail.prev = this.dummyHead;
  }

  /**
   * 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
   * @param key
   * @returns
   */
  get(key: number): number {
    const node = this.map.get(key);
    if (!node) return -1;

    this.removeFromList(node); // 从链表中移除该节点
    this.addToHead(node); // 再把该节点移动到链表头部

    return node.value;
  }

  /**
   * 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。
   * 如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
   * @param key
   * @param value
   */
  put(key: number, value: number): void {
    const node = this.map.get(key); // 获取链表中的node

    if (!node) {
      // 不存在于链表，是新数据
      if (this.count === this.capacity) {
        // 容量已满
        const tail = this.popTail(); // 删除链表中的尾结点
        this.map.delete(tail.key); // 从 map 中删除它
        this.count--; // 当前数目减一
      }

      // 创建一个新节点
      const newNode = new DLinkedNode(key, value); // 创建新的节点
      this.map.set(key, newNode); // 存入 map
      this.addToHead(newNode); // 将节点添加到链表头部
      this.count++; // 缓存数目 +1
    } else {
      // 已经存在于链表
      node.value = value; // 更新value
      this.removeFromList(node); // 从链表中移除该节点
      this.addToHead(node); // 再把该节点移动到链表头部
    }
  }

  /**
   * 从链表中移除该节点
   * @param node
   * @returns
   */
  removeFromList(node: DLinkedNode): DLinkedNode {
    let temp1 = node.prev; // 暂存它的后继节点
    let temp2 = node.next; // 暂存它的前驱节点
    temp1.next = temp2; // 前驱节点的next指向后继节点
    temp2.prev = temp1; // 后继节点的prev指向前驱节点

    // 返回被删除的节点
    return node;
  }

  /**
   * 把一个节点添加到链表头部
   * @param node
   */
  addToHead(node: DLinkedNode): void {
    // 将该节点插入到虚拟头结点和第一个节点之间，作为第一个节点
    node.prev = this.dummyHead;
    node.next = this.dummyHead.next;
    this.dummyHead.next.prev = node;
    this.dummyHead.next = node;
  }

  /**
   * 删除链表中尾结点，不是虚拟尾结点
   * @returns
   */
  popTail(): DLinkedNode {
    // 删除链表尾节点
    const tail = this.dummyTail.prev; // 通过虚拟尾节点找到它
    this.removeFromList(tail); // 删除该真实尾节点
    return tail; // 返回被删除的节点
  }
}

到这就结束了，有什么问题，欢迎在评论区讨论~~