题目：
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

解题思路：
阅读了灵神的题解之后，总结一下自己的理解。
想象有一堆书很妙。
对于get：想阅读一本书，那么我就需要从这堆书里面把书取出来，读完之后再放到最上面。这里就涉及到三个步骤：
1、先从这一堆书中找到这本书
2、从这堆书里拿出这本书
3、再将这本书放回到这堆书最上面

对于put：想添加一本书，首先需要判断有没有这本书，如果有，就把他拿出来，更新value，再放回这堆书最上面。如果没有，就先判断这堆书容量是否以达到最大容量，如果达到了，就丢弃最下面那本书，因为最下面那本书代表最久每阅读的书了，然后再将这本新书放到书堆上面。这里也涉及三个步骤：
1、首先获取这本书，如果有就更新value。注意在获取这本书的过程也要包含找书、拿书、再放书，所以可以封装成一个方法。
2、如果没有这本书，则判断容量是否达到阈值。如果达到，则删除最下面一本书。
3、将这本新书放到书堆最上面。

那么现在的问题就是，该用什么数据结构来表示这堆书呢？
题目中的要求是get和put的时间复杂度都要是O(1)，可以想到用链表来实现，因为如果我们知道这本书在链表中的位置，我们可以在O(1)的时间复杂度删除它再将它添加到链表头部。
那为什么要使用双向链表呢？
因为我们有一个删除最下面那本书的过程，也就是删除链表尾节点，如果我们用单向链表的话，我们需要先遍历链表找到尾节点，就会导致时间复杂度不满足要求。
而添加一个哨兵节点是为了不用特殊处理链表为空的情况

那为什么还需要有一个哈希表呢
注意我在上面说的“如果我们知道这本书在链表中的位置，我们可以在O(1)的时间复杂度删除它再将它添加到链表头部”。
我们一开始肯定是不知道这本书在链表中的具体位置的，我们就需要先遍历链表找到这本书，这样的话时间复杂度也是不符合要求的。
所以，我们需要用key能够在O(1)的时间复杂度内，找到这本书的位置，那么就可以用哈希表来存储key到链表节点的映射关系。

代码：

class LRUCache {private static class Node{int key;int value;Node pre;Node next;public Node(int key, int value){this.key = key;this.value = value;}  }private final int capacity;private final Node dummy = new Node(0, 0);private final Map<Integer, Node> keyToNode = new HashMap<>();public LRUCache(int capacity) {this.capacity = capacity;dummy.next = dummy;dummy.pre = dummy;}public int get(int key) {Node node = getNode(key);return node == null ? -1 : node.value;}public void put(int key, int value) {Node node = getNode(key);if(node != null){node.value = value;return;}// 如果关键容量达到capacity，则删除最久未使用的if(keyToNode.size() == capacity){Node lastNode = dummy.pre;keyToNode.remove(lastNode.key);remove(lastNode);}node = new Node(key, value);keyToNode.put(key, node);putFirst(node);}private Node getNode(int key){if(!keyToNode.containsKey(key)){return null;}Node node = keyToNode.get(key);remove(node);putFirst(node);return node;}private void remove(Node node){node.pre.next = node.next;node.next.pre = node.pre;}private void putFirst(Node node){node.next =  dummy.next;node.pre = dummy;dummy.next.pre = node;dummy.next = node;}
}/*** Your LRUCache object will be instantiated and called as such:* LRUCache obj = new LRUCache(capacity);* int param_1 = obj.get(key);* obj.put(key,value);*/