[数据结构与算法]【算法-LeetCode】146. LRU 缓存机制（双向链表；Map；栈）

146. LRU 缓存机制 - 力扣（LeetCode）

发布：2021年9月11日15:01:14

问题描述及示例

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。

实现 LRUCache 类：

• LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 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

提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lru-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的题解

解题之前首先要了解 LRU 页面调度算法的原理。

下面是用栈来描述的模型：

其他详细描述请参阅：《计算机操作系统（第四版）》P176~P177 汤小丹、梁红兵、哲凤屏、汤子瀛 编著——西安电子科技大学出版社

可以看见，实现 LRU 算法的关键就是一个合适的存储结构。选用栈来模拟的话，可以利用栈元素的先进先出的特点很容易地找到最近最久未使用的页面的页面号——也就是栈底元素。而栈顶元素则是刚刚被访问的那个页面的页面号。所以我们只要维护好栈底和栈顶元素就好了。

但是由于本题中的需要被访问的元素不是单纯的一个页面号，而是 {key, val}形式的对象。其中的 key 其实可以看做是我们上面提到的页面号，而 val 值则需要另外再通过一个映射关系来获取。而这个映射关系就可以用哈希表来实现。

成功前的尝试（用数组模拟栈结构；Map模拟哈希表）

我首先想到的方法就是用一个数组来模拟栈的结构，然后用纯对象或是 Map 对象来来模拟哈希表，因为 Map 有很多方便的方法可供我们调用，所以我觉得选用这种类型的对象更合适。

①首先是通过构造函数给每一个 LRUCache 实例对象身上绑定三个属性：

• capacity 属性用来代表缓存区的最大容量；
• keyStack 属性用来维护缓存中关键字 key 的顺序（这是实现算法的关键结构）；
• cache 属性用来维护缓存中关键字 key 和 val 的映射关系（这是真正存储缓存数据的结构）；

这些属性之间的关系大致如图：

仔细观察上图，思考一下为什么不直接只用 cache 来维护 key 呢？原因是 Map 类型的对象不能维护其元素的顺序性。虽说 Map 对象保存键值对，并且能够记住键的原始插入顺序，但是却不能像数组通过元素的下标改变元素顺序一样通过 key 来随意调换元素顺序。这也是为什么往往用数组来模拟栈结构。

更新：2021年9月11日21:52:38
经过改进，似乎可以直接使用Map类型的 cache 变量来完成 key 关键字的顺序性维护。关键就在于Map 的遍历顺序就是插入顺序。详细解释看下方的【我的题解2】。

②接下来就是实现 LRUCache.prototype.get(key) 方法。这个方法可以看做是对缓存内容的访问。

• 首先判断 keyStack 中有没有我们传入的 key 关键字。

• 如果有的话，则将这个 key 关键字提到栈顶，

  我的实现方法就是先用数组的 splice() 方法从 keyStack 中删除这个 key 关键字，然后再用数组的 push() 方法将这个关键字压入栈顶。

  然后用Map对象的 get() 方法获取这个 key 关键字所对应的 val 值并将其作为返回值返回。

• 如果没有的话，就直接返回 -1。

②接下来就是实现 LRUCache.prototype.put(key, value) 方法。这个方法可以看做是对缓存内容先做一次访问，然后根据访问结果来决定将新内容存入缓存区的方式。

• 首先判断 keyStack 中有没有我们传入的 key 关键字。

• 如果有的话，则修改这个 key 关键字所对应的 val 值。

  我的实现方法就是直接用Map对象的 set() 方法更新 val 值。因为Map对象的 set 方法有这样一个特点：如果对同一个键多次赋值，后面的值将覆盖前面的值。

  因为存入新的缓存也算是一次访问，所以要同时调用一次 LRUCache.prototype.get(key) 方法，来保证我们新存入的值所对应的 key 在 keyStack 的栈顶。

• 如果没有的话，再判断 keyStack 的长度是否达到该 LRUCache 的最大容量。

  • 如果没有达到的话，说明 keyStack 还能容纳元素，此时直接将新的元素压入栈顶即可。
  • 如果已经达到了的话，说明 keyStack 已经满了，必须把其中的最近最久未使用的元素从 keyStack 删除，其实就是把栈底元素给删除。然后再将新元素压入栈顶。

