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