LRU(Least Recently Used), 即近期最少使用算法.
使用緩存策略变秦， 對網(wǎng)絡(luò)上下載的圖片等資源文件進行緩存成榜， 當再次請求同一個資源url時， 首先從緩存中查找是否存在赎婚， 當不存在時再從網(wǎng)絡(luò)上下載刘绣。采用緩存， 除了提高獲取資源的速度纬凤， 也對減少使用用戶手機上的流量有很好的作用. 核心思想是當緩存滿時，會優(yōu)先淘汰那些最少使用的緩存對象撩嚼。采用LRU算法的緩存有兩種停士，LruCache用于內(nèi)存緩存完丽， DiskLruCache用于存儲設(shè)備緩存, 它通過把對象寫入文件系統(tǒng)從而實現(xiàn)緩存的效果.
LruCache
Android3.1引入的范型類恋技，通過support-v4包可以支持低版本android設(shè)備.
public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;
...
}
它內(nèi)部采用LinkedHashMap來存儲要緩存的對象, 之所以要采用LinkedHashMap來存儲對象逻族， 我們稍后再談.
典型的使用方法是:
//獲取進程最大的內(nèi)存使用量
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并不能通過構(gòu)造方法來創(chuàng)建，它提供了一個create方法用于創(chuàng)建自身.
public static DiskLruCache create(File directory, int appVersion, int valueCount, long maxSize)
指定緩存文件的存放的目錄聘鳞，和緩存文件在設(shè)備上的最大占用空間.
獲取緩存對象和添加緩存對象薄辅， 用到了Editor的commit()方法來提交寫入操作, 用DiskLruCache.get(key)返回一個DiskLruCache.Snapshot對象抠璃， 再從snapshot對象中獲得緩存的對象. 具體的用法這里不再詳述.
LinkedHashMap
之前提到LruCache和DiskLruCache的底層實現(xiàn)都是使用LinkedHashMap赢乓，那為什么不用HashMap<K,V>而要用LinkedHashMap呢? 這是由于LinkedHashMap的特性決定的.
LinkedHashMap和HashMap的區(qū)別:
HashMap和LinkedHashMap都是實現(xiàn)Map<K, V>接口抱怔，區(qū)別在于HashMap中的對象存放是沒有特定規(guī)則的，而LinkedHashMap中的對象存放順序有特定的實現(xiàn).
public class LinkedHashMap<K, V> extends HashMap<K, V>
LinkedHashMap有兩個常用的構(gòu)造方法:
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
init();
this.accessOrder = accessOrder;
}
public LinkedHashMap() {
init();
accessOrder = false;//默認值為false
}
其中成員變量accessOrder規(guī)定了對象的存放順序彻况， 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()+" ");
}
}
輸出結(jié)果:
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);
}
}
輸出結(jié)果: 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);
}
}
輸出結(jié)果: c d a b
這就是基于訪問的順序纽甘，get一個元素后，這個元素被加到最后(使用了LRU 最近最少被使用的調(diào)度算法).
對LinkedHashMap調(diào)用get(k)和put(k,v)悍赢， 當accessOrder為true時都會在方法內(nèi)調(diào)用makeTail()把最新訪問的對象移到鏈表頭部决瞳，這樣鏈表尾部就成為了最久沒有使用的數(shù)據(jù)結(jié)點货徙。這樣當緩存空間達到最大值時皮胡，刪除鏈表的第一個元素就可以減少緩存所占用的空間了, 這就實現(xiàn)了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);
}
}
}
