引言：最近许多人在博客中提到自己在面试时被问“LruCache 的原理是？”，发现自己之前完全没有接触过这个知识点，本着知其然知其所以然的态度，先搜索了一些博文了解相关知识，就去看源码了。现在大概知道 LruCache 是啥，写个博文权当是学习笔记把

LruCache 的前世今生

LruCache 是何方神圣？

我一般不喜欢野路子的定义，所以我摘选了 Android 官方对 LruCache 的定义：

A cache that holds strong references to a limited number of values. Each time a value is accessed, it is moved to the head of a queue. When a value is added to a full cache, the value at the end of that queue is evicted and may become eligible for garbage collection.

定义的意思是：LruCache 是对限定数量的缓存对象持有强引用的缓存，每一次缓存对象被访问，都会被移动到队列的头部。当有对象要被添加到已经达到数量上限的 LruCache 中，队列尾部的对象将会被移除，而且可能会被垃圾回收机制回收。

所以从定义里我们可以知道：LruCache 中有一个队列存储对象的访问顺序，在 LruCache 达到存储上线时，将会通过移除队列中的队尾元素为需要添加进来的元素腾出空间。

LruCache 中的队列的存在意义是什么？

要探讨这个问题首先我们要知道的是：LruCache 中的 Lru 指的是“Least Recently Used-近期最少使用算法”。这就意味着，LruCache 应该是一个能够判断哪个缓存对象是近期最少使用的缓存类。解释到这里我相信大家都能明白为什么需要引入队列了。

引入队列的意义在于，每一次 LruCache 中的某个缓存对象被访问，该对象在队列中的位置就会发生改变——即提到队列的头部，假设队列有 n 个元素，n-1 个元素都被不同频率地访问过，唯独元素 A 一直没有被访问，那么 A 必然处于队尾，成为“近期最少使用元素”了。

LruCache 的实现原理

LruCache 初步源码分析

