正文在下面，先打个广告：

使用javaAPI

java 的LinkedHashMap可以实现LRU算法，LinkedHashMap 本身内部有一个触发条件则自动执行的方法：删除最老元素（最近最少使用的元素）。我们只需要通过参数控制数据排序逻辑和数据删除规则就行了。

LinkedHashMap源码中有这么一个注释：

<p>The {@link #removeEldestEntry(Map.Entry)} method may be overridden to
 * impose a policy for removing stale mappings automatically when new mappings
 * are added to the map.

可以看到 removeEldestEntry 方法可以用来删除过时的数据。不过他的默认实现是返回false，需要我们手动重写该方法。

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
 return false;
}

还有一个需要注意的是，LinkedHashMap默认是按照插入顺序排序的，很显然不能满足LRU算法的需求。LRU是希望按照访问顺序排序，最新访问的数据放到队头，老数据放到队尾，这样数据总量超过容量时，删除队尾的数据即可。

LinkedHashMap构造函数中有一个参数accessOrder，该参数控制了数据排序的规则。下面get方法中可以看到，有个if判断，如果accessOrder是true，则将当前访问的node移动到队尾last（LinkedHashMap是用last存储最新数据）

/**
 * Constructs an empty <tt>LinkedHashMap</tt> instance with the
 * specified initial capacity, load factor and ordering mode.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @param  accessOrder     the ordering mode - <tt>true</tt> for
 *         access-order, <tt>false</tt> for insertion-order
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public LinkedHashMap(int initialCapacity,
                     float loadFactor,
                     boolean accessOrder) {
    super(initialCapacity, loadFactor);
    this.accessOrder = accessOrder;
}

public V get(Object key) {
        Node<K,V> e;
        if ((e = getNode(hash(key), key)) == null)
            return null;
        if (accessOrder)
            afterNodeAccess(e);
        return e.value;
    }

void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        if (accessOrder && (last = tail) != e) {
            LinkedHashMap.Entry<K,V> p =
                (LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;
            p.after = null;
            if (b == null)
                head = a;
            else
                b.after = a;
            if (a != null)
                a.before = b;
            else
                last = b;
            if (last == null)
                head = p;
            else {
                p.before = last;
                last.after = p;
            }
            tail = p;
            ++modCount;
        }
    }

当插入数据时，就会通过removeEldestEntry方法的返回值决定是否需要删除老的数据。

void afterNodeInsertion(boolean evict) { // possibly remove eldest
    LinkedHashMap.Entry<K,V> first;
    if (evict && (first = head) != null && removeEldestEntry(first)) {
        K key = first.key;
        removeNode(hash(key), key, null, false, true);
    }
}

完整代码：

public interface ILru {
    void put(Object key, Object value);

    void remove(String key);

    Object get(String key);
}

public class JavaLRUCache implements ILru{

    private Map<Object, Object> map;
    private final int capacity;

    public JavaLRUCache(int capacity) {
        this.capacity = capacity;
        map = new LinkedHashMap<Object, Object>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
                return size() > capacity;
            }

            @Override
            public String toString() {
                return super.toString();
            }
        };
    }

    @Override
    public Object get(String key) {
        return map.get(key);
    }

    @Override
    public void put(Object key, Object value) {
        map.put(key, value);
    }

    @Override
    public void remove(String key) {
        map.remove(key);
    }

    @Override
    public String toString() {
        return "JavaLRUCache{" +
                "map=" + map +
                ", capacity=" + capacity +
                '}';
    }
}

纯手撸

纯手撸的话，其实和上面LinkedHashMap原理一样。
先定义node

/**
 * @author liubenlog
 * @className Node
 * @description map 中的V，设置为一个对象，主要是为了记录前后指针，已达到 0（1）的时间复杂度
 * @date 2020/10/22 16:02
 */
@Data
public class Node {
    private Object key;
    private Object value;
    private Node pre;
    private Node next;

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

    @Override
    public String toString() {
        return key.toString() + "=" + value.toString();
    }
}

再定义链表，包含LRU的核心算法

/**
 * @author liubenlog
 * @className MyList
 * @description 双向链表. 我这里规定head是最新的数据
 * @date 2020/10/22 16:03
 */
public class MyList {

    private long maxSize;

    private Node head;

    private Node tail;

    private long size;

    private Map map;

    public MyList(long maxSize, Map map) {
        this.maxSize = maxSize;
        this.map = map;
    }

    /**
     * 直接添加到tail
     *
     * @param node
     */
    public void add(Node node) {
        size++;
        if (null == head) {
            //head为空，说明此时队列中一个数据也没有
            head = node;
            tail = node;
        } else {
            node.setPre(tail);
            tail.setNext(node);
            tail = node;

            //超过容量后，将head元素删除
            if (size > maxSize) {
                map.remove(head.getKey());

                Node next = head.getNext();
                next.setPre(null);
                head.setNext(null);
                head = next;
                size--;
            }
        }
    }

    public void remove(Node node) {
        if (null == head) {//队列为空
            return;
        } else if (head == node && tail == node) {//只有一个元素时
            head = null;
            tail = null;
            size--;
        } else {
            Node pre = node.getPre();
            Node next = node.getNext();
            if (null != pre) {
                pre.setNext(next);
            } else {
                head = next;
            }
            if (null != next) {
                next.setPre(pre);
            } else {
                tail = pre;
            }
            node.setPre(null);
            node.setNext(null);
            size--;
        }
    }