总体思路就描述完了，下面的代码就是完全按照这个思路实现的。所以就不再逐行注释了。

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.capacity = capacity;
  this.keyStack = [];
  this.cache = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  let keyIndex = this.keyStack.indexOf(key);
  if(keyIndex !== -1) {
    // for(let i = keyIndex; i < this.keyStack.length - 1; i++) {
    //   this.keyStack[i] = this.keyStack[i + 1];
    // }
    // this.keyStack[this.keyStack.length - 1] = key;
    // 上面注释掉的这几行代码和下面两行代码的效果是一样的。
    this.keyStack.splice(keyIndex, 1);
    this.keyStack.push(key);
    
    return this.cache.get(key);
  }
  return -1;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
  if(!this.keyStack.includes(key)){
    if(this.keyStack.length !== this.capacity) {
      this.keyStack.push(key);
    } else {
      this.keyStack.shift();
      this.keyStack.push(key);
    }
  }
  // 注意这个访问操作不能忽略
  this.get(key);
  this.cache.set(key,value);
};


提交记录
20 / 21 个通过测试用例
状态：超出时间限制
时间：2021/09/11 12:10	

然后正当我充满自信地提交时，我突然发现有一个超长的测试用例没有通过，所以我觉得应该是上面的程序虽然思路正确，但是性能太差了。在面对大量数据的连续操作时还是经受不住考验。

我的题解1（用数组模拟栈结构；Map模拟哈希表）

由于上面的程序运用数组来模拟栈结构，所以当涉及大量的数组元素的位置调换或删减某个元素时，线性空间的性能短板自然就显露出来了。没办法只能用其他结构来模拟了。运行时间超时，那么往往可以通过更多的空间分配来平衡时间消耗。于是我想到了可以非常自由地删减某个元素且不会引起大量数据更改的数据结构：双向链表。

于是我就用双向链表来模拟栈结构。

首先是分析单个链表节点需要有哪些结构：

• key 属性是缓存内容的 key 关键字；
• val 属性是缓存内容的 val 值；
• pre 属性是当前节点的前驱节点；
• next 属性是当前节点的后继节点。

其中 key 和 val 都需要在我们创建链表节点时用参数的方式指定，如果未传入则默认为 -1（因为题目的【提示】说了 0 <= key <= 10000 ）。而 pre 和 next 则默认为空对象 null。

因为要用双向链表来模拟栈结构，所以 LRUCache 的构造函数中有关栈结构的初始化也要有所变化。

我是用一个辅助头结点 keyHead 和辅助尾结点 keyRear 来做初始化的。这两个结点将始终在链表的头部和尾部，这样就方便我们对栈底和栈顶的一些操作。

此时 cache 这个Map类型的结构里所存储的键值对的形式也有所改变，其中 key 仍然表示缓存对象中的 key 关键字，而 value 则是这个 key 关键字所对应的链表节点（准确地来说其链表节点对象的内存地址）。

此后的思路和上面用数组的方法一样，只不过有些细节的实现有所改变。比如结点入栈时其实是往keyRear 前插入节点；而删除栈底元素则是改变 keyHead 的 next 域和 keyHead.next 的 pre 域的指向。详解可看下方注释。

// 链表节点的构造函数，这是我们额外加的函数
function ListNode(key, val) {
  this.key = key === undefined ? -1 : key;
  this.val = val === undefined ? -1 : val;
  this.next = this.pre = null;
}

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
  this.capacity = capacity;
  
  // 初始化栈结构，其运行结果就是上面的那张图，注意操作这些实例属性时不要忘记加上this
  this.keyHead = new ListNode(-1, 'head');
  this.keyRear = new ListNode(-1, 'rear');
  this.keyHead.next = this.keyRear;
  this.keyRear.pre = this.keyHead;
  // 仍然用map结构来存储映射关系，只不过cache的value值所存储的对象变为了一个链表节点对象
  this.cache = new Map();
};

