设计一个存储key-value的值，需要能get到对应key的值，在存储的时候如果关键字存在则变更，如果不存在则存储，如果容量满了则删除最久没使用的值，会用到一个哈希表和一个双向链表，用哈希表来存储键值对，用双向链表来存储使用顺序。越靠近头部越是最近使用的，使用也就一位这使用了get（）
get时如果哈希表不存在key则返回-1，如果存在则得知在双向链表中的下标，将它移动到头部并返回。
put时如果key不存在则创造一个新的节点。并在双向链表的头部添加该节点（使用意味着添加和返回都算），并将其添加到哈希表中。如果key存在，则先通过哈希表定位找到该节点，然后再改变它的位置到双向链表的头部。
哈希表可以用hashmap，然后双向链表需要自己实现。
双向链表的操作共三步，在双向链表的头部添加节点，在双向链表的尾部删除节点，将指定节点移向头部的操作就是先删除然后再头部添加。
在实现的时候设置一个伪头部和一个伪尾部，这样就不用检查相邻的节点是否存在而可以直接添加或删除。

class LRUCache {
     class Node{//双向链表的节点类
        int key;//此节点的键
        int value;//此节点的值
        Node prev;//前一个节点
        Node next;//后一个节点
        public Node(){}
        public Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    }
    //缓存类的初始化
    private Map<Integer, Node> map = new HashMap<Integer, Node>();//实现这个缓存机制的哈希表，key对应双向链表节点
    private Node head, tail;//双向链表的头结点和尾结点
    private int size;//此时的大小
    private int capacity;//要求的容量
    public LRUCache(int capacity){//缓存类的构造函数
        this.size=0;
        this.capacity=capacity;
        head=new Node();//初始化头结点尾结点
        tail=new Node();
        head.next=tail;
        tail.prev=head;
    }
    // 双向链表的方法，共四个
     private void addToHead(Node node) {
        node.prev = head;
        node.next = head.next;
        head.next.prev = node;
        head.next = node;
    }

    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
     private Node removeTail() {
        Node res = tail.prev;
        removeNode(res);
        return res;
    }
    private void moveToHead(Node node) {
        removeNode(node);
        addToHead(node);
    }
    // LRU缓存核心方法get和put
    public int get(int key) {
        if(map.containsKey(key)){
            Node n=map.get(key);
            moveToHead(n);
            return n.value;
        }else{
            return -1;
        }
    }
    
    public void put(int key, int value) {
        if(map.containsKey(key)){
            Node n=map.get(key);
            n.value=value;
            moveToHead(n);
        }else{
            Node n=new Node(key,value);
            map.put(key,n);
            addToHead(n);
            size++;
            if(size>capacity){
                Node tail=removeTail();
                map.remove(tail.key);
                --size;
            }
        }
    }
}