LRUCache

LRU（Least recently used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是“如果数据最近被访问过，那么将来被访问的几率也更高” 。

代码：

/**
 * @Author: cuzz
 * @Date: 2019/3/16 15:35
 * @Description: LRU cache
 */
public class LRUCache {

    private Map<Integer, DLinkedList> cache = new HashMap<>();
    private int count;
    private int capacity;
    private DLinkedList head, tail;

    public LRUCache(int capacity) {
        this.count = 0;
        this.capacity = capacity;

        this.head = new DLinkedList();
        this.tail = new DLinkedList();

        head.next = tail;
        tail.pre = head;
    }

    public int get(int key) {
        DLinkedList node = cache.get(key);
        if (node == null) {
            return -1;
        }
        removeNode(node);
        addHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        DLinkedList node = cache.get(key);
        if (node == null) {
            node = new DLinkedList(key, value);
            addHead(node);
            cache.put(key, node);
            count++;
            if (count > capacity) {
                DLinkedList preTail = tail.pre;
                removeNode(preTail);
                cache.remove(preTail.key);
                count--;
            }
        } else {
            node.value = value;
            removeNode(node);
            addHead(node);
        }

    }

    // 移除给定的结点
    private void removeNode(DLinkedList node) {
        DLinkedList pre = node.pre;
        DLinkedList next = node.next;
        pre.next = next;
        next.pre = pre;
    }

    // 把结点添加头节点
    private void addHead(DLinkedList node) {
        DLinkedList next = head.next;
        head.next = node;
        node.next = next;
        next.pre = node;
        node.pre = head;
    }

    public static void main(String[] args) {
        LRUCache cache = new LRUCache(2);
        cache.put(1, 1);
        cache.put(2, 2);                    
        System.out.println(cache.get(1));   // 返回 1
        cache.put(3, 3);                    // 使 2 作废
        System.out.println(cache.get(2));   // 返回 -1
        cache.put(4, 4);                    // 使 1 作废
        System.out.println(cache.get(1));   // 返回 -1 未找到
        System.out.println(cache.get(3));   // 返回 3
        System.out.println(cache.get(4));   // 返回 4
    }

}

class DLinkedList {
    int key;
    int value;
    DLinkedList pre;
    DLinkedList next;

    public DLinkedList() {};

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