什么是LRU算法

    LRU算法的全称Least Recently Used。即最近最少使用。
    LRU算法是内存管理的一种页面置换算法，对于在内存中但是又不用的数据块叫做LRU，操作系统会将那些数据数据LRU而将其移除内存腾出空间来加载其他数据（以上来自百度百科）。

LRU算法的实现

    LRU算法通常是基于双向链表来实现的，下面我们一起看一下双向链表是如何实现LRU算法的。

image.png

    如上图所示，我们定义了一个双向链表。对链表中元素的操作不外乎四种：get，put，remove，update。其中remove操作，删除链表中的一个元素，不会影响链表中现有的排序情况，而update和put操作可以看作是同一种操作。所以我们主要看get，put操作对链表中元素的影响。

image.png

image.png

基于LinkedHashMap的LRU算法实现

    LinkedHashMap中LRU算法的实现主要依赖的几个方法。

1. afterNodeInsertion(boolean evict)

    void afterNodeInsertion(boolean evict) { // possibly remove eldest
        LinkedHashMap.Entry<K,V> first;
        // first = head 这一步是关键，从if的判断条件中可以看出，在链表的头结点head存在的情况下，会将head赋值给first，然后交给removeEldestEntry(first)执行
        if (evict && (first = head) != null && removeEldestEntry(first)) {
            K key = first.key;
            // 该方法移除的是链表的头结点
            removeNode(hash(key), key, null, false, true);
        }
    }

2. afterNodeAccess(Node<K,V> e)

    void afterNodeAccess(Node<K,V> e) { // move node to last
        LinkedHashMap.Entry<K,V> last;
        // 执行移动操作的前提是accessOrder和要移动的元素e != tail，这是为什么呢，刚开始看到这样的代码我也疑惑，说好的移动到链表的头部呢？挠头
        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;
        }
    }

3. removeEldestEntry(Map.Entry<K,V> eldest)

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
   // 默认返回false，也就是不移除最老的元素，我们需要重新改写该方法，在当前容量大于预设的最大容量时，移除最老元素。 
   return false;
}

    介绍完几个关键方法之后，我们来从整体的角度看一下这几个方法在整个流程中的作用。

image.png

image.png

Demo

public class LruCache {

    private Map<Object, Object> cache;

    LruCache(int size) {
        // 初始化LinkedHashMap三个参数，容量，负载引子，accessOrder
        this.cache = new LinkedHashMap<Object, Object>(size, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Object, Object> eldest) {
               // 比较当前LinkedHashMap中的节点数量与允许存放最大数量的比较
                return super.size() > size;
            }
        };
    }

    public Object put(Object key, Object value) {
        return cache.put(key, value);
    }

    public Object get(Object key) {
        return cache.get(key);
    }
}