问题描述：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

解法一：LinkedHashMap实现
public class LRUCache {

    private Integer capacity;

    LinkedHashMap<Integer,Integer> cache  = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        makeKeyRecentUse(key);
        return cache.get(key);
    }

    public void put(int key, int value) {
    //如果缓存已存在，因为key的不可阿重复性，直接调用hashmap的put方法覆盖之前的key-value,覆盖之后呢就返回
        if(cache.containsKey(key)){
            cache.put(key,value);
            makeKeyRecentUse(key);
            return;
        }
    //如果容量已大于设置的初始容量，因为链表头的元素为最久未使用，所以先删除表头的元素，在讲新的key-value加载表尾
        if(cache.size() >= this.capacity){
            Iterator<Integer> iterator = cache.keySet().iterator();
            cache.remove(iterator.next());
        }
        cache.put(key,value);

    }

   //根据key值将该key-value移到表尾，表示最近使用
    private void makeKeyRecentUse(int key){
        Integer value = cache.get(key);
        cache.remove(key);
        cache.put(key,value);
    }

}

第二种解法：自定义双链表和hashmap解决
public class LRUCache {

    private Integer capacity;
    //自定义缓存来存储每一个节点
    SelfList cache = new SelfList();

    //map里面的key就是key，但value是每一个节点
    HashMap<Integer,Node> map = new HashMap<>();
    public LRUCache(Integer capacity) {
        this.capacity = capacity;
    }

    public int get(int key){
    //如果map已经包含该key-node，就将双链表里的该节点移动到链表尾部，表示最近使用，不包含就返回-1
        if(!map.containsKey(key)){
            return -1;
        }
        //将双链表中的该节点移到链表尾部
        makeKeyRecentUse(key);
        Node node = map.get(key);
        return node.value;
    }

    public void put(int key,int value){

       //如果该map已经含有该key,那就覆盖
       //先从map中定位到旧节点，然后删除map的该key-node和双链表中旧node，再将新key-node和心node分别加到map和双链表中
       //记得return 不然会添加两次
       if(map.containsKey(key)){
            Node node = map.get(key);
            cache.remove(node);
            map.remove(key);
            Node newNode = new Node(key, value);
            cache.addLast(newNode);
            map.put(key,newNode);
            return;
        }

       //如果缓存的个数已经大于预设的容量，那么就删除双链表的表头节点（不是head节点嗷），并且删除map中的旧key-node
        //并且将新的额key-node和心node分别加到map和双链表中，记得返回
        if(cache.size() >= capacity){
            Node node = cache.removeFirst();
            map.remove(node.key);
            Node newNod1 = new Node(key,value);
            map.put(key,newNod1);
            cache.addLast(newNod1);
            return;
        }

        //正常添加
        Node newNode2 = new Node(key, value);
        map.put(key,newNode2);
        cache.addLast(newNode2);
    }

   //将已有并且不需要覆盖的节点移动到双链表尾部，这里map不用变，不涉及到数值的变化
    private void makeKeyRecentUse(int key){
        Node node = map.get(key);
        cache.remove(node);
        cache.addLast(node);
    }


}

class Node{
     int key;
     int value;

    Node prev ;
    Node next ;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}

class SelfList{
    Node head,tail;
    int size;

   //双链表构建 初始化
    public SelfList() {
        head  = new Node(0,0);
        tail = new Node(0,0);
        head.next = tail;
        tail.prev = head;
        size = 0;
    }


    public int size(){
        return size;
    }

   //在链表尾部添加元素
    public void addLast(Node node){
        tail.prev.next = node;
        node.next = tail;
        node.prev = tail.prev;
        tail.prev = node;
        size++;
    }
   //移除头部第一个节点
    public Node removeFirst(){
        if(head.next == null){
            return null;
        }
        Node first = head.next;
        first.next.prev = head;
        head.next = first.next;
        size--;

        return first;
    }
    //移除某一个节点
    public void remove(Node node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
        size--;
    }


}