LRU（last recent used）

package fighting.algorithm.project;

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

/**
 * LRU：即last recent used，最近使用的队列
 * <p>
 * 作用：
 * 用于缓存，当内存满时，删除最近未使用的元素
 * <p>
 * 操作：
 * put(k, v)：插入元素，当内存满时需要先做清除。满足O(1)复杂度
 * get(k)：获取，同时设为最近使用。满足O(1)复杂度
 * <p>
 * 分析：
 * 最近使用关系，可使用元素顺序来表示，即队头是最近使用的，队尾的是最后使用的
 * 需要满足快速查询：哈希表
 * 满足元素顺序：链表
 * <p>
 * 结论：
 * 使用双向链表作为基础，最近使用的移到队头，内存不足时删除队尾的。双向的目的是做O(1)删除
 * 用哈希表来加速查询
 */
public class LRU {

    private Map<Integer, Node> map;

    private DoubleLinkedList doubleLinkedList;

    private int maxSize;

    private int size;

    public LRU(int maxSize) {
        this.maxSize = maxSize;
        doubleLinkedList = new DoubleLinkedList();
        map = new HashMap<>();
    }

    /**
     * 添加元素并移到队头
     * 1、已存在
     * 2、已满
     * 3、注意移到队头并更新size
     */
    public void put(int k, int value) {
        if (map.containsKey(k)) {
            doubleLinkedList.remove(map.get(k));
        } else if (size == maxSize) {
            Node deletedNode = doubleLinkedList.removeLast();
            map.remove(deletedNode.key);
        } else {
            size++;
        }

        Node newNode = new Node(k, value);
        doubleLinkedList.addFirst(newNode);
        map.put(k, newNode);
    }

    /**
     * 获取元素并移到队头
     */
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        doubleLinkedList.remove(node);
        doubleLinkedList.addFirst(node);
        return node.value;
    }

    public static void main(String[] args) {
        LRU lru = new LRU(3);
        lru.put(1, 1);
        lru.put(2, 2);
        lru.put(3, 3);
        lru.put(4, 4);
        lru.doubleLinkedList.print();

        System.out.println(lru.get(2));
        lru.put(5, 5);
        lru.doubleLinkedList.print();
    }

    public static void doubleLinkedListTest() {
        Node node1 = new Node(1, 1);
        Node node2 = new Node(2, 2);
        Node node3 = new Node(3, 3);
        Node node4 = new Node(4, 4);

        DoubleLinkedList linkedList = new DoubleLinkedList();
        linkedList.addFirst(node4);
        linkedList.addFirst(node3);
        linkedList.addFirst(node2);
        linkedList.addFirst(node1);

        linkedList.print();
        linkedList.removeLast();
        linkedList.remove(node1);
        linkedList.print();
        linkedList.remove(node2);
        linkedList.removeLast();
        linkedList.print();
    }
}

/**
 * 链表节点
 */
class Node {
    public int key, value;
    public Node prev, next;

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

/**
 * 双向链表
 * 注意size为0（空队列），size为1（头尾相同）的情况
 * 注意对size做加减操作
 */
class DoubleLinkedList {
    private Node head, tail;
    private int size;

    /**
     * 添加到队头
     */
    public void addFirst(Node node) {
        if (size == 0) {
            head = tail = node;
            node.prev = node.next = null;
            size++;
            return;
        }

        node.next = head;
        head.prev = node;
        head = node;
        size++;
    }

    /**
     * 移除给定元素
     */
    public void remove(Node node) {
        if (node == tail) {
            removeLast();
            return;
        }

        size--;
        if (head == node) {
            head = node.next;
            return;
        }

        node.prev.next = node.next;
    }

    /**
     * 移除最后一个元素
     */
    public Node removeLast() {
        if (size == 0) {
            return null;
        }

        if (size == 1) {
            Node last = tail;
            head = tail = null;
            size = 0;
            return last;
        }

        Node last = tail;
        Node secondLast = tail.prev;
        secondLast.next = null;
        tail = secondLast;
        size--;
        return last;
    }

    public void print() {
        Node node = head;
        System.out.println();
        while (node != null) {
            System.out.println(node.value);
            node = node.next;
        }
        System.out.println();
    }
}