题目来源

https://leetcode.cn/problems/lru-cache/

描述

思路：双向链表+哈希表

双向链表的节点存放key-value，根据最近访问的次序，越靠近头节点，说明距离上次访问的时间越短。哈希表用来存放key-节点，用于快速定位key对应的节点在双向链表中的位置，或者判断key是否在LRU缓存中。

对于初始化操作LRUCache(int capacity)，可以初始化双向链表，初始化哈希表、初始化capacity。

对于get操作，可以先使用哈希表判断缓存中是否存在key，若果不存在，直接返回-1，如果存在，则将key对应的双向链表中的节点挪到链表的表头，并且返回节点中的value。

对于put操作，可以先使用哈希表判断缓存中是否存在key，如果存在，则获取其对应节点，更新其value值，并将该节点挪到表头位置；如果不存在，则新建节点保存key-value，并将其插到表头位置，此外要在哈希表中添加key-节点键值对，此时缓存大小增加，因此要判断大小是否超过了capacity，如果超过了，需要将表尾的节点删除，同时删除表为节点在哈希表中的信息。

代码

import java.util.HashMap;
public class Main {
    public static void main(String[] args) {
        LRUCache lruCache = new LRUCache(2);
        System.out.println(lruCache.put(1, 0));
        System.out.println(lruCache.put(2, 2));
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.put(3, 3));
        System.out.println(lruCache.get(2));
        System.out.println(lruCache.put(4, 4));
        System.out.println(lruCache.get(1));
        System.out.println(lruCache.get(3));
        System.out.println(lruCache.get(4));
    }
}
class DLinkedNode{
    DLinkedNode prev;
    DLinkedNode next;
    int key;
    int value;
}
class LRUCache{
    int capacity;
    int size;
    DLinkedNode dLinkedList = null;
    DLinkedNode head = null;
    DLinkedNode tail = null;
    HashMap<Integer, DLinkedNode> hashMap = null;
    //构造函数
    public LRUCache(int capacity){
        this.capacity = capacity;
        size = 0;
        DLinkedNode headDummy = new DLinkedNode();
        DLinkedNode tailDummy = new DLinkedNode();
        headDummy.next = tailDummy;
        headDummy.prev = null;
        tailDummy.next = null;
        tailDummy.prev = headDummy;
        head = headDummy;
        tail = tailDummy;
        hashMap = new HashMap<>();
    }
    /**
     * 获取关键字的值，如果没有，返回-1
     * 先通过hashMap获取到key所在链表的位置，如果没有，返回-1结束
     * 如果存在，将双向链表中对应的节点挪到头节点的位置，返回对应的value
     * @param key 获取key关键字的值
     * @return 返回key对应的值，如果没有，返回-1
     */
    int get(int key){
        if(!hashMap.containsKey(key)) return -1;
        DLinkedNode linkedNodeOfKey = hashMap.get(key);         // 获取key对应节点
        linkedNodeOfKey.prev.next = linkedNodeOfKey.next;
        linkedNodeOfKey.next.prev = linkedNodeOfKey.prev;
        head.next.prev = linkedNodeOfKey;
        linkedNodeOfKey.prev = head;
        linkedNodeOfKey.next = head.next;
        head.next = linkedNodeOfKey;
        return linkedNodeOfKey.value;
    }
    /**
     * 将key-value添加到缓存中
     * 如果key已经存在，更新其value值，并将对应节点挪到头节点的位置
     * 如果key不存在，则新建节点保存key-value，并将该节点插入链表头部，并且将key和节点对添加到hashMap中，更新size，如果size超过capacity，删除链表末尾元素
     * @param key 待插入的key
     * @param value 待插入的value
     */
    Object put(int key, int value){
        DLinkedNode linkedNodeOfKey = null;
        if(hashMap.containsKey(key)){
            linkedNodeOfKey = hashMap.get(key);
            linkedNodeOfKey.value = value;
            linkedNodeOfKey.prev.next = linkedNodeOfKey.next;
            linkedNodeOfKey.next.prev = linkedNodeOfKey.prev;
        }else{
            linkedNodeOfKey = new DLinkedNode();
            linkedNodeOfKey.key = key;
            linkedNodeOfKey.value = value;
            hashMap.put(key, linkedNodeOfKey);
            size++;
        }
        head.next.prev = linkedNodeOfKey;
        linkedNodeOfKey.prev = head;
        linkedNodeOfKey.next = head.next;
        head.next = linkedNodeOfKey;
        if(size > capacity){
            int keyForDel = tail.prev.key;
            hashMap.remove(keyForDel);
            tail.prev.prev.next = tail;
            tail.prev = tail.prev.prev;
            size--;
        }
        return null;
    }
}