LRU代码实现详解

什么是LRU？LRU是什么？

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

当你看到这篇文章我就当你有了一定的基础，看过其他LRU的介绍博客了

网友：想了半天终于想明白了为啥要用hashmap和双向链表，

<1>首先我想的是用队列不行吗？

不行，队列只能做到先进先出，但是重复用到中间的数据时无法把中间的数据移动到顶端。

<2> 就用单链表不行吗？

单链表能实现新来的放头部，最久不用的在尾部删除，但删除的时候需要遍历到尾部，因为单链表只有头指针。在用到已经用到过的数据时，还要遍历整合链表，来确定是否用过，然后再遍历到响应位置来剔除的节点，并重新放在头部。这效率可想而知。

这时hashmap的作用就出来了， 它可以在单位的时间判断value的值是否存在，key直接存储节点对象，能直接定位删除对应的节点(将比节点的父节点指向子节点)。要通过一个节点直接获得父节点的话，通过单链表是不行的。
这时双向链表的作用也提现出来了。能直接定位到父节点。 这效率就很高了。而且由于双向链表有尾指针，所以剔除最后的尾节点也十分方便，快捷。

下面的代码就是双向链表和HashMap实现的：

package com.company.test01;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;
/**
 * @ClassName : LRUCache  //类名
 * @Description : LRU  //描述
 * @Author : Mr.Duan  //作者
 * @Date: 2020-08-13 08:57  //时间
 */
public class LRUCache<V> {
    private int capacity=1024;//容量
    private final Map<String, ListNode<String, V>> table = new ConcurrentHashMap<>();//记录Node
    private final ListNode<String, V> head;
    private final ListNode<String, V> tail;
    public LRUCache(int capacity) {
        this();
        this.capacity = capacity;
    }
    public LRUCache() {
        head = new ListNode<>();
        tail = new ListNode<>();
        head.next = tail;
        head.prev = null;
        tail.prev = head;
        tail.next = null;
    }
    public void get(String key) {
        ListNode<String, V> node = table.get(key);
        //如果Node不在表中，代表缓存中并没有
        if (node == null) {
            return;
        }
        //如果存在，则需要移动Node节点到表头
        //截断链表，node.prev -> node  -> node.next ====> node.prev -> node.next
        //         node.prev <- node <- node.next  ====>  node.prev <- node.next
        node.prev.next = node.next;
        node.next.prev = node.prev;
        //移动节点到表头
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        head.next = node;
        //存在缓存表
        table.put(key, node);
    }
    @Override
    public String toString() {
        return "{" +
                "capacity=" + capacity +
                ", table=" + table +
                '}'+"\n";
    }
    public void put(String key, V value) {
        ListNode<String, V> node = table.get(key);
        //如果Node不在表中，代表缓存中并没有
        if (node == null) {
            if (table.size() == capacity) {
                //超过容量了 ,首先移除尾部的节点
                table.remove(tail.prev.key);//移除尾节点的上一个节点
                tail.prev.prev.next = tail;//尾部的上上个节点的下个节点设置为尾节点
                tail.prev = tail.prev.prev;//尾部的上个节点设置为尾部的上上个节点
            }
            node = new ListNode<>();
            node.key = key;
            node.value = value;
            table.put(key, node);
        }
        //如果存在，则需要移动Node节点到表头
        node.next = head.next;
        head.next.prev = node;
        node.prev = head;
        head.next = node;
    }
    /**
     * 双向链表内部类
     */
    public static class ListNode<K, V> {
        private K key;
        private V value;
        ListNode<K, V> prev;
        ListNode<K, V> next;
        public ListNode(K key, V value) {
            this.key = key;
            this.value = value;
        }
        public ListNode() {
        }
        @Override
        public String toString() {
            return "{" +
                    "key=" + key +
                    ", value=" + value +
                    '}'+"\n";
        }
    }
    public static void main(String[] args) {
        LRUCache<ListNode> cache = new LRUCache<>(4);
        ListNode<String, Integer> node1 = new ListNode<>("key1", 1);
        ListNode<String, Integer> node2 = new ListNode<>("key2", 2);
        ListNode<String, Integer> node3 = new ListNode<>("key3", 3);
        ListNode<String, Integer> node4 = new ListNode<>("key4", 4);
        ListNode<String, Integer> node5 = new ListNode<>("key5", 5);
        cache.put("key1", node1);
        System.out.println("插入了："+node1);
        System.out.println(cache);
        cache.put("key2", node2);
        System.out.println("插入了："+node2);
        System.out.println(cache);
        cache.put("key3", node3);
        System.out.println("插入了："+node3);
        System.out.println(cache);
        cache.put("key4", node4);
        System.out.println("插入了："+node4);
        System.out.println(cache);
        cache.get("key2");
        System.out.println("获取了："+node2);
        System.out.println(cache);
        cache.put("key5", node5);
        System.out.println("插入了："+node5);
        System.out.println(cache);
        cache.get("key2");
        System.out.println("获取了："+node2);
        System.out.println(cache);
    }
}

