LRU缓存机制

代码 

哈希表 + 双链表

class LRUCache {
    //双向链表节点
    private static class DListNode{
        int key;
        int value;
        DListNode prev;
        DListNode next;
        DListNode(){

        }
        DListNode(int key, int value){
            this.key = key;
            this.value = value;
        }
    }
    //缓存的最大容量
    private int capacity;
    //缓存的当前大小
    private int size;
    private DListNode head;
    private DListNode tail;
    //真正的缓存结构
    private Map<Integer, DListNode> cache = new HashMap<>();
    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        //构造函数中初始化一个有尾结点和头节点的双向链表
        head = new DListNode();
        tail = new DListNode();
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
         DListNode dListNode = cache.get(key);
        if(dListNode == null){
            return -1;
        }
        //找到链表节点则将其加入到链表头，并返回链表的节点
        removeNode(dListNode);
        addNodeToHead(dListNode);
        return dListNode.value;
    }
    
    public void put(int key, int value) {
     
        DListNode dnode = cache.get(key);
        if(dnode == null){
            DListNode newNode = new DListNode(key, value);
            cache.put(key, newNode);
            addNodeToHead(newNode);
            //插入成功，大小加一
            size++;
            //超出尺寸，则删除双链表中的最后一个元素结点，并删除该链表元素节点的hashMap中的元素
            if(size > capacity){
                DListNode finalNode = tail.prev;
                removeNode(finalNode);
                //通过链表元素的key找到hashMap中的key并删除
                cache.remove(finalNode.key);
                size--;
            }
        }else{//如果key存在则需要对hashMap的值进行更新,并将双链表节点放到链表头
            // cache.put(key, newNode);
            dnode.value = value;
            removeNode(dnode);
            addNodeToHead(dnode);
        }
    }

    public void removeNode(DListNode dListNode) {
        dListNode.prev.next = dListNode.next;
        dListNode.next.prev = dListNode.prev;
    }

    public void addNodeToHead(DListNode dListNode){
        dListNode.next = head.next;
        head.next.prev = dListNode;
        head.next = dListNode;
        dListNode.prev = head;
    }
}