如何实现一个LRU算法？

LRU就是Least recently used,最近最少使用，如果空间不足淘汰掉最近最少使用的数据。
实现方式可以有一下三种：

1、单链表

实现原理：
1、插入：插入数据是最新的数据，直接插入到链表尾部
2、查找：查找到的数据移动到链表尾部，代表最新访问。
3、删除：链表头代表最近最少使用，如果链表满，则删除链表头数据

时间复杂度：O(n)

2、哈希表+双向链表

1、先后插入5个节点，每个节点在2个链表中。
2、黑色链表，代表哈希冲突之后的链表。
3、红色链表，代表节点之间的顺序。
4、每个节点，由4部分组成，分别是数据，黑色链表的next指针，红色链表的pre指针和next指针。

查找：通过哈希表查找到，然后移动到双向链表的尾部。
删除：通过哈希表查找到，通过双向链表拿到前驱节点，直接删除即可。
插入：先看是否存在，如果存在移动到链表尾部，如果不存在，链表满的话删除头节点，然后插入链表尾部，否则不满，则直接插入链表尾部。

3、LinkedHashMap

LinkedHashMap继承自HashMap，拥有HashMap的所有特性，同时LinkedHashMap增加了head和tail指针，用于实现双向链表。

1、LinkedHashMap默认的支持按照插入顺序保存数据，新的数据插入双向链表尾部。


2、构造方法支持按照访问顺序，最新访问的数据放到双向链表尾部。

4、如何实现LRU算法呢，自动删除掉链表头的过期数据？

LinkedHashMap默认是不会自动删除链表头节点数据的，我们需要覆盖类的一个方法：removeEldestEntry

1、实现一个类LruLinkedMap继承LinkedHashMap

package com.jane;import java.util.LinkedHashMap;public class LruLinkedMap extends LinkedHashMap {    private int size;    public LruLinkedMap(int initialCapacity,               float loadFactor,               boolean accessOrder) {        super(initialCapacity, loadFactor, accessOrder);        this.size = initialCapacity;    }    /**     * @description 重写LinkedHashMap中的removeEldestEntry方法，当LRU中元素多余6个时，     *              删除最不经常使用的元素     */    @Override    protected boolean removeEldestEntry(java.util.Map.Entry eldest) {        if(size() > size){            return true;        }        return false;    }}

2、启动文件：

package com.jane;import java.util.Map;public class Main {    public static void main(String[] args) {        LruLinkedMap ss = new LruLinkedMap(5, 0.75f, true);        ss.put("1", "3");        ss.put("2", "4");        ss.put("3", "6");        ss.put("4", "1");        ss.put("5", "5");        for(Map.Entry e: ss.entrySet()) {            System.out.println(e.getKey());        }        System.out.println("---------------");        ss.get("1");        for(Map.Entry e: ss.entrySet()) {            System.out.println(e.getKey());        }        System.out.println("---------------");        ss.put("7", "10");        for(Map.Entry e: ss.entrySet()) {            System.out.println(e.getKey());        }    }}

3、结果：

这样LRU就轻松的实现了。