LruCache和DiskLruCache

LRU(Least Recently Used), 即近期最少使用算法.
使用缓存策略， 对网络上下载的图片等资源文件进行缓存， 当再次请求同一个资源url时， 首先从缓存中查找是否存在， 当不存在时再从网络上下载。采用缓存， 除了提高获取资源的速度， 也对减少使用用户手机上的流量有很好的作用. 核心思想是当缓存满时，会优先淘汰那些最少使用的缓存对象。采用LRU算法的缓存有两种，LruCache用于内存缓存， DiskLruCache用于存储设备缓存, 它通过把对象写入文件系统从而实现缓存的效果.

LruCache

Android3.1引入的范型类，通过support-v4包可以支持低版本android设备.

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

它内部采用LinkedHashMap来存储要缓存的对象, 之所以要采用LinkedHashMap来存储对象， 我们稍后再谈.
典型的使用方法是:

//获取进程最大的内存使用量
LruCache<String, Bitmap> mMemoryCache;
int maxMemory = (int) (Runtime.getRuntime().maxMemory)/1024); //单位是kb
int cacheSize = maxMemory/8;
mMemoryCache = new LruCache<String, Bitmap>(cacheSize) {
    @Override
    protected int sizeOf(String key, Bitmap bitmap) {
        return bitmap*getRowBytes() * bitmap.getHeight() / 1024;
    }
}

获取一个缓存对象:

mMemoryCache.get(key);

添加一个缓存对象:

mMemoryCache.put(key, bitmap);

DiskLruCache

DiskLruCache并不能通过构造方法来创建，它提供了一个create方法用于创建自身.
public static DiskLruCache create(File directory, int appVersion, int valueCount, long maxSize)
指定缓存文件的存放的目录，和缓存文件在设备上的最大占用空间.
获取缓存对象和添加缓存对象， 用到了Editor的commit()方法来提交写入操作, 用DiskLruCache.get(key)返回一个DiskLruCache.Snapshot对象， 再从snapshot对象中获得缓存的对象. 具体的用法这里不再详述.

LinkedHashMap

之前提到LruCache和DiskLruCache的底层实现都是使用LinkedHashMap，那为什么不用HashMap<K,V>而要用LinkedHashMap呢? 这是由于LinkedHashMap的特性决定的.

LinkedHashMap和HashMap的区别:

HashMap和LinkedHashMap都是实现Map<K, V>接口，区别在于HashMap中的对象存放是没有特定规则的，而LinkedHashMap中的对象存放顺序有特定的实现.

public class LinkedHashMap<K, V> extends HashMap<K, V>
LinkedHashMap有两个常用的构造方法:
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        init();
        this.accessOrder = accessOrder;
}
public LinkedHashMap() {
        init();
        accessOrder = false;//默认值为false
}

其中成员变量accessOrder规定了对象的存放顺序， false为按插入顺序存放， true为按访问顺序存放.

/**
* True if access ordered, false if insertion ordered.
*/
private final boolean accessOrder;

看下面的例子.

public static void main(String[] args) {
    
    Map<String,String> hashmap = new HashMap<String,String>();
    Map<String,String> linkmap = new LinkedHashMap<String,String>();//accessOrder默认值为false

    for(int i=0;i<10;i++){
      hashmap.put(""+i, ""+i);
      linkmap.put(""+i, ""+i);
    }

    System.out.println("HashMap遍历输出：");
    for(Entry<String,String> entry:hashmap.entrySet()){
      System.out.print(entry.getKey()+" ");
    }

    System.out.println("LinkedHashMap遍历输出：");
    for(Entry<String,String> entry:linkmap.entrySet()){
      System.out.print(entry.getKey()+" ");
    }
}

输出结果:

HashMap遍历输出：
3 2 1 0 7 6 5 4 9 8 
LinkedHashMap遍历输出：
0 1 2 3 4 5 6 7 8 9

LinkedHashMap的accessOrder的作用

public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
        super(initialCapacity, loadFactor);
        init();
        this.accessOrder = accessOrder;
}
/**
* True if access ordered, false if insertion ordered.
*/
private final boolean accessOrder;

实例:
false： 基于插入顺序

public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,false);
        map.put("1", "a");
        map.put("2", "b");
        map.put("3", "c");
        map.put("4", "d");
        
        //访问其中的两个对象
        map.get("1");
        map.get("2");

        for (Iterator<String> iterator = map.values().iterator(); iterator
                .hasNext();) {
            String name = (String) iterator.next();
            System.out.print(name);
        }
}

输出结果: a b c d

true： 基于访问顺序

public static void main(String[] args) {
        Map<String, String> map = new LinkedHashMap<String, String>(16,0.75f,true);
        map.put("1", "a");
        map.put("2", "b");
        map.put("3", "c");
        map.put("4", "d");
        
        //访问其中的两个对象
        map.get("1");
        map.get("2");

        for (Iterator<String> iterator = map.values().iterator(); iterator
                .hasNext();) {
            String name = (String) iterator.next();
            System.out.print(name);
        }
}

输出结果: c d a b

这就是基于访问的顺序，get一个元素后，这个元素被加到最后(使用了LRU 最近最少被使用的调度算法).
对LinkedHashMap调用get(k)和put(k,v)， 当accessOrder为true时都会在方法内调用makeTail()把最新访问的对象移到链表头部，这样链表尾部就成为了最久没有使用的数据结点。这样当缓存空间达到最大值时，删除链表的第一个元素就可以减少缓存所占用的空间了, 这就实现了LRU的核心算法.

LruCache的核心 LinkedHashMap

伪代码:

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

        public LruCache(int maxSize) {
        this.maxSize = maxSize;
        this.map = new LinkedHashMap(0, 0.75F, true);
        }

    public final V get(K key) {
        Object mapValue;
        mapValue = this.map.get(key);
        return mapValue;
    }

    public final V put(K key, V value) {
        this.map.put(key, value);
        this.trimToSize(this.maxSize);
    }
    public void trimToSize(int maxSize) {
        while(true) {
            Object key;
            Object value;
            synchronized(this) {
                if(this.size <= maxSize || this.map.isEmpty()) {
                    return;
                }

                Entry toEvict = (Entry)this.map.entrySet().iterator().next(); //链表中最尾部的对象
                key = toEvict.getKey();
                value = toEvict.getValue();
                this.map.remove(key);//删除尾部对象
                this.size -= this.safeSizeOf(key, value);
            }
            this.entryRemoved(true, key, value, (Object)null);
        }
    }
}