（注意：上面代码为了方便观察表的变化重写了类中的toString（）方法和main中的打印语句，正常状况下是没有的）代码运行结果如下：

"D:\Program Files\Java\jdk1.8.0_144\bin\java.exe" "-javaagent:D:\IntelliJ IDEA 2020.1\lib\idea_rt.jar=52888:D:\IntelliJ IDEA 2020.1\bin" -Dfile.encoding=UTF-8 -classpath "D:\Program Files\Java\jdk1.8.0_144\jre\lib\charsets.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\deploy.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\access-bridge-64.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\cldrdata.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\dnsns.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\jaccess.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\jfxrt.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\localedata.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\nashorn.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\sunec.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\sunjce_provider.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\sunmscapi.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\sunpkcs11.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\ext\zipfs.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\javaws.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\jce.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\jfr.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\jfxswt.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\jsse.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\management-agent.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\plugin.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\resources.jar;D:\Program Files\Java\jdk1.8.0_144\jre\lib\rt.jar;E:\IdeaProjects\20200813\ClassDome\out\production\ClassDome" com.company.test01.LRUCache
插入了：{key=key1, value=1}
{capacity=4, table={key1={key=key1, value={key=key1, value=1}
}
}}
插入了：{key=key2, value=2}
{capacity=4, table={key1={key=key1, value={key=key1, value=1}
}
, key2={key=key2, value={key=key2, value=2}
}
}}
插入了：{key=key3, value=3}
{capacity=4, table={key1={key=key1, value={key=key1, value=1}
}
, key2={key=key2, value={key=key2, value=2}
}
, key3={key=key3, value={key=key3, value=3}
}
}}
插入了：{key=key4, value=4}
{capacity=4, table={key1={key=key1, value={key=key1, value=1}
}
, key2={key=key2, value={key=key2, value=2}
}
, key3={key=key3, value={key=key3, value=3}
}
, key4={key=key4, value={key=key4, value=4}
}
}}
获取了：{key=key2, value=2}
{capacity=4, table={key1={key=key1, value={key=key1, value=1}
}
, key2={key=key2, value={key=key2, value=2}
}
, key3={key=key3, value={key=key3, value=3}
}
, key4={key=key4, value={key=key4, value=4}
}
}}
插入了：{key=key5, value=5}
{capacity=4, table={key2={key=key2, value={key=key2, value=2}
}
, key5={key=key5, value={key=key5, value=5}
}
, key3={key=key3, value={key=key3, value=3}
}
, key4={key=key4, value={key=key4, value=4}
}
}}
获取了：{key=key2, value=2}
{capacity=4, table={key2={key=key2, value={key=key2, value=2}
}
, key5={key=key5, value={key=key5, value=5}
}
, key3={key=key3, value={key=key3, value=3}
}
, key4={key=key4, value={key=key4, value=4}
}
}}
Process finished with exit code 0