/** 
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
  // 判断链表中是否有某个值比较复杂，所以用map对象的has()方法来判断当前key是否已在缓存中
  if(this.cache.has(key)) {
    // 如果缓存中已经有当前key了，则获取当前key所对应的节点对象keyNode
    let keyNode = this.cache.get(key);
    // 把keyNode从链表中删除
    keyNode.pre.next = keyNode.next;
    keyNode.next.pre = keyNode.pre;
	// 再把keyNode插入链表栈的末尾
    keyNode.next = this.keyRear;
    keyNode.pre = this.keyRear.pre;
    this.keyRear.pre.next = keyNode;
    this.keyRear.pre = keyNode;
	// 最后把找到的这个缓存节点的val值作为返回值返回
    return keyNode.val;
  }
  // 如果缓存中没有当前key，则直接返回 -1
  return -1;
};

/** 
 * @param {number} key 
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  // 如果缓存中不存在当前key
  if (!this.cache.has(key)) {
    // 创建一个新的节点，并设置其key和value
    let newKeyNode = new ListNode(key, value);
    // 如果当前缓存容量已满
    if (this.cache.size === this.capacity) {
      // 从缓存中删除当前key及其所对应的节点
      this.cache.delete(this.keyHead.next.key);
      // 并且同时把链表栈底的节点给删除，注意下面两句的顺序千万不能调换【详看下方补充】
      this.keyHead.next.next.pre = this.keyHead;
      this.keyHead.next = this.keyHead.next.next;
      // 本来后续应该是把要放入的新节点插入链表栈的栈顶的，
      // 但是这部分逻辑和下面缓存未满时的情况重复了,所以放到了if判断外
    }
    // 如果当前缓存未满，直接把新节点插入链表栈的栈顶
    newKeyNode.next = this.keyRear;
    newKeyNode.pre = this.keyRear.pre;
    this.keyRear.pre.next = newKeyNode;
    this.keyRear.pre = newKeyNode;
    // 同时把新节点放入cache中形成映射
    this.cache.set(key, newKeyNode);
  } else {
  	// 如果缓存中存在当前key，则修改该key在cache中对应的val值
    this.cache.get(key).val = value;
  }
  // 和上面数组实现时一样，put的操作其实也是一种对缓存的访问，
  // 所以这里要调用一下get方法来让被访问的块缓存被提到链表栈的栈顶
  this.get(key);
};


提交记录
22 / 22 个通过测试用例
状态：通过
执行用时：620 ms, 在所有 JavaScript 提交中击败了73.60%的用户
内存消耗：88.9 MB, 在所有 JavaScript 提交中击败了87.72%的用户
时间：2021/09/11 15:15

这种方法虽然解决了超时的问题，但是也花费了更多的空间，是一种典型的用空间来换时间的做法。

【补充】
下面是先 this.keyHead.next.next.pre = this.keyHead; 再 this.keyHead.next = this.keyHead.next.next;的动态图。

下面是先 this.keyHead.next = this.keyHead.next.next; 再 this.keyHead.next.next.pre = this.keyHead; 的动态图。

我的题解2（只用Map结构）

更新：2021年9月11日21:52:38

之前我说无法用Map来模拟栈结构，因为我觉得Map类型对象中元素是无序的，无法准确地标识栈顶，也无法确定各个元素的先后进入的顺序。后来我仔细想了想，发现其实是可以的，关键就是【Map 的遍历顺序就是插入顺序】这一特性，也就是说，当你遍历Map对象中的元素时，所获得结果的顺序和元素插入的顺序是一样的。比如：

let map = new Map();
map.set(1, 'one');
map.set(3, 'three');
map.set(2, 'two');

let keyValArr = [...map.entries()];
console.log(keyValArr);
	(3) [Array(2), Array(2), Array(2)]
	0: (2) [1, "one"]
	1: (2) [3, "three"]
	2: (2) [2, "two"]
	length: 3

let keyArr = [...map.keys()];
console.log(keyArr);
	(3) [1, 3, 2]
	0: 1
	1: 3
	2: 2
	length: 3
	
let valArr = [...map.values()];
console.log(valArr);
	(3) ["one", "three", "two"]
	0: "one"
	1: "three"
	2: "two"
	length: 3

详细的遍历方法可以参看下方的相关内容：

参考：Set 和 Map 数据结构 - ES6 教程 - 网道
参考：Map.prototype.entries() - JavaScript | MDN

也就是说，现在 cache 有两个任务：维护各个缓存的访问顺序；同时保存 key 和 val 的映射关系。能够把 cache 当做栈来使用，全依赖于上面我们提到的那个Map对象的遍历特性。

核心思路和之前讲得一致，只是有一些实现方面的细微差别。详解看下方注释。

/**
  * @param {number} capacity
  */
