[LeetCode解题] -- LRU缓存机制

146. LRU缓存机制

LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used : 最近最少使用。

重写双向链表 + HashMap   [要求 put get 方法时间复杂度为O(1) ]

[ 题目描述 ]

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

[ 解题思路 ]

哈希链表。

问题：怎么保证“get 和 put 方法必须都是 O(1) 的时间复杂度”？

get 查找快 -- hashmap

put 插入快，删除快，有顺序之分 -- 双向链表

问题：“为什么必须要用双向链表”？

因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)

 

因为显然 cache 必须有顺序之分，以区分最近使用的和久未使用的数据；而且我们要在 cache 中查找键是否已存在；如果容量满了要删除最后一个数据；每次访问还要把数据插入到队头。

那么，什么数据结构同时符合上述条件呢？哈希表查找快，但是数据无固定顺序；链表有顺序之分，插入删除快，但是查找慢。所以结合一下，形成一种新的数据结构：哈希链表。

 

[ 代码实现 ]  

第一步 双链表的节点类

为了简化，key 和 val 都认为是 int 类型

class Node { public int key, val; public Node next, prev; public Node(int k, int v) { this.key = k; this.val = v; } }

第二步 用Node 类型构建一个双链表。

        实现其【 头插 删除 删尾 获得size】 addFirst(Node x); remove(Node x); removeLast(); size();方法。将要实现的这几个需要的 API（这些操作的时间复杂度均为 O(1)。

class DoubleList { // 在链表头部添加节点 x，时间 O(1) public void addFirst(Node x); // 删除链表中的 x 节点（x 一定存在） // 由于是双链表且给的是目标 Node 节点，时间 O(1) public void remove(Node x); // 删除链表中最后一个节点，并返回该节点，时间 O(1) public Node removeLast(); // 返回链表长度，时间 O(1) public int size(); }

到这里就能回答刚才“为什么必须要用双向链表”的问题了，因为我们需要删除操作。删除一个节点不光要得到该节点本身的指针，也需要操作其前驱节点的指针，而双向链表才能支持直接查找前驱，保证操作的时间复杂度 O(1)。

第三步  双向链表和哈希表实现 get put方法

有了双向链表的实现，我们只需要在 LRU 算法中把它和哈希表结合起来即可。我们先把逻辑理清楚：

// key 映射到 Node(key, val) HashMap<Integer, Node> map; // Node(k1, v1) <-> Node(k2, v2)... DoubleList cache; int get(int key) { if (key 不存在) { return -1; } else { 将数据 (key, val) 提到开头； return val; } } void put(int key, int val) { Node x = new Node(key, val); if (key 已存在) { 把旧的数据删除； 将新节点 x 插入到开头； } else { if (cache 已满) { 删除链表的最后一个数据腾位置； 删除 map 中映射到该数据的键； } 将新节点 x 插入到开头； map 中新建 key 对新节点 x 的映射； } }

第四步 伪代码逻辑实现

class LRUCache { // key -> Node(key, val) private HashMap<Integer, Node> map; // Node(k1, v1) <-> Node(k2, v2)... private DoubleList cache; // 最大容量 private int cap; public LRUCache(int capacity) { this.cap = capacity; map = new HashMap<>(); cache = new DoubleList(); } public int get(int key) { if (!map.containsKey(key)) return -1; int val = map.get(key).val; // 利用 put 方法把该数据提前 put(key, val); return val; } public void put(int key, int val) { // 先把新节点 x 做出来 Node x = new Node(key, val); if (map.containsKey(key)) { // 删除旧的节点，新的插到头部 cache.remove(map.get(key)); cache.addFirst(x); // 更新 map 中对应的数据 map.put(key, x); } else { if (cap == cache.size()) { // 删除链表最后一个数据 Node last = cache.removeLast(); map.remove(last.key); } // 直接添加到头部 cache.addFirst(x); map.put(key, x); } } }

这里就能回答之前的问答题“为什么要在链表中同时存储 key 和 val，而不是只存储 val”，注意这段代码：

if (cap == cache.size()) {     // 删除链表最后一个数据     Node last = cache.removeLast();     map.remove(last.key); }

当缓存容量已满，我们不仅仅要删除最后一个 Node 节点，还要把 map 中映射到该节点的 key 同时删除，而这个 key 只能由 Node 得到。如果 Node 结构中只存储 val，那么我们就无法得知 key 是什么，就无法删除 map 中的键，造成错误。

至此，你应该已经掌握 LRU 算法的思想和实现了，很容易犯错的一点是：处理链表节点的同时不要忘了更新哈希表中对节点的映射。

第五步 完整代码

1. Node类。  int k,v ; Node next,prev; 2. DoubleList类-双向链表类。   int size  ; Node head,tail; 3. LRUCache 构造函数。  int cap;  DoubleList cache;    HashMap<Integer, Node> map; 4. get put 方法。

class LRUCache { // Node 类 class Node { public int key, val; public Node next, prev; public Node(int k, int v) { this.key = k; this.val = v; } } // DoubleList 类 class DoubleList { // 对Node的操作，无 k v 操作 private Node head, tail; private int size; // 双向链表 的实际size大小 public void addFirst(Node node) { if (head == null) { head = tail = node; } else { Node n = head; n.prev = node; node.next = n; head = node; } size++; } public void remove(Node node) { // node tail head if (head == node && tail == node) { head = null; tail = null; } else if (tail == node) { // 最后 前下=null ; node.pre.next node.prev.next = null; tail = node.prev; } else if (head == node) { // 开头 下前=null ; node.next.pre node.next.prev = null; head = node.next; } else { node.prev.next = node.next; node.next.prev = node.prev; } size--; } public Node removeLast() { Node node = tail; remove(tail); // 调用了remove() return node; } public int size() { return size; } } // LRUCache 构造函数 private int cap; // 双向链表 容量 capacity private DoubleList cache; private HashMap<Integer, Node> map; // map 的 k , v public LRUCache(int capacity) { this.cap = capacity; cache = new DoubleList(); map = new HashMap<>(); } // get put 方法 public int get(int key) { if(!map.containsKey(key)) return -1; int val = map.get(key).val; put(key, val); // 此处调用了 put() return val; } public void put(int key, int value) { Node x = new Node(key, value); if (map.containsKey(key)){ cache.remove(map.get(key)); cache.addFirst(x); map.put(key,x); } else { if (cap == cache.size()) { Node last = cache.removeLast(); map.remove(last.key); } cache.addFirst(x); map.put(key,x); } } }

对put()的理解

put 方法主要有3个

1.remove 删除缓存cache或者删除缓存cache、map中的数据

2.缓存头插 cache.addFirst(x);

3.更新map map.put(key,x);

那么索性如下写法

public void put(int key, int value) { Node x = new Node(key, value); if (map.containsKey(key)){ cache.remove(map.get(key)); } else { if (cap == cache.size()) { Node last = cache.removeLast(); map.remove(last.key); } } cache.addFirst(x); map.put(key,x); }

 

写在最后，好久没白嫖别人思想了，还好自己得空实现了一版代码，此处奉上链接，以示敬意。

参考

https://leetcode-cn.com/problems/lru-cache/solution/lru-ce-lue-xiang-jie-he-shi-xian-by-labuladong/