LRU

最近最少使用（LRU）缓存按使用顺序组织项目，允许您快速识别最长时间未使用的项目。

想象一下衣服架，衣服总是挂在一边。要找到最近最少使用的项目，请查看架子的另一端的项目。

问题描述

实现LRUCache类：

• LRUCache(int capacity) 使用正数大小capacity初始化LRU缓存。
• int get(int key) 如果存在key，则返回key的值，否则返回undefined。
• void set(int key, int value) 如果存在key，则更新key的值。否则，将key-value对添加到缓存中。如果此操作导致键的数量超过capacity，则删除最近最少使用的键。

函数get()和set()的平均时间复杂度必须为O(1)。

实现

版本1：双向链表 + 哈希映射

请参阅LRUCache.js中的LRUCache实现示例。该解决方案使用HashMap快速访问缓存项（平均时间复杂度为O(1)）和DoublyLinkedList快速推广和驱逐缓存项（以保持最大允许的缓存容量，平均时间复杂度为O(1)）。

链表

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

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.size = 0;
    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;
  }

  get(key) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      this.moveToHead(node);
      return node.value;
    }
    return -1;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      node.value = value;
      this.moveToHead(node);
    } else {
      const newNode = new Node(key, value);
      this.cache.set(key, newNode);
      this.addToHead(newNode);
      this.size++;
      if (this.size > this.capacity) {
        const tailNode = this.removeFromTail();
        this.cache.delete(tailNode.key);
        this.size--;
      }
    }
  }

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

  removeFromList(node) {
    const prevNode = node.prev;
    const nextNode = node.next;
    prevNode.next = nextNode;
    nextNode.prev = prevNode;
  }

  addToHead(node) {
    const nextNode = this.head.next;
    this.head.next = node;
    node.prev = this.head;
    node.next = nextNode;
    nextNode.prev = node;
  }

  removeFromTail() {
    const tailNode = this.tail.prev;
    this.removeFromList(tailNode);
    return tailNode;
  }
}

版本2：有序映射

第一个使用双向链表的实现方法对于学习目的和更好地理解如何在进行set()和get()时实现平均O(1)时间复杂度是很好的。

然而，更简单的方法可能是使用JavaScript的Map对象。Map对象保存键值对，并通过记住键的原始插入顺序来保持原始顺序。我们可以利用这一点，通过删除和重新添加项来将最近使用的项保持在映射的“末尾”。如果缓存容量溢出，位于Map开头的项将首先被驱逐。可以使用map.keys()之类的IterableIterator来检查项的顺序。

class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    this.keySet = new Set();
  }

  get(key) {
    if (this.cache.has(key)) {
      const value = this.cache.get(key);
      // 更新访问顺序
      this.keySet.delete(key);
      this.keySet.add(key);
      return value;
    }
    return -1;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      // 更新已存在的键值对
      this.cache.set(key, value);
      // 更新访问顺序
      this.keySet.delete(key);
      this.keySet.add(key);
    } else {
      // 插入新的键值对
      if (this.cache.size === this.capacity) {
        // 达到容量上限，移除最久未使用的键值对
        const oldestKey = this.keySet.values().next().value;
        this.cache.delete(oldestKey);
        this.keySet.delete(oldestKey);
      }
      // 添加新的键值对
      this.cache.set(key, value);
      this.keySet.add(key);
    }
  }
}

复杂度

	平均
空间	O(n)
获取项	O(1)
设置项	O(1)

参考资料

• LeetCode上的LRU Cache
• InterviewCake上的LRU Cache
• 维基百科上的LRU Cache