哈希表 - 面试题 16.25. LRU 缓存 - 《数据结构与算法》

题目
思路分析

题目

题目来源：力扣（LeetCode)

设计和构建一个“最近最少使用”缓存，该缓存会删除最近最少使用的项目。缓存应该从键映射到值(允许你插入和检索特定键对应的值)，并在初始化时指定最大容量。当缓存被填满时，它应该删除最近最少使用的项目。
它应该支持以下操作：获取数据 get 和写入数据 put 。

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

示例:

LRUCache cache = new LRUCache( 2 / 缓存容量 / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4

思路分析

LRU 是一种十分常见的页面置换算法。
将 LRU 翻译成大白话就是：当不得不淘汰某些数据时（通常是容量已满），选择最久未被使用的数据进行淘汰。

题目让我们实现一个容量固定的 LRUCache 。如果插入数据时，发现容器已满时，则先按照 LRU 规则淘汰一个数据，再将新数据插入，其中「插入」和「查询」都算作一次“使用”。

可以通过 🌰 来理解，假设我们有容量为 22 的 LRUCache 和测试键值对 [1-1,2-2,3-3] ，将其按照顺序进行插入 & 查询：

插入 1-1，此时最新的使用数据为 1-1
插入 2-2，此时最新使用数据变为 2-2
查询 1-1，此时最新使用数据为 1-1
插入 3-3，由于容器已经达到容量，需要先淘汰已有数据才能插入，这时候会淘汰 2-2，3-3 成为最新使用数据
键值对存储方面，我们可以使用「哈希表」来确保插入和查询的复杂度为 O(1)O(1)。

另外我们还需要额外维护一个「使用顺序」序列。

我们期望当「新数据被插入」或「发生键值对查询」时，能够将当前键值对放到序列头部，这样当触发 LRU 淘汰时，只需要从序列尾部进行数据删除即可。

具体地：

LRU的缓存策略就像是维护一个队列，每次把访问的节点移动过到队列的末尾，当队列的长度大于缓存的长度，就把队列首部的元素给删除。
在调用get和put的时候，访问或者修改了的数据要被更新到最新访问的位置，所以会在这里处理数据的顺序。
其次存取的数据要能记录访问顺序，或者说要有序。

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  // 最大缓存容量
  this.capacity = parseInt(capacity, 10);
  // 数据缓存对象 
  this.cache = {};
  // 键名缓存数组，还可提供 key 的访问时间顺序
  this.keys = [];
};
/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  const idx = this.keys.indexOf(key);
  if (idx === -1) {
    return -1;
  }
  // 更新 keys 的顺序
  this.keys.push(this.keys.splice(idx, 1)[0]);
  return this.cache[key];
};
/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  const idx = this.keys.indexOf(key);
  if (idx !== -1) {
    // 更新原有数据和访问时间顺序
    this.keys.push(this.keys.splice(idx, 1)[0]);
  } else {
    if (this.keys.length === this.capacity) {
      // 超出缓存容量，删除缓存中最少使用的缓存
      this.cache[this.keys.shift()] = null;
    }
    this.keys.push(key);
  }
  this.cache[key] = value;
};