代码太多，我不可能全都贴上来，所以我就按照我的思路来贴啦～

    public class LruCache<K, V> {
        private final LinkedHashMap<K, V> map;

        /** Size of this cache in units. Not necessarily the number of elements. */
        private int size;
        private int maxSize;

        private int putCount;
        private int createCount;
        private int evictionCount;
        private int hitCount;
        private int missCount;

从代码里我们可以知道：LruCache 不是其他类的子类，并且其中实际涉及到的只有一个 LinkedHashMap 对象和一堆 int 值。也就是说，LruCache 实现其核心逻辑的关键应该就是 LinkedHashMap。

那我们就先来看看 LinkedHashMap的源码吧。

LinkedHashMap 剖析

LinkedHashMap 是什么

同样的，引用官方的解释：

LinkedHashMap is an implementation of Map that guarantees iteration order. All optional operations are supported.

Entries are kept in a doubly-linked list. The iteration order is, by default, the order in which keys were inserted. Reinserting an already-present key doesn’t change the order. If the three argument constructor is used, and accessOrder is specified as true, the iteration will be in the order that entries were accessed. The access order is affected by put, get, and putAll operations, but not by operations on the collection views.

LinkedHashMap 是 Map 的一种实现（HashMap 的子类，HashMap 的父类是抽象 Map 类，其中实现了 Map 接口），能够保证迭代器的顺序。LinkedHashMap 中的数据通过一个双向链表存储，默认情况下，迭代器的顺序为键的掺入顺序，并且重新插入一个已经存在的键不会改变迭代器的顺序。

如果构造方法中的第三个参数 boolean accessOrder 被使用，而且 accessOrder 的值为 true，那么迭代器的顺序就是数据的访问顺序，并且，这个顺序将受 put,get,putall 这些方法影响，但不受集合视图操作的影响。

LinkedHashmap 的解释证明了我们刚刚的猜测 LruCache 实现其核心逻辑的关键应该就是 LinkedHashMap 是对的，那么我们只要弄懂了 LinkedHashpMap 的具体原理，LruCache 的原理也不是问题了。

LinkedHashMap 使用范例

在分析 LinkedHashMap 之前，我们不妨先看看 LinkedHashMap 到底能干些什么，毕竟从他的外在表现去分析内在逻辑会更轻松些，下面是一段简单的 Java 代码：

public class Demo {
    public static void main(String[] args) {
        LinkedHashMap<String, String> accessOrderMap = new LinkedHashMap<>(10, 0.75f, true);

        System.out.println("处理前");

        //受访问顺序影响的LinkedHashMap测试
        accessOrderMap.put("one", "one");
        accessOrderMap.put("two", "two");
        accessOrderMap.put("three", "three");

        //未经过任何处理的输出
        for(Entry<String, String> entry : accessOrderMap.entrySet()){
            System.out.println(entry.getValue());
        }

        System.out.println("处理后");

        //访问Map中的恶元素，改变顺序
        accessOrderMap.get("one");

        //经过处理的输出
        for(Entry<String, String> entry : accessOrderMap.entrySet()){
            System.out.println(entry.getValue());
        }
    }
}

这是输出：

处理前
one
two
three
处理后
two
three
one

我们可以看到，处理后 one 的位置显然发生了改变，跑到了 two,three 的前面。

LinkedHashMap 实现原理

我们直接看 LinkedHashMap 中相关的第三个构造方法吧：

public LinkedHashMap(
            int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        init();
        this.accessOrder = accessOrder;
    }

@Override void init() {
        header = new LinkedEntry<K, V>();
    }

我们可以看到，构造方法调用了父类的构造方法，创建了一个 LinkedEntry 对象，并把 accessOrder 的值设为构造方法传入的值。那这个 LinkedEntry 是什么呢？

    /**
     * LinkedEntry adds nxt/prv double-links to plain HashMapEntry.
     */
    static class LinkedEntry<K, V> extends HashMapEntry<K, V> {
        LinkedEntry<K, V> nxt;
        LinkedEntry<K, V> prv;

        /** Create the header entry */
        LinkedEntry() {
            super(null, null, 0, null);
            nxt = prv = this;
        }

        /** Create a normal entry */
        LinkedEntry(K key, V value, int hash, HashMapEntry<K, V> next,
                    LinkedEntry<K, V> nxt, LinkedEntry<K, V> prv) {
            super(key, value, hash, next);
            this.nxt = nxt;
            this.prv = prv;
        }
    }

我们可以看到，LinkedEntry 就是用于存储数据的双向链表。所以，我们现在只需要知道 LinkedHashMap 类是如何根据 accessOrder 的值，决定程序使用 get,put 等方法将如何操作 LinkedEntry 就可以知道一整个 LinkedHashMap 的实现原理了。

我们追踪 accessOrder 的值很容易发现在 get 方法中有相应的处理：

    /**
     * Returns the value of the mapping with the specified key.
     *
     * @param key
     *            the key.
     * @return the value of the mapping with the specified key, or {@code null}
     *         if no mapping for the specified key is found.
     */
    @Override public V get(Object key) {
        /*
         * This method is overridden to eliminate the need for a polymorphic
         * invocation in superclass at the expense of code duplication.
         */
        if (key == null) {
            HashMapEntry<K, V> e = entryForNullKey;
            if (e == null)
                return null;
            if (accessOrder)
                makeTail((LinkedEntry<K, V>) e);
            return e.value;
        }

        int hash = Collections.secondaryHash(key);
        HashMapEntry<K, V>[] tab = table;
        for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
                e != null; e = e.next) {
            K eKey = e.key;
            if (eKey == key || (e.hash == hash && key.equals(eKey))) {
                if (accessOrder)
                    makeTail((LinkedEntry<K, V>) e);
                return e.value;
            }
        }
        return null;
    }

从代码中可以看到，只要 accessOrder 为 true，就会执行 makeTail 方法操作一个新建的 LinkedEntry 对象，我们不妨进入 makeTail 方法一探究竟：

    /**
     * Relinks the given entry to the tail of the list. Under access ordering,
     * this method is invoked whenever the value of a  pre-existing entry is
     * read by Map.get or modified by Map.put.
     */
    private void makeTail(LinkedEntry<K, V> e) {
        // Unlink e
        e.prv.nxt = e.nxt;
        e.nxt.prv = e.prv;

        // Relink e as tail
        LinkedEntry<K, V> header = this.header;
        LinkedEntry<K, V> oldTail = header.prv;
        e.nxt = header;
        e.prv = oldTail;
        oldTail.nxt = header.prv = e;
        modCount++;
    }

相信这里的逻辑稍微学过数据结构的朋友都能看懂了，就是改变某个结点的位置，把它放到头部。

