这是LeetCode上的「.LRU缓存机制」，难度为「中等」。
运用你所掌握的数据结构，设计和实现一个LRU(最近最少使用)缓存机制。实现LRUCache类：
LRUCache(intcapacity)以正整数作为容量capacity初始化LRU缓存intget(intkey)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。voidput(intkey,intvalue)如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。进阶：你是否可以在
时间复杂度内完成这两种操作？
示例：
输入["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]解释LRUCachelRUCache=newLRUCache(2);lRUCache.put(1,1);//缓存是{1=1}lRUCache.put(2,2);//缓存是{1=1,2=2}lRUCache.get(1);//返回1lRUCache.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);//返回3lRUCache.get(4);//返回4
提示：
1=capacity==key==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。代码：
classLRUCache{classNode{intk,v;Nodel,r;Node(int_k,int_v){k=_k;v=_v;}}intn;Nodehead,tail;MapInteger,Nodemap;publicLRUCache(intcapacity){n=capacity;map=newHashMap();head=newNode(-1,-1);tail=newNode(-1,-1);head.r=tail;tail.l=head;}publicintget(intkey){if(map.containsKey(key)){Nodenode=map.get(key);refresh(node);returnnode.v;}return-1;}publicvoidput(intkey,intvalue){Nodenode=null;if(map.containsKey(key)){node=map.get(key);node.v=value;}else{if(map.size()==n){Nodedel=tail.l;map.remove(del.k);delete(del);}node=newNode(key,value);map.put(key,node);}refresh(node);}//refresh操作分两步：//1.先将当前节点从双向链表中删除（如果该节点本身存在于双向链表中的话）//2.将当前节点添加到双向链表头部voidrefresh(Nodenode){delete(node);node.r=head.r;node.l=head;head.r.l=node;head.r=node;}//delete操作：将当前节点从双向链表中移除//由于我们预先建立head和tail两位哨兵，因此如果node.l不为空，则代表了node本身存在于双向链表（不是新节点）voiddelete(Nodenode){if(node.l!=null){Nodeleft=node.l;left.r=node.r;node.r.l=left;}}}时间复杂度：各操作均为
空间复杂度：
最后
这是我们「刷穿LeetCode」系列文章的第No.篇，系列开始于/01/01，截止于起始日LeetCode上共有道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：