LRU Cache

LRU 即 Latest Recently Used 最近最少使用算法，本文介绍该缓存策略以及简单的算法实现

LRU 介绍

LRU 是一种通过丢弃掉最近最少使用的元素的方法来维护缓存的一种策略。
举个栗子，假如缓存的大小是2，按照如下的顺序进行插入和读取元素（key, value)，表现应为：

             // 位于前面的是<最近最少使用>元素
- put(1, 1)  // 1
- put(2, 2)  // 1 - 2
- get(1)     // 2 - 1 , return 1
- put(3, 3)  // 1 - 3
- get(2)     // return -1
- put(4, 4)  // 3 - 4
- get(1)     // return -1
- get(3)     // 4 - 3
- get(4)     // 3 - 4

算法实现

LeetCode 链接
目标： 实现LRU缓存策略，实现get, put 方法，并使get 和 put 方法的时间复杂度为O(1)
思路：

• 首先观察该算法要实现的功能，放入元素&获取元素，其特性为要维护一个类似链表的数据结构，每次使用过的元素（get&put)要从队列中的某个地方放到队尾，而插入元素的时候，需要判断Cache的容量，如果未超过容量则直接放到队尾即可，如果超过Cache的容量，则需要淘汰掉队首元素（最近最少使用），并把新插入的元素放到队尾。
• 可以设置一个有prev和next 指针的链表的数据结构，来满足快速删除插入元素的特性
• 要实现O(1)的时间复杂度，很容易让人想到利用HashMap进行元素的存储
• 另外一个比较巧妙的一点是，由于head 和 tail 元素经常变化，可以利用dummy node来进行算法的实现，可提高算法的可读性和简化算法的实现
• 总结起来就是：结合利用HashMap和List的数据结构实现LRU算法

实现代码参考：

public class LRUCache {
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            prev = null;
            next = null;
        }

    }

    HashMap<Integer, Node> cache;
    int capacity;
    Node head;
    Node tail; // most recently be used , include get & set

    public LRUCache(int capacity) {
        this.capacity = capacity;
        head = new Node(-1, -1);
        tail = new Node(-1, -1);
        cache = new HashMap<>();
    }

    public int get(int key) {
        if(cache.get(key) == null) {
            return -1;
        }
        Node current = cache.get(key);
        current.prev.next = current.next;
        current.next.prev = current.prev;
        moveToTail(current);

        return cache.get(key).value;
    }

    public void put(int key, int value) {
    	// 执行完该get方法后，元素即已经被更新到队尾
        if(get(key) != -1) {
            cache.get(key).value = value;
            return;
        }
        if(cache.size() == capacity) {
            cache.remove(head.next.key);
            head.next = head.next.next;
            head.next.prev = head;
        }
        Node newNode = new Node(key, value);
        cache.put(key, newNode);
        moveToTail(newNode);

    }

    private void moveToTail(Node node) {
        node.prev = tail.prev;
        node.prev.next = node;
        node.next = tail;
        tail.prev = node;
    }
}