get 带来的队列变化我们是知道了，那 put 呢？我们一搜索 put，发现类里没有这个方法，这是什么鬼……莫慌，我们耐心地翻翻代码会发现 addNewEntry(K key, V value, int hash, int index) 和 addNewEntryForNullKey(V value) 方法，而它们就是实现 put 改变队列逻辑的两个方法了，我们不妨看看：

    @Override void addNewEntry(K key, V value, int hash, int index) {
        LinkedEntry<K, V> header = this.header;

        // Remove eldest entry if instructed to do so.
        LinkedEntry<K, V> eldest = header.nxt;
        if (eldest != header && removeEldestEntry(eldest)) {
            remove(eldest.key);
        }

        // Create new entry, link it on to list, and put it into table
        LinkedEntry<K, V> oldTail = header.prv;
        LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
                key, value, hash, table[index], header, oldTail);
        table[index] = oldTail.nxt = header.prv = newTail;
    }

    @Override void addNewEntryForNullKey(V value) {
        LinkedEntry<K, V> header = this.header;

        // Remove eldest entry if instructed to do so.
        LinkedEntry<K, V> eldest = header.nxt;
        if (eldest != header && removeEldestEntry(eldest)) {
            remove(eldest.key);
        }

        // Create new entry, link it on to list, and put it into table
        LinkedEntry<K, V> oldTail = header.prv;
        LinkedEntry<K, V> newTail = new LinkedEntry<K,V>(
                null, value, 0, null, header, oldTail);
        entryForNullKey = oldTail.nxt = header.prv = newTail;
    }

addNewEntry 方法中，当有新元素加入时就会执行进行判断，决定是否移除过期的元素，当我们进入 removeEldestEntry 方法会发现，removeEldestEntry 方法的返回值恒为 false，也就是说过期元素无论如何都不会被移除，那这是什么意思呢？

其实这挺好理解的，LinkedHashMap 作为一个存储结构，它并没有限制自身的存储容量（因为他的实现基于一个双向链表），所以他没有理由在默认实现中移除过期元素，而 LruCache 中则是自己设计了相应的逻辑去处理过期元素。

再探 LruCache

通过刚刚的分析，我们已经知道 LruCache 的核心 LinkedHashMap 是如何提取“近期最少使用对象”的了，那么 LruCache 中还利用 LinkedHashMap 的特性做了什么事呢？大家跟着我继续探索吧～

通过 get/put 方法我们可以知道，LruCache 是通过 trimToSize 来控制其中的元素数量的，当达到数量上限，添加元素则会将过期元素移除：

    private void trimToSize(int maxSize) {
        while (true) {
            K key;
            V value;
            synchronized (this) {
                if (size < 0 || (map.isEmpty() && size != 0)) {
                    throw new IllegalStateException(getClass().getName()
                            + ".sizeOf() is reporting inconsistent results!");
                }

                if (size <= maxSize) {
                    break;
                }

                // BEGIN LAYOUTLIB CHANGE
                // get the last item in the linked list.
                // This is not efficient, the goal here is to minimize the changes
                // compared to the platform version.
                Map.Entry<K, V> toEvict = null;
                for (Map.Entry<K, V> entry : map.entrySet()) {
                    toEvict = entry;
                }
                // END LAYOUTLIB CHANGE

                if (toEvict == null) {
                    break;
                }

                key = toEvict.getKey();
                value = toEvict.getValue();
                map.remove(key);
                size -= safeSizeOf(key, value);
                evictionCount++;
            }

            entryRemoved(true, key, value, null);
        }
    }

代码首先作一些简单判断，只有 size > maxSize 才会执行相关逻辑：遍历 LinkedHashMap 双向链表的元素，取得队列尾部的元素（就是我们所说的过期元素），如果它不为空，就将它移除。

注意事项

1、如果你的缓存对象持有需要被精确回收的资源，重写 entryRemoved 方法能完成你的需求。

2、默认情况下，缓存空间的大小由元素的数量决定，但你可以在不同的单元中重写 sizeOf 方法改变大小。例如：bitmap 对象大小为 4m

   int cacheSize = 4 * 1024 * 1024; // 4MiB
   LruCache bitmapCache = new LruCache(cacheSize) {
       protected int sizeOf(String key, Bitmap value) {
           return value.getByteCount();
       }
   }}

3、传入 LruCache 的键值对不能是 null，因为 get/put/remove 方法的含义会因此变得模糊。