LRU缓存

• 数据结构知识
• 算法思路

链接：LRU缓存

• 思路回忆，要求put()方法和get()方法都要在O(1)的时间复杂度，联想到HashMap。最久未使用，考虑双向链表，通过HashMap找到需要修改的节点，根据已知链表头节点，尾节点可以在O(1)的时间复杂度内快速增加删除节点。
• 由此，代码模板如下：

class LRUCache {

 
    private Map cache = new HashMap();
    private int size;
    private int capacity;
    private DLinkNode head,tail;


    public LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        // 使用伪头部和伪尾部节点
        head = new DLinkNode();
        tail = new DLinkNode();
        head.next = tail;
        tail.prev = head;
    }

    public int get(int key) {
        DLinkNode node = cache.get(key);
        if (node == null){
            return -1;
        }
        moveToHead(node);
        return node.value;
    }

    private void moveToHead(DLinkNode node) {
        removeNode(node);
        head.next.prev=node;
        node.next = head.next;
        node.prev = head;
        head.next = node;
    }
    
    public void removeNode(DLinkNode node){
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    public void put(int key, int value) {
        DLinkNode node = cache.get(key);
        if (node == null){
            DLinkNode newNode = new DLinkNode(key,value);
            cache.put(key,newNode);
            addToHead(newNode);
            size++;
            if (size>capacity){
                DLinkNode temp = removeTail();
                cache.remove(temp.key);
                --size;
            }
        } else {
            // 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
            node.value = value;
            moveToHead(node);
        }
    }

    private DLinkNode removeTail() {
            DLinkNode temp = tail.prev;
            temp.prev.next = tail;
            tail.prev = temp.prev;
            return temp;
    }

    private void addToHead(DLinkNode newNode) {
        newNode.next = head.next;    
        head.next.prev = newNode;
        newNode.prev = head;
        head.next = newNode;
    }
}

class DLinkNode{
    int key;
    int value;
    DLinkNode prev;
    DLinkNode next;

    public DLinkNode() {
    }

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

Java中LinkedHashMap封装Lru缓存，通过重写removeEldestEntry可以快速实现LRU缓存机制。