关于java:设计数据结构实现一个-LRUCache

题目形容

这是 LeetCode 上的 「146. LRU 缓存机制」，难度为 「中等」。

使用你所把握的数据结构，设计和实现一个  LRU (最近起码应用) 缓存机制。实现 LRUCache 类：

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

进阶：你是否能够在  工夫复杂度内实现这两种操作？

示例：

 输出
["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 <= 3000
• 0 <= value <=
• 最多调用 3 * 次 get 和 put

根本剖析

LRU 是一种非常常见的页面置换算法。

将 LRU 翻译成大白话就是：当不得不淘汰某些数据时（通常是容量已满），抉择最久未被应用的数据进行淘汰。

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

能够通过 🌰 来了解，假如咱们有容量为 的 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 成为最新应用数据

键值对存储方面，咱们能够应用「哈希表」来确保插入和查问的复杂度为。

另外咱们还须要额定保护一个「应用程序」序列。

咱们冀望当「新数据被插入」或「产生键值对查问」时，可能将以后键值对放到序列头部，这样当触发 LRU 淘汰时，只须要从序列尾部进行数据删除即可。

冀望在 复杂度内调整某个节点在序列中的地位，很天然想到双向链表。

双向链表

具体的，咱们应用哈希表来存储「键值对」，键值对的键作为哈希表的 Key，而哈希表的 Value 则应用咱们本人封装的 Node 类，Node 同时作为双向链表的节点。

• 插入：查看以后键值对是否曾经存在于哈希表：
• 没达到容量：插入哈希表，并将以后键值对所对应的 Node 节点调整到链表头部（refresh 操作）
• 已达到容量：先从链表尾部找到待删除元素进行删除（delete 操作），而后再插入哈希表，并将以后键值对所对应的 Node 节点调整到链表头部（refresh 操作）
• 如果存在，则更新键值对，并将以后键值对所对应的 Node 节点调整到链表头部（refresh 操作）
• 如果不存在，则查看哈希表容量是否曾经达到容量：
• 查问：如果没在哈希表中找到该 Key，间接返回；如果存在该 Key，则将对应的值返回，并将以后键值对所对应的 Node 节点调整到链表头部（refresh 操作）

一些细节：

• 为了缩小双向链表左右节点的「判空」操作，咱们事后建设两个「哨兵」节点 head 和 tail。

代码：

class LRUCache {
    class Node {
        int k, v;
        Node l, r;
        Node(int _k, int _v) {
            k = _k;
            v = _v;
        }
    }
    int n;
    Node head, tail;
    Map<Integer, Node> map;
    public LRUCache(int capacity) {
        n = capacity;
        map = new HashMap<>();
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        head.r = tail;
        tail.l = head;
    }
    
    public int get(int key) {if (map.containsKey(key)) {Node node = map.get(key);
            refresh(node);
            return node.v;
        } 
        return -1;
    }
    
    public void put(int key, int value) {
        Node node = null;
        if (map.containsKey(key)) {node = map.get(key);
            node.v = value;
        } else {if (map.size() == n) {
                Node del = tail.l;
                map.remove(del.k);
                delete(del);
            }
            node = new Node(key, value);
            map.put(key, node);
        }
        refresh(node);
    }
 
    // refresh 操作分两步：// 1. 先将以后节点从双向链表中删除（如果该节点自身存在于双向链表中的话）// 2. 将以后节点增加到双向链表头部
    void refresh(Node node) {delete(node);
        node.r = head.r;
        node.l = head;
        head.r.l = node;
        head.r = node;
    }
 
    // delete 操作：将以后节点从双向链表中移除
    // 因为咱们事后建设 head 和 tail 两位哨兵，因而如果 node.l 不为空，则代表了 node 自身存在于双向链表（不是新节点）void delete(Node node) {if (node.l != null) {
            Node left = node.l;
            left.r = node.r;
            node.r.l = left;
        }
    }
}

• 工夫复杂度：各操作均为
• 空间复杂度：

最初

这是咱们「刷穿 LeetCode」系列文章的第 No.146 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先将所有不带锁的题目刷完。

在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。

为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。

在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。