1、题目

:::info 运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥已经存在，则变更其数据值；如果密钥不存在，则插入该组「密钥/数据值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例： :::

  1. LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );
  3. cache.put(1, 1);
  4. cache.put(2, 2);
  5. cache.get(1);       // 返回  1
  6. cache.put(3, 3);    // 该操作会使得密钥 2 作废
  7. cache.get(2);       // 返回 -1 (未找到)
  8. cache.put(4, 4);    // 该操作会使得密钥 1 作废
  9. cache.get(1);       // 返回 -1 (未找到)
  10. cache.get(3);       // 返回  3
  11. cache.get(4);       // 返回  4

2、什么是LRU（Least Recently Used）

  • LRU是最近最少使用算法

  • 它是根据时间维度来选择要淘汰的元素，即删除最长时间没被访问的元素

    3、解题思路

  • LRU缓存策略举例：

    • 假设缓存大小为4，依次打开了github、力扣、微信、QQ，缓存链表为 QQ -> 微信 ->力扣 -> github;
    • 若此时切换到了微信，则缓存链表更新为 微信 -> QQ ->力扣 -> github ;
    • 若此时打开了 语雀，因为缓存已经满 4 个，所以要进行缓存淘汰机制，删除链表的最后一位 github, 则缓存链表更新为 语雀 -> 微信 -> QQ -> 力扣
  • 本题用的是 map 迭代器，map 实现了 iterator，next 模拟链表的下一个指针，为了方便操作，这里将 map 第一个元素作为链表的最后一个元素： ```javascript let cache = new map() cache.set(‘a’, 1) cache.set(‘b’, 2) cache.set(‘c’, 3)

cache.keys(); // MapIterator [‘a’, ‘b’, ‘c’] cache.keys().next().value; // a

  2. - 复杂度
  3.    - 时间复杂度：对于 put 和 get 都是 O(1)
  4.    - 空间复杂度： O（capacity）
  5. <a name="An07N"></a>
  6. ### 4、代码实现
  7. ```javascript
  8. var LRUCache = function(capacity) {
  9.     // 利用map的迭代器进行插入顺序记录
  10.     this.map = new Map()
  11.     this.capacity = capacity
  12. };
  14. LRUCache.prototype.get = function(key) {
  15.     // 如果关键字存在于缓存中，先删除然后再次存入
  16.     if (this.map.has(key)) {
  17.         let value = this.map.get(key)
  18.         this.map.delete(key)
  19.         this.map.set(key, value)
  20.         return value
  21.     }
  22.     return -1
  23. };
  25. LRUCache.prototype.put = function(key, value) {
  26.     if (this.map.has(key)) {
  27.         this.map.delete(key)
  28.     }
  29.     this.map.set(key, value)
  30.     if (this.map.size > this.capacity) {
  31.         this.map.delete(this.map.keys().next().value)
  32.     }
  33. };

5、进阶实现

在上述的解题方法中，直接利用迭代器使得问题变得简单，但也可以难到 System Design 的内容。
以下我们可以参考该篇文章，很优雅的代码思路：
https://juejin.cn/post/6844904161545289742

5.1 思路

维护一个双向链表 :

  1. class DoubleNode {
  2.   constructor(key, val) {
  3.     this.key = key
  4.     this.val = val
  6.     this.prev = null
  7.     this.next = null
  8.   }
  9. }

和一个「哈希表」map，map 的目的是通过 key 去查找对应的 node：

  1. // key -> DoubleNode
  2. this.map = new Map()

并且维护 LRUCache 实例中的 head 头结点和 tail 尾结点。

get 操作

从 map 中获取节点，并且把节点的头部更新为本次获取的节点。

put 操作

分为几种情况：

  1. 原本就有这个 key 值，那么更新对应 node 的值，并且删掉旧节点，移动新节点头部。

  2. 原本没有这个 key 值：

    1. 容量没超过上限：那么就直接放到头部节点即可。
    2. 容量超过了上限：那么就删除尾部节点，把新的节点放到放到头部节点即可。
      remove 操作

  3. 删除头部节点，需要重新维护 head 的值，以及 next 节点的 prev 值。

  4. 删除尾部节点，需要重新维护 tail 的值，以及 prev 节点的 next 值。

  5. 删除中间节点，需要维护节点以及它的相邻节点的 prev、next 值。 ```javascript class DoubleNode { constructor(key, val) { this.key = key this.val = val

    this.prev = null this.next = null } }

class LRUCache { constructor(max) { this.max = max this.map = new Map()

  1. this.head = null
  2. this.tail = null

}

get(key) { const node = this.map.get(key) if (!node) { return -1 } else { const res = node.val this.remove(node) this.appendHead(node) return res } }

put(key, value) { let node = this.map.get(key) // 有这个缓存 if (node) { node.val = value // 新加入的 放在最前面 this.remove(node) this.appendHead(node) } else { // 没有这个缓存 node = new DoubleNode(key, value) // 如果超出容量了 删除最后一个 再放到头部 if (this.map.size >= this.max) { this.map.delete(this.tail.key) this.remove(this.tail) this.appendHead(node) this.map.set(key, node) } else { // 未超出容量 就直接放到头部 this.appendHead(node) this.map.set(key, node) } } }

/**

  • 把头部指针的改变成新的node

  • @param {DoubleNode} node */ appendHead(node) { if (this.head === null) { this.head = this.tail = node } else { node.next = this.head this.head.prev = node this.head = node } }

    /**

  • 删除某个节点
  • @param {DoubleNode} node */ remove(node) { if (this.head === this.tail) { this.head = this.tail = null } else { // 删除头部 if (this.head === node) { this.head = this.head.next node.next = null } else if (this.tail === node) { this.tail = this.tail.prev this.tail.next = null node.prev = null } else { node.prev.next = node.next node.next.prev = node.prev node.prev = node.next = null } } } } ```