实现时间复杂度为O(1)的LRU Cache

LRU (Least Recently Used)，最近最少使用策略

基于链表的简单实现

维护一个有序的单链表，越靠近链表尾部的结点是越早之前访问的。当有一个新的数据被访问时，从链表头部开始顺序遍历链表：
1.如果此数据之前已经被缓存在链表中，我们遍历得到这个数据对应的结点，并将其从原来的位置删除，然后再插入到链表的头部
2.如果此数据没有在缓存链表中：Ⅰ如果缓存未满，则直接插入链表头部 Ⅱ如果缓存已满，删除尾部结点，新的结点插入头部

由于使用的是链表，每次访问元素都需要遍历，所以这种实现方式的时间复杂度为O（n）

基于哈希表+双向链表的简单实现

数据存在双向链表，由于是双向链表，可以保证删除节点时，时间复杂度为O(1)；但是链表的查询的复杂度为O(n)，所以使用哈希表来改进，通过哈希表，我们可以直接找到双向链表中的每一个结点，从而实现时间复杂度为O(1)的LRU Cache

package listnode;


import java.util.HashMap;
import java.util.Map;

public class LRUCache {

    private int capacity;

    private Map<Integer, Node> map;

    private DoubleLinkedList doubleLinkedList;

    LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        doubleLinkedList = new DoubleLinkedList();
    }

    public int get(int key) {
        Node node = map.get(key);
        if (node == null) return -1;
        // 查询之后需要提到最前面
        put(key, node.value);
        return node.value;
    }

    public void put(int key, int value) {
        Node node = new Node(key, value);
        if (map.containsKey(key)) {
            doubleLinkedList.remove(map.get(key));
        } else {
            if (doubleLinkedList.size == capacity) {
                // 满了需要删除最后面的缓存
                Node last = doubleLinkedList.removeLast();
                map.remove(last.key);
            }
        }
        doubleLinkedList.add(node);
        map.put(key, node);
    }

    /**
     * 双向链表
     */
    class DoubleLinkedList {
        int size;
        Node head;
        Node tail;

        DoubleLinkedList() {
            head = new Node(0, 0);
            tail = new Node(0, 0);
            head.next = tail;
            tail.prev = head;
        }

        void add(Node node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
            size++;
        }

        void remove(Node node) {
            node.next.prev = node.prev;
            node.prev.next = node.next;
            size--;
        }

        Node removeLast() {
            if (head.next == tail) return null;
            Node last = tail.prev;
            remove(last);
            return last;
        }
    }

    /**
     * 链表中的节点
     */
    class Node {
        int key;
        int value;
        Node prev;
        Node next;

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

平常见到的LRU

• innodb的缓存池，使用的是LRU Cache，不过其策略略微变化：将新查询的SQL放到缓存的3/8处