题设
    运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
    实现 LRUCache 类：

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

    进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

    解法1
    分析
    LRU 算法一般用在缓存淘汰算法中，指的最少最近使用的那部分缓存需要被释放掉以腾出空间存放新到的数据，算法的基本做法就是只要数据被查看或者修改或者被新增，就将它视为最近使用的，当要插入新的数据且容量空间不够时，就将最早前使用的数据移除掉。

    可见这中间涉及到了数据的删除，插入 ，查找和修改 ，对于缓存而言
    插入操作： 只涉及了数据的插入，若空间不够则同时涉及数据的删除 和 插入
    查询操作： 涉及数据的查询 和 删除 同时还要有插入
    修改操作： 涉及数据的查询，修改，删除 和 插入

    上面的分析可得数据的增删改查一个没落下，要想实现O(1)时间复杂度，能选的数据结构中最接近的就是双向链表。
    双向链表在修改，插入 和 删除操作上的时间复杂度都是 O(1) ，但是查询上由于需要遍历，变成了O(n)。 很容易的可以想到，将双向链表配合着散列一起使用，就能将查询的时间复杂度提升为 O(1) ，同时在修改和删除上也能够快速找出目标元素。

    实现

    1. class LRUCache {
    3.     private int cap;
    5.     private int size = 0;
    7.     Map<Integer,Node> map = new HashMap<>();
    9.     // 使用哨兵要求不与输入数据混淆
    10.     Node head = new Node(-1,-1);
    11.     Node tail = new Node(-1,-1);
    13.     class Node{
    14.         private Node prev;
    15.         private Node next;
    16.         int key;
    17.         int val;
    19.         public Node(int key ,int val){
    20.             this.key = key;
    21.             this.val = val;
    22.         }
    23.     }
    26.     public LRUCache(int capacity) {
    27.         this.cap = capacity;
    28.         head.next = tail;
    29.         tail.prev = head;
    30.     }
    32.     public int get(int key) {
    33.         Node node = map.get(key);
    34.         if(null == node) return -1;
    35.         remove(node);
    36.         addToTail(node);
    37.         return node.val;
    38.     }
    40.     public void put(int key, int value) {
    41.         if(cap <= 0) return;
    42.         Node node = map.get(key);
    43.         if(null == node){
    44.             capCheck();
    45.             Node nNode = new Node(key,value);
    46.             addToTail(nNode);
    47.             map.put(key,nNode);
    48.             size++;
    49.         }else{
    50.             remove(node);
    51.             addToTail(node);
    52.             node.val = value;
    53.         }
    54.     }
    57.     private void remove(Node node){
    58.         Node prev = node.prev;
    59.         prev.next = node.next;
    60.         node.next.prev = prev;
    61.     }
    63.     private void addToTail(Node node){
    64.         node.prev = tail.prev;
    65.         tail.prev.next = node;
    66.         tail.prev = node;
    67.         node.next = tail;
    68.     }
    71.     private void capCheck(){
    72.         if(cap == size){
    73.             // put时有判断cap 要大于0, 这里一定能移除某个元素
    74.             map.remove(head.next.key);
    75.             remove(head.next);
    76.             size--;
    77.         }
    78.     }
    79. }
    81. /**
    82.  * Your LRUCache object will be instantiated and called as such:
    83.  * LRUCache obj = new LRUCache(capacity);
    84.  * int param_1 = obj.get(key);
    85.  * obj.put(key,value);
    86.  */