LrcCache是Android3.1所提供的一個(gè)緩存類。LruCache類是泛型類朴摊,主要算法原理是把最近使用的對(duì)象強(qiáng)引用(即我們平常使用的對(duì)象引用方式)存儲(chǔ)在LinkedHashMap中。當(dāng)緩存滿時(shí)此虑,把最近最少使用的對(duì)象從內(nèi)存中移除甚纲,并提供了get和put方法來(lái)完成緩存的獲取和添加操作。
1朦前、LruCache的使用
lruCache的使用非常簡(jiǎn)單介杆,以圖片緩存為例
private LruCache mMemoryCache = null;
private void lrcCaheceInit() {
int maxMemory = (int) (Runtime.getRuntime().totalMemory() / 1024);
int cacheSize = maxMemory / 8;
mMemoryCache = new LruCache<String, Bitmap>(cacheSize) {
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getRowBytes() * value.getHeight() / 1024;
}
};
}
- 設(shè)置LruCache緩存的大小鹃操,一般為當(dāng)前進(jìn)程可用容量的1/8.
- 重寫(xiě)sizeOf方法,計(jì)算出要緩存的每張圖片的大小春哨。
注意:緩存的總量和每個(gè)緩存對(duì)象的大小所用單位要一致荆隘。
2、LruCache實(shí)現(xiàn)的原理
維護(hù)一個(gè)緩存對(duì)象的列表赴背,其中對(duì)象列表的排序方式是按照訪問(wèn)的順序?qū)崿F(xiàn)的椰拒,即一直沒(méi)有訪問(wèn)的對(duì)象,就放在隊(duì)尾凰荚,即將被淘汰燃观。而最近訪問(wèn)的對(duì)象放在隊(duì)頭,最后被淘汰便瑟。淘汰過(guò)程圖:
該隊(duì)列便是由linkedHashMap來(lái)維護(hù)缆毁。而LinkedHashMap則是由數(shù)組+雙向鏈表的數(shù)據(jù)結(jié)構(gòu)來(lái)實(shí)現(xiàn)的。其中雙向鏈表的結(jié)構(gòu)可以實(shí)現(xiàn)訪問(wèn)順序和插入順序胳徽,使得LinkedHashMap中的鍵值對(duì)积锅,按照一定的順序排列起來(lái)。
通過(guò)下面構(gòu)造函數(shù)來(lái)指定LinkedHashMap中的結(jié)構(gòu)是訪問(wèn)順序還是插入順序养盗。
public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {
super(initialCapacity, loadFactor);
this.accessOrder = accessOrder;
}
其中accessOrder設(shè)置為true則為訪問(wèn)順序,false則為插入順序适篙。
具體例子解釋往核,當(dāng)設(shè)置為true時(shí):
LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(0,
0.75f, true);
map.put(0, 0);
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);
map.put(6, 6);
map.get(1);
map.get(2);
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}
輸出結(jié)果:
0:0
3:3
4:4
5:5
6:6
1:1
2:2
即最近訪問(wèn)的的最后輸出,那么這就正好滿足LRU緩存算法的思想嚷节。
在LruCache源碼中聂儒,怎么應(yīng)用LinkedHashMap來(lái)實(shí)現(xiàn)緩存的添加,獲得和刪除的硫痰。
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
從LruCache的構(gòu)造函數(shù)中可以看到是用了LinkedHashMap的訪問(wèn)順序衩婚。
put方法():
public final V put(K key, V value) {
//為空就拋出異常
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
//插入的緩存對(duì)象加1
putCount++;
//增加已有的緩存大小
size += safeSizeOf(key, value);
//在map中加入緩存對(duì)象
previous = map.put(key, value);
//如果已有緩存對(duì)象,則緩存大小回復(fù)之前的大小
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
//空方法效斑,自行實(shí)現(xiàn)
if (previous != null) {
entryRemoved(false, key, previous, value);
}
//調(diào)整緩存大小的關(guān)鍵方法
trimToSize(maxSize);
return previous;
}
put方法中非春,主要的就是添加緩存對(duì)象后,調(diào)用trimSize()方法缓屠,來(lái)判斷是否緩存已滿奇昙,如果滿了就要?jiǎng)h除近期最少使用的算法。
private void trimToSize(int maxSize) {
while (true) {
K key;
V value;
synchronized (this) {
//如果map為空并且緩存size不等于0或者緩存size小于0敌完,則拋出異常
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
//如果緩存大小小于最大緩存储耐,跳出緩存
if (size <= maxSize) {
break;
}
//遍歷map集合,取隊(duì)尾的元素滨溉,近期訪問(wèn)最少的元素
Map.Entry<K, V> toEvict = null;
for (Map.Entry<K, V> entry : map.entrySet()) {
toEvict = entry;
}
if (toEvict == null) {
break;
}
key = toEvict.getKey();
value = toEvict.getValue();
//刪除該對(duì)象什湘,并更新緩存大小
map.remove(key);
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
trimToSize()方法不停地刪除LinkedHashMap中隊(duì)尾的元素长赞,即近期最少訪問(wèn)的,知道緩存大小小于最大值闽撤。
當(dāng)調(diào)用LruCache的get()方法獲取緩存中的對(duì)象時(shí)涧卵,就代表了一次該元素,將會(huì)更新隊(duì)列腹尖,保持整個(gè)隊(duì)列是按照訪問(wèn)順序排序柳恐。這個(gè)更新過(guò)程就是在LinkedHashMap中的get()方法中完成的。
get()方法:
public final V get(K key) {
//key為空拋出異常
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
//獲取對(duì)應(yīng)的緩存對(duì)象
//get()方法會(huì)實(shí)現(xiàn)將訪問(wèn)的元素更新到隊(duì)列頭部的功能热幔。
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
其中LinkedHashMap的get()方法如下:
public V get(Object key) {
Node<K,V> e;
if ((e = getNode(hash(key), key)) == null)
return null;
if (accessOrder)
//實(shí)現(xiàn)排序的方法
afterNodeAccess(e);
return e.value;
}
afterNodeAccess()方法
void afterNodeAccess(Node<K,V> e) { // 將節(jié)點(diǎn)挪到隊(duì)尾
LinkedHashMapEntry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMapEntry<K,V> p =
(LinkedHashMapEntry<K,V>)e, b = p.before, a = p.after;
p.after = null;
if (b == null)
head = a;
else
b.after = a;
if (a != null)
a.before = b;
else
last = b;
if (last == null)
head = p;
else {
p.before = last;
last.after = p;
}
tail = p;
++modCount;
}
}
由此乐设,LruCache中維護(hù)了一個(gè)集合LinkedHashMap,該LinkedHashMap是以順序排序的绎巨。當(dāng)調(diào)用put()方法時(shí)近尚,就會(huì)在集合中添加元素,并調(diào)用trimToSize()判斷緩存是否已滿场勤。如果滿了就刪除最后的元素戈锻。當(dāng)調(diào)用get()方法訪問(wèn)緩存的對(duì)象時(shí),就調(diào)用LinkedHashMap的get()方法獲得對(duì)應(yīng)集合元素和媳。同時(shí)更新該元素到隊(duì)頭格遭。