LRU Cache
1. 概念解析睛竣，LRU Cache算法
- Lru Cache算法就是Least Recently Used笨腥，按照字面意思就是最近最少使用，用這種算法來(lái)實(shí)現(xiàn)緩存就比較合適了介袜，當(dāng)緩存滿了的時(shí)候蛮粮，不經(jīng)常使用的就直接刪除，挪出空間來(lái)緩存新的對(duì)象颤诀；
- 實(shí)現(xiàn)緩存的最關(guān)鍵的操作就是字旭，添加和讀取以及刪除等操作了
- LRU 實(shí)現(xiàn)使用LinkedHashMap永久的緩存數(shù)據(jù)对湃，那為什么要用這個(gè)呢？
- LinkedHashMap是雙向列表實(shí)現(xiàn)的遗淳，剛好在內(nèi)部具有排序的功能拍柒，內(nèi)部的accessorder代表了兩種模式，插入模式和訪問(wèn)模式屈暗，false為訪問(wèn)模式按照順序來(lái)實(shí)現(xiàn)（默認(rèn)就是false）拆讯，所以按照此種思路，則鏈表的最后段就是最少使用的緩存养叛，比較方便來(lái)實(shí)現(xiàn)种呐；
- LinkedHashMap是雙向循環(huán)列表來(lái)實(shí)現(xiàn)，默認(rèn)容量大小16弃甥、負(fù)載因子0.75以及按照插入順序排序爽室，不用我們管理擴(kuò)容等問(wèn)題；
- 添加和讀取數(shù)據(jù)：保證訪問(wèn)順序排序淆攻，會(huì)將數(shù)據(jù)插入或者移動(dòng)到鏈表的尾部阔墩，而且鏈表的刪除和增加速度比較快；
- LinkedHashMap遍歷順序是從頭到尾卜录，這樣可以保證刪除最老的數(shù)據(jù)戈擒；
2. LRU cache的簡(jiǎn)單使用
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;
}
};
- 獲取到當(dāng)前虛擬機(jī)的最大內(nèi)存值眶明，然后取1/8來(lái)當(dāng)緩存艰毒；
- 注意單位的一致性sizeof（）和cacheSize的單位要一直，上面為kb搜囱；
- sizeOf()是為了計(jì)算緩存對(duì)象大小的計(jì)算丑瞧；
- 使用的時(shí)候你就可以當(dāng)做一個(gè)map去使用就好了，只不過(guò)自動(dòng)添加了擴(kuò)容蜀肘，緩存绊汹，以及幫你防止OOM的情況；
3. LRU Cache源碼解析
分析源碼主要從幾個(gè)方面來(lái)分析扮宠，創(chuàng)建西乖，存取，刪除這三個(gè)方面來(lái)：
-
創(chuàng)建：
public class LruCache<K, V> { private final LinkedHashMap<K, V> map; /** Size of this cache in units. Not necessarily the number of elements. */ private int size; private int maxSize; private int putCount; private int createCount; private int evictionCount; private int hitCount; private int missCount; 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); } }構(gòu)建特別簡(jiǎn)單坛增，相當(dāng)于創(chuàng)建了一個(gè)LinkedHashMap获雕；
-
put方法是把內(nèi)容放入到緩存中去
//給對(duì)應(yīng)key緩存value，該value將被移動(dòng)到隊(duì)頭收捣。 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,記錄 put 的次數(shù) putCount++; //增加已有緩存的大小,拿到鍵值對(duì)，計(jì)算出在容量中的相對(duì)長(zhǎng)度罢艾，然后加上 size += safeSizeOf(key, value); //向map中加入緩存對(duì)象,如果 之前存在key 則返回 之前key 的value,記錄在 previous previous = map.put(key, value); //如果已有緩存對(duì)象楣颠，則緩存大小恢復(fù)到之前 if (previous != null) { // // 計(jì)算出 沖突鍵值 在容量中的相對(duì)長(zhǎng)度尽纽，然后減去 size -= safeSizeOf(key, previous); } } //entryRemoved()是個(gè)空方法，可以自行實(shí)現(xiàn),如果上面發(fā)生沖突 if (previous != null) { //previous值被剔除了童漩，此次添加的 value 已經(jīng)作為key的 新值,告訴 自定義 的 entryRemoved 方法 entryRemoved(false, key, previous, value); } //調(diào)整緩存大小 trimToSize(maxSize); return previous; } /* * 這是一個(gè)死循環(huán)弄贿， * 1.只有 擴(kuò)容 的情況下能立即跳出 * 2.非擴(kuò)容的情況下，map的數(shù)據(jù)會(huì)一個(gè)一個(gè)刪除矫膨，直到map里沒(méi)有值了挎春，就會(huì)跳出 */ public void trimToSize(int maxSize) { while (true) { K key; V value; synchronized (this) { // 在重新調(diào)整容量大小前，本身容量就為空的話豆拨，會(huì)出異常的直奋。 //如果map為空并且緩存size不等于0或者緩存size小于0，拋出異常 if (size < 0 || (map.isEmpty() && size != 0)) { throw new IllegalStateException(getClass().getName() + ".sizeOf() is reporting inconsistent results!"); } // 如果是 擴(kuò)容 或者 map為空了施禾，就會(huì)中斷脚线，因?yàn)閿U(kuò)容不會(huì)涉及到丟棄數(shù)據(jù)的情況 //如果緩存大小size小于最大緩存，或者map為空弥搞，不需要再刪除緩存對(duì)象邮绿，跳出循環(huán) if (size <= maxSize || map.isEmpty()) { break; } //迭代器獲取第一個(gè)對(duì)象，即隊(duì)尾的元素攀例，近期最少訪問(wèn)的元素 Map.Entry<K, V> toEvict = map.entrySet().iterator().next(); key = toEvict.getKey(); value = toEvict.getValue(); //刪除該對(duì)象船逮，并更新緩存大小 map.remove(key); // 拿到鍵值對(duì)，計(jì)算出在容量中的相對(duì)長(zhǎng)度粤铭，然后減去挖胃。 size -= safeSizeOf(key, value); evictionCount++; } //將最后一次刪除的最少訪問(wèn)數(shù)據(jù)回調(diào)出去 entryRemoved(true, key, value, null); } }put方法比較簡(jiǎn)單只是把對(duì)象存儲(chǔ)，然后關(guān)鍵的方法是trimToSize()梆惯，調(diào)整緩存的酱鸭，如果滿了就刪除然后更新
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ì)列頭部的功能,LinkHashMap 如果設(shè)置按照訪問(wèn)順序的話，這里每次get都會(huì)重整數(shù)據(jù)順序
mapValue = map.get(key);
if (mapValue != null) {
hitCount++;
return mapValue;
}
missCount++;
}
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
//判斷是否是訪問(wèn)排序
if (lm.accessOrder) {
lm.modCount++;
//刪除此元素
remove();
//將此元素移動(dòng)到隊(duì)列的頭部
addBefore(lm.header);
}
}
- 總結(jié)：
- LRUcache的源碼相對(duì)簡(jiǎn)單垛吗，只要理解LinkedHashMap的原理凹髓，這個(gè)是非常簡(jiǎn)單的實(shí)現(xiàn)；關(guān)鍵代碼是trimSize方法怯屉，每次添加完成之后調(diào)整緩存大小蔚舀，get方法的也是調(diào)用的LinkedHashMap的get然后通過(guò)recordAcess來(lái)調(diào)整順序；
