思路

具体的思路在LeetCode官方解答中有，里面还有动画和视频，推荐看不懂下面思路的可以去看一下。

LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1)O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：

对于 get 操作，首先判断key是否存在：
如果key不存在，则返回 -1；
如果key存在，则 key 对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
对于 put 操作，首先判断key 是否存在：

如果 key不存在，使用 key 和 value 创建一个新的节点，在双向链表的头部添加该节点，并将 key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项；

如果 key 存在，则与 get 操作类似，先通过哈希表定位，再将对应的节点的值更新为 value，并将该节点移到双向链表的头部。

上述各项操作中，访问哈希表的时间复杂度为 O(1)O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1)O(1)时间内完成。

注意：在双向链表的实现中，可以使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在

不使用内置的LinkedHashMap ，使用哈希表+双向链表

代码

class LRUCache {
    //定义双链表节点类
    class Node{
        public int key,val;
        public Node next,prev;
        public Node(int k ,int v){
            this.key = k;
            this.val = v;
        }
    }

    //用Node类型构建一个双向链表
    class DoubleList{
        //定义一个头尾伪节点，这样在添加和删除节点的时候就不需要检查相邻的节点是否存在了
        private Node head,tail;
        //链表的元素个数
        private int size;
        public DoubleList(){
            //初始化双链表的数据
            head = new Node(0,0);
            tail = new Node(0,0);
            head.next = tail;
            tail.prev = head;
            size = 0;
        }

    //在链表的尾部添加节点x，时间复杂度尾0（1）
    public void addLast(Node x){
        x.prev = tail.prev;
        x.next = tail;
        tail.prev.next = x;
        tail.prev = x;
        size++;
    }

    //删除链表节点x，且该x一定存在（调用前做了判断）
    public void remove (Node x){
        x.prev.next = x.next;
        x.next.prev = x.prev;
        size--;
    }

    //删除链表头的第一个元素（注意不是head，则是head后的第一个），并返回该节点，时间复杂度尾0(1);
    public Node removeFirst(){
       //首先判断链表是否为空
       if(head.next==tail) return null;
       //不为空，先记录该节点，然后调用删除函数将该节点删除，之后返回
       Node fist = head.next;
       remove(fist);
       return fist;
    }
    //返回链表的长度
    public int size() {
        return size;
    }
}
    //key -> Node(key,value)
    private HashMap<Integer,Node> map;
    //Node<k1,v1> <-> Node(k2,v2)...
    private DoubleList cache;
    //最大容量
    private int cap;
    public LRUCache(int capacity) {
        //初始化
        this.cap = capacity;
        map = new HashMap<>();
        cache = new DoubleList();
    }
    //将某个key提升为最近使用
    private void makeRecently (int key){
         //根据索引取出节点
        Node x = map.get(key);
        //删除key
        cache.remove(x);
        //重新插到链表尾
        cache.addLast(x);
    }

    //添加最近使用的元素
    private void addRecently(int key,int val){
       //新建一个节点
       Node x = new Node(key,val);
        //在链表尾添加
        cache.addLast(x);
        //最后别忘了在map中也要记录key的映射
        map.put(key,x);
    }

    //删除某一个key
    private void deleteKey(int key){
        Node x = map.get(key);
        //从链表中删除
        cache.remove(x);
        //从map中删除
        map.remove(key);
    }
    //删除最久没有使用的元素(第一个元素)
    private void deleteLastRecently(){
        //删除第一个，返回被删除的节点
        Node x = cache.removeFirst();
        //同时从map中删除
        //先取得key
        int key = x.key;
        //再删除
        map.remove(key);
    }

    public int get(int key) {
        //如果没有对应的索引，那就返回-1
        if(!map.containsKey(key)){
            return -1;
        }
        //有对应的索引，
        /* 1. 把它变成最近使用
           2. 返回这个的值
        */
        makeRecently(key);
        return map.get(key).val; //哈希表用get获得key获得节点，然后再取Node上的值

    }
    
    public void put(int key, int val) {
        //如果有，则修改值，同时变成最近使用
        if(map.containsKey(key)){
            //删除旧的数据
            deleteKey(key);
            //插入新的数据
            addRecently(key,val);
            return;
        }
        //如果没有，则要判断是否有容量
        //没有容量，则先删除最久未使用的，然后插入,有容量，直接插入；
        if(cache.size()==this.cap){
           deleteLastRecently();
        }
        //插入新的
        addRecently(key,val);

    }
   
}

/**
 * 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);
 */

说明

为什么不使用单链表而要使用双向链表？

在代码中就可以看出，我们需要进行删除操作（remove ），删除一个节点不仅要得到该节点本身的指针，也需要操作其前驱节点的指针，而只有双向链表才支持直接找前驱，这样才能保证时间复杂度为0(1)，而单链表则达不到这样的效果。

为什么哈希表存储了key，为什么链表中还要存key和val，直接存val不行吗？

因为在deleteLastRecently函数中，既需要删除节点，也需要得到key。也就是当存储容量满了之后，不仅要删除最后一个Node节点，还要把map·中映射到该节点的key删除，而这个key只能通过Node节点获得。如果Node结构中只存储了val，那么就无法知道key是什么了，也就无法通过key去删除map中的键了。

使用内置的LinkedHashMap

class LRUCache {
    int cap;
    LinkedHashMap<Integer,Integer> cache = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    
    public int get(int key) {
        //如果没有对应的索引，那就返回-1
        if(!cache.containsKey(key)){
            return -1;
        }
        //有对应的索引，
        /* 1. 把它变成最近使用
           2. 返回这个的值
        */
        makeRecently(key);
        return cache.get(key); //哈希表用get获得值

    }
    
    public void put(int key, int value) {
        //如果有，则修改值，同时变成最近使用
        if(cache.containsKey(key)){
            cache.put(key,value);
            makeRecently(key);
            return;
        }
        //如果没有，则要判断是否有容量
        //没有容量，则先删除最久未使用的，然后插入
        if(cache.size()>=this.cap){
            //链表头就是最久未使用的
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        //插入新的
        cache.put(key,value);

    }
    private void makeRecently (int key){
        int value = cache.get(key);
        //删除key，重新插到链表尾
        cache.remove(key);
        cache.put(key,value);
    }
}