    public void get(Node node) {
        remove(node);
        add(node);
    }

    public void update(Node node) {
        remove(node);
        add(node);
    }

    @Override
    public String toString() {
        String result = "";
        if (head == null) {
            return result;
        } else {
            Node next = head;
            result += next + ", ";
            while ((next = next.getNext()) != null) {
                result += next + ", ";
            }
            return result;
        }
    }
}

最后封装LRU

public class LRU implements ILru{
    private HashMap<Object, Node> map = new HashMap();
    private MyList list;

    public LRU(long size) {
        list = new MyList(size, map);
    }

    @Override
    public void put(Object key, Object value) {
        Node node = map.get(key);
        if (node == null) {
            node = new Node(key, value);
            map.put(key, node);
            list.add(node);
        } else {
            node.setValue(value);
            map.put(key, node);
            list.update(node);
        }
    }

    @Override
    public void remove(String key) {
        list.remove(map.get(key));
        map.remove(key);
    }

    @Override
    public Object get(String key) {
        Node node = map.get(key);
        if (node == null) {
            return null;
        }
        list.get(node);

        return node.getValue();
    }

    @Override
    public String toString() {
        return "LRU{" +
                "list=" + list +
                '}';
    }
}

测试

测试代码

public class Main {
    public static void main(String[] args) {
        lruTest(new LRU(5));
        System.out.println("-------------------------");
        lruTest(new JavaLRUCache(5));
    }

    static void lruTest(ILru lru){
        lru.put("a", 1);
        System.out.println(lru.toString());
        lru.put("b", 2);
        System.out.println(lru.toString());
        lru.put("c", 3);
        System.out.println(lru.toString());
        lru.put("d", 4);
        System.out.println(lru.toString());
        lru.get("a");
        System.out.println("get a 1  " + lru.toString());
        lru.get("b");
        System.out.println("get b 2  " + lru.toString());
        lru.get("b");
        System.out.println("get b 2  " + lru.toString());
        lru.get("d");
        System.out.println("get d 4  " + lru.toString());
        lru.put("e", 5);
        System.out.println(lru.toString());
        lru.put("f", 6);
        System.out.println(lru.toString());
        lru.put("g", 7);
        System.out.println(lru.toString());
        lru.remove("g");
        System.out.println("remove g 7  " + lru.toString());
        lru.remove("e");
        System.out.println("remove e 5  " + lru.toString());
        lru.put("e", 5);
        System.out.println(lru.toString());
        lru.put("e", 9);
        System.out.println(lru.toString());
        lru.put("f", "f");
        System.out.println(lru.toString());
    }
}

输出：

LRU{list=a=1, }
LRU{list=a=1, b=2, }
LRU{list=a=1, b=2, c=3, }
LRU{list=a=1, b=2, c=3, d=4, }
get a 1  LRU{list=b=2, c=3, d=4, a=1, }
get b 2  LRU{list=c=3, d=4, a=1, b=2, }
get b 2  LRU{list=c=3, d=4, a=1, b=2, }
get d 4  LRU{list=c=3, a=1, b=2, d=4, }
LRU{list=c=3, a=1, b=2, d=4, e=5, }
LRU{list=a=1, b=2, d=4, e=5, f=6, }
LRU{list=b=2, d=4, e=5, f=6, g=7, }
remove g 7  LRU{list=b=2, d=4, e=5, f=6, }
remove e 5  LRU{list=b=2, d=4, f=6, }
LRU{list=b=2, d=4, f=6, e=5, }
LRU{list=b=2, d=4, f=6, e=9, }
LRU{list=b=2, d=4, e=9, f=f, }
-------------------------
JavaLRUCache{map={a=1}, capacity=5}
JavaLRUCache{map={a=1, b=2}, capacity=5}
JavaLRUCache{map={a=1, b=2, c=3}, capacity=5}
JavaLRUCache{map={a=1, b=2, c=3, d=4}, capacity=5}
get a 1  JavaLRUCache{map={b=2, c=3, d=4, a=1}, capacity=5}
get b 2  JavaLRUCache{map={c=3, d=4, a=1, b=2}, capacity=5}
get b 2  JavaLRUCache{map={c=3, d=4, a=1, b=2}, capacity=5}
get d 4  JavaLRUCache{map={c=3, a=1, b=2, d=4}, capacity=5}
JavaLRUCache{map={c=3, a=1, b=2, d=4, e=5}, capacity=5}
JavaLRUCache{map={a=1, b=2, d=4, e=5, f=6}, capacity=5}
JavaLRUCache{map={b=2, d=4, e=5, f=6, g=7}, capacity=5}
remove g 7  JavaLRUCache{map={b=2, d=4, e=5, f=6}, capacity=5}
remove e 5  JavaLRUCache{map={b=2, d=4, f=6}, capacity=5}
JavaLRUCache{map={b=2, d=4, f=6, e=5}, capacity=5}
JavaLRUCache{map={b=2, d=4, f=6, e=9}, capacity=5}
JavaLRUCache{map={b=2, d=4, e=9, f=f}, capacity=5}