题目：
请你设计并实现一个满足 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);
*/