因此LRU(Least Recently Used)缓存算法便应运而生，LRU是最近最少使用的算法，它的核心思想是当缓存满时，会优先淘汰那些最近最少使用的缓存对象。采用LRU算法的缓存有两种：LrhCache和DisLruCache，分别用于实现内存缓存和硬盘缓存，其核心思想都是LRU缓存算法。

二、LruCache的使用

LruCache是Android 3.1所提供的一个缓存类，所以在Android中可以直接使用LruCache实现内存缓存。而DisLruCache目前在Android 还不是Android SDK的一部分，但Android官方文档推荐使用该算法来实现硬盘缓存。

LruCache是个泛型类，主要算法原理是把最近使用的对象用强引用（即我们平常使用的对象引用方式）存储在 LinkedHashMap 中。当缓存满时，把最近最少使用的对象从内存中移除，并提供了get和put方法来完成缓存的获取和添加操作。

LruCache的使用非常简单，我们就已图片缓存为例。

①设置LruCache缓存的大小，一般为当前进程可用容量的1/8。


②重写sizeOf方法，计算出要缓存的每张图片的大小。

注意： 缓存的总容量和每个缓存对象的大小所用单位要一致。

LruCache的核心思想很好理解，就是要维护一个缓存对象列表，其中对象列表的排列方式是按照访问顺序实现的，即一直没访问的对象，将放在队尾，即将被淘汰。而最近访问的对象将放在队头，最后被淘汰。

如下图所示：

而LinkedHashMap是由数组+双向链表的数据结构来实现的。其中双向链表的结构可以实现访问顺序和插入顺序，使得LinkedHashMap中的对按照一定顺序排列起来。

通过下面构造函数来指定LinkedHashMap中双向链表的结构是访问顺序还是插入顺序。

  2.     float loadFactor,
  3.     boolean accessOrder) {
  4.     super(initialCapacity, loadFactor);
  5.     this.accessOrder = accessOrder;
  6. }

其中accessOrder设置为true则为访问顺序，为false，则为插入顺序。

以具体例子解释：
当设置为true时

  1. public static final void main(String[] args) {
  2.     LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(0, 0.75f, true);
  3.     map.put(0, 0);
  4.     map.put(1, 1);
  5.     map.put(2, 2);
  6.     map.put(3, 3);
  7.     map.put(4, 4);
  8.     map.put(5, 5);
  9.     map.put(6, 6);
  10.     map.get(1);
  11.     map.get(2);
  13.     for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
  14.         System.out.println(entry.getKey() + ":" + entry.getValue());
  16.     }
  17. }

输出结果：

即最近访问的最后输出，那么这就正好满足的LRU缓存算法的思想。可见LruCache巧妙实现，就是利用了LinkedHashMap的这种数据结构。

下面我们在LruCache源码中具体看看，怎么应用LinkedHashMap来实现缓存的添加，获得和删除的。

从LruCache的构造函数中可以看到正是用了LinkedHashMap的访问顺序。

  1. public final V put(K key, V value) {
  2.          //不可为空，否则抛出异常
  3.     if (key == null || value == null) {
  4.         throw new NullPointerException("key == null || value == null");
  5.     }
  6.     synchronized (this) {
  7.             //插入的缓存对象值加1
  9.             //增加已有缓存的大小
  10.         size += safeSizeOf(key, value);
  11.            //向map中加入缓存对象
  12.         previous = map.put(key, value);
  13.             //如果已有缓存对象，则缓存大小恢复到之前
  14.         if (previous != null) {
  15.             size -= safeSizeOf(key, previous);
  16.         }
  17.     }
  18.         //entryRemoved()是个空方法，可以自行实现
  19.     if (previous != null) {
  20.         entryRemoved(false, key, previous, value);
  21.     }
  22.         //调整缓存大小(关键方法)
  23.     trimToSize(maxSize);
  24.     return previous;
  25. }

可以看到put()方法并没有什么难点，重要的就是在添加过缓存对象后，调用 trimToSize()方法，来判断缓存是否已满，如果满了就要删除近期最少使用的算法。

trimToSize()方法

  1. public void trimToSize(int maxSize) {
  2.     //死循环
  3.     while (true) {
  4.         K key;
  5.         V value;
  6.         synchronized (this) {
  7.             //如果map为空并且缓存size不等于0或者缓存size小于0，抛出异常
  8.             if (size < 0 || (map.isEmpty() && size != 0)) {
  9.                 throw new IllegalStateException(getClass().getName()
  10.                     + ".sizeOf() is reporting inconsistent results!");
  11.             }
  12.             //如果缓存大小size小于最大缓存，或者map为空，不需要再删除缓存对象，跳出循环
  14.             }
  15.             //迭代器获取第一个对象，即队尾的元素，近期最少访问的元素
  16.             Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
  17.             key = toEvict.getKey();
  18.             value = toEvict.getValue();
  19.             //删除该对象，并更新缓存大小
  20.             map.remove(key);
  21.             size -= safeSizeOf(key, value);
  22.             evictionCount++;
  23.         }
  24.         entryRemoved(true, key, value, null);
  25.     }
  26. }

trimToSize()方法不断地删除LinkedHashMap中队尾的元素，即近期最少访问的，直到缓存大小小于最大值。

当调用LruCache的get()方法获取集合中的缓存对象时，就代表访问了一次该元素，将会更新队列，保持整个队列是按照访问顺序排序。这个更新过程就是在LinkedHashMap中的get()方法中完成的。

先看LruCache的get()方法

get()方法

其中LinkedHashMap的get()方法如下：

  1. public V get(Object key) {
  2.     LinkedHashMapEntry<K,V> e = (LinkedHashMapEntry<K,V>)getEntry(key);
  3.     if (e == null)
  4.         return null;
  5.     //实现排序的关键方法
  6.     e.recordAccess(this);
  7.     return e.value;
  8. }

调用recordAccess()方法如下：

  1. void recordAccess(HashMap<K,V> m) {
  2.     LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
  3.     //判断是否是访问排序
  4.     if (lm.accessOrder) {
  5.         lm.modCount++;
  6.         //删除此元素
  7.         remove();
  8.         //将此元素移动到队列的头部
  9.         addBefore(lm.header);

由此可见LruCache中维护了一个集合LinkedHashMap，该LinkedHashMap是以访问顺序排序的。当调用put()方法时，就会在结合中添加元素，并调用trimToSize()判断缓存是否已满，如果满了就用LinkedHashMap的迭代器删除队尾元素，即近期最少访问的元素。当调用get()方法访问缓存对象时，就会调用LinkedHashMap的get()方法获得对应集合元素，同时会更新该元素到队头。