var LRUCache = function (capacity) {
  // 因为我们直接利用Map对象遍历时的特性来实现类似栈的效果，
  // 所以原先的keyStack或是头尾节点就不需要了
  this.capacity = capacity;
  this.cache = new Map();
};

/** 
  * @param {number} key
  * @return {number}
  */
LRUCache.prototype.get = function (key) {
  // 如果缓存中存在当前想要访问的key
  if (this.cache.has(key)) {
    // 获取当前key所对应的val值，因为后续要把它放到栈顶
    let targetVal = this.cache.get(key);
    // 从缓存中删除当前key对应的项
    this.cache.delete(key);
    // 再重新把删除的那个项存入缓存，这句和上面那句合起来的的效果
    // 就是把命中的那个key所对应的项提到栈顶
    this.cache.set(key, targetVal);
    // 最后将命中的那个key所对应的val值作为返回值返回。
    return targetVal;
  }
  // 如果缓存中没有当前想要访问的key，则直接返回-1
  return -1;
};

/** 
  * @param {number} key 
  * @param {number} value
  * @return {void}
  */
LRUCache.prototype.put = function (key, value) {
  // 如果缓存中没有当前key，也就说明这个key是第一次进入缓存
  if (!this.cache.has(key)) {
  	// 如果缓存容量已满（其实这个if判断可以和上面那个合并，但是为了好理解，我特意拆开了）
    if (this.cache.size === this.capacity) {
      // 遍历缓存中的key值，这里利用了【Map对象的遍历顺序和插入顺序是一致的】这一特点
      // 遍历的结果是一个MapIterator对象，将其进行结构赋值到一个数组中方便读取
      let keyArr = [...this.cache.keys()];
      // 删除缓存结构中栈底的那个项，它的key值就是上面获取的keyArr的第一项
      this.cache.delete(keyArr[0]);
    }
  }
  // 如果缓存中有当前key，则下面的set()是用来更新这个key所对应的val值的；
  // 如果缓存中没有当前key，且缓存容量未满，则下面的set()是用于存入新项的；
  // 如果缓存中没有当前key，且缓存容量已满，则下面的set()是用于更新栈顶元素的；
  this.cache.set(key, value);
  // 和之前提到的一样，put时其实也是一种访问操作，所以需要调用一下get()函数来更新栈顶
  this.get(key);
};


提交记录
22 / 22 个通过测试用例
状态：通过
执行用时：868 ms, 在所有 JavaScript 提交中击败了5.21%的用户
内存消耗：88.4 MB, 在所有 JavaScript 提交中击败了91.93%的用户
时间：2021/09/11 21:51

可以看到这种方式的显得更加简洁。而且空间消耗降低了不少，但是其时间消耗的表现比较差，看来这种思路就是拿时间来换空间的体现了。我猜应该是Map内部的那些方法的实现还是花费了比较多的时间，所以也能理解。但是我还比较偏爱这种方法，因为这种方法的理解还是相对简洁了许多。

官方题解

更新：2021年7月29日18:43:21

因为我考虑到著作权归属问题，所以【官方题解】部分我不再粘贴具体的代码了，可到下方的链接中查看。

更新：2021年9月11日15:35:37

参考：LRU缓存机制 - LRU 缓存机制 - 力扣（LeetCode）

【更新结束】

有关参考

更新：2021年9月11日15:36:15
参考：《计算机操作系统（第四版）》P176~P177 汤小丹、梁红兵、哲凤屏、汤子瀛 编著——西安电子科技大学出版社
更新：2021年9月11日16:50:11
参考：Map - JavaScript | MDN
参考：Set 和 Map 数据结构 - ES6 教程 - 网道
参考：JavaScript splice() 方法