LruCache

LruCache

图片缓存常用的容器， Least Recently Used Cache（最近最少使用）。
顾名思义，这个缓存算法的亮点： 当缓存内容过多的时候， 将最近最少使用的缓存对象移除；

先看看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;
    ......
}

其中， 内部的数据是通过LinkedHashMap来存储的， LinkedHashMap可以实现最新插入排序和最近使用的排序两种方式。
最新插入排序应该很好理解， 最后插入的元素放在链表的末端； 最近使用排序，则需要在访问元素的时候（也就是get() 方法）做一些操作，使得最新访问的元素移动到最末端， 而链表的结构则对于这种插入删除的操作时间复杂度为O(1)， 当然是在找到要插入节点的情况下。

下面我们看看LInkedHashMap实现最新访问排序的方法，首先， 我们通过源码看到， 链表的节点对象LinkedHashMapEntry:

private static class LinkedHashMapEntry<K,V> extends HashMapEntry<K,V> {
        // These fields comprise the doubly linked list used for iteration.
        LinkedHashMapEntry<K,V> before, after;

        LinkedHashMapEntry(int hash, K key, V value, HashMapEntry<K,V> next) {
            super(hash, key, value, next);
        }
        ......
}

可以看出是一个双链表的结构， 至于为什么用双链表，是因为需要在尾部做插入操作， 而尾部做插入操作， 双链表的结构是O(1)的时间复杂度。
下面看看LinkedHashMap在调用get()方法后，是如何实现将最近查找过的元素放到最后的。

  public V get(Object key) {
        LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
        if (e == null)
            return null;
        e.recordAccess(this);
        return e.value;
    }

      void recordAccess(HashMap<K,V> m) {
            LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
            if (lm.accessOrder) {
                lm.modCount++;
                remove();
                addBefore(lm.header);
            }
        }
        /**
         * Removes this entry from the linked list.
         */
        private void remove() {
            before.after = after;
            after.before = before;
        }

        /**
         * Inserts this entry before the specified existing entry in the list.
         */
        private void addBefore(LinkedHashMapEntry<K,V> existingEntry) {
            after  = existingEntry;
            before = existingEntry.before;
            before.after = this;
            after.before = this;
        }

recordAccess() 方法是主要的排序方法， 这个方法是Entry的方法， 他会根据变量accessOrder， 是否按照最近最少使用排序， 然后进一步操作， 如果是最近最少，则移除该元素， 将该元素加到header节点之前， 也就是最后一个节点了。

所以， 可以看到，实现最近最少使用的主要是依靠LinkedHashMap这一结构。 而LruCache则只要调用相应的方法， 并且维护数据量在不超出最大范围即可， 那下面就再看一下trimToSize这一方法：

  public 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;
                }

                Map.Entry<K, V> toEvict = map.eldest();
                if (toEvict == null) {
                    break;
                }

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

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

其中是一个死循环， 跳出的条件是size小于设置的最大容量， 或者链表的eldest节点为空。而eldest的获取方法则是header.after, 即头节点后第一个节点。