LRU 缓存的JAVA实现

　　LRU(最近最少使用)  缓存为一段固定大小的缓存，按最近最少使用的淘汰策略对数据进行管理。

　　一个 LRU 缓存应当支持 put 和 get 操作：

　　进行 get 操作时，发生 cache miss 返回固定标识。缓存命中在返回数据的同时更新最近使用时间。

　　进行 put 操作时，如果 key 存在则更新数据的同时更新最近使用时间。key 不存在则新增缓存数据并将其标识位最近访问的数据。

　　总的来说需要两个数据结构复合完成对数据的存取及对访问时间的排序。需要一张哈希表存储键值对，同时可以通过一个双向链表对各节点的访问时间进行排序。

　　借助哈希表将存取操作的时间复杂度控制在 O(1) ，通过双向链表记录访问顺序。

public class LRUCache {

    /**
     * @Author Niuxy
     * @Date 2020/6/7 12:20 上午
     * @Description 双向链表，记录最近访问顺序
     */
    private class LRUNode {
        LRUNode(Integer key,Integer value) {
            this.value = value;
            this.key = key;
        }

        LRUNode next;
        LRUNode pre;
        Integer value;
        Integer key;
    }

    //虚拟头结点
    private LRUNode firstNode;
    //虚拟尾结点
    private LRUNode lastNode;
    //当前数据长度
    private int size;
    //缓存容量
    private int capacity;

    private Map<Integer, LRUNode> cacheMap;

    LRUCache(int capacity) {
        this.size = 0;
        this.capacity = capacity;
        this.firstNode = new LRUNode(0, Integer.MIN_VALUE);
        this.lastNode = new LRUNode(0, Integer.MAX_VALUE);
        this.cacheMap = new HashMap<Integer, LRUNode>();
        firstNode.next = lastNode;
        lastNode.pre = firstNode;
    }

    //查找元素
    public Integer get(Integer key) {
        LRUNode node = cacheMap.get(key);
        if (node == null) {
            return -1;
        }
        removeToHead(node);
        return node.value;
    }

    //新增元素
    public void put(Integer key, Integer value) {
        LRUNode beforeNode = cacheMap.get(key);
        //key 已存在，覆盖
        if (beforeNode != null) {
            beforeNode.value = value;
            removeToHead(beforeNode);
            return;
        }
        LRUNode node = new LRUNode(key, value);
        cacheMap.put(key, node);
        putToHead(node);
        size++;
        if (size > capacity) {
            removeLast();
            size--;
        }
        printList();
    }

    private final void putToHead(LRUNode node) {
        node.next = firstNode.next;
        firstNode.next = node;
        node.pre = firstNode;
        node.next.pre = node;
    }

    private final void removeToHead(LRUNode node) {
        removeNode(node.key);
        putToHead(node);
    }

    private final void removeLast() {
        removeNode(lastNode.pre.key);
    }

    private final void removeNode(Integer key) {
        LRUNode node = cacheMap.get(key);
        if (node == null) {
            return;
        }
        node.pre.next = node.next;
        node.next.pre = node.pre;
        cacheMap.remove(key);
    }

    private void printList() {
        LRUNode node = firstNode.next;
        System.out.print("***");
        while (node != lastNode) {
            System.out.print(node.key + ":" + node.value + " , ");
            node = node.next;
        }
        System.out.println(" --- ");
    }
}