編輯：關於Android編程
/*
* 初始化LinkedHashMap
* 第一個參數：initialCapacity，初始大小
* 第二個參數：loadFactor，負載因子=0.75f
* 第三個參數：accessOrder=true，基於訪問順序；accessOrder=false，基於插入順序
*/
public LinkedHashMap(int initialCapacity, float loadFactor, boolean accessOrder) {
super(initialCapacity, loadFactor);
init();
this.accessOrder = accessOrder;
}
顯然，在LruCache中選擇的是accessOrder = true；此時，當accessOrder 設置為 true時，每當我們更新（即調用put方法）或訪問（即調用get方法）map中的結點時，LinkedHashMap內部都會將這個結點移動到鏈表的尾部，因此，在鏈表的尾部是最近剛剛使用的結點，在鏈表的頭部是是最近最少使用的結點，當我們的緩存空間不足時，就應該持續把鏈表頭部結點移除掉，直到有剩余空間放置新結點。
可以看到，LinkedHashMap完成了LruCache中的核心功能，那LruCache中剩下要做的就是定義緩存空間總容量，當前保存數據已使用的容量，對外提供put、get方法。
//核心數據結構
private final LinkedHashMap map;
// 當前緩存數據所占的大小
private int size;
//緩存空間總容量
private int maxSize;
要注意的是size字段，因為map中可以存放各種類型的數據，這些數據的大小測量方式也是不一樣的，比如Bitmap類型的數據和String類型的數據計算他們的大小方式肯定不同，因此，LruCache中在計算放入數據大小的方法sizeOf中，只是簡單的返回了1，需要我們重寫這個方法，自己去定義數據的測量方式。因此，我們在使用LruCache的時候，經常會看到這種方式：
private static final int CACHE_SIZE = 4 * 1024 * 1024;//4Mib
LruCache bitmapCache = new LruCache(CACHE_SIZE){
@Override
protected int sizeOf(String key, Bitmap value) {
return value.getByteCount();//自定義Bitmap數據大小的計算方式
}
};
（2）構造方法
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
this.map = new LinkedHashMap(0, 0.75f, true);
}
LruCache只有一個唯一的構造方法，在構造方法中，給定了緩存空間的總大小，初始化了LinkedHashMap核心數據結構，在LinkedHashMap中的第三個參數指定為true，也就設置了accessOrder=true，表示這個LinkedHashMap將是基於數據的訪問順序進行排序。
（3）sizeOf()和safeSizeOf()方法
根據上面的解釋，由於各種數據類型大小測量的標准不統一，具體測量的方法應該由使用者來實現，如上面給出的一個在實現LruCache時重寫sizeOf的一種常用實現方式。通過多態的性質，再具體調用sizeOf時會調用我們重寫的方法進行測量，LruCache對sizeOf()的調用進行一層封裝，如下：
private int safeSizeOf(K key, V value) {
int result = sizeOf(key, value);
if (result < 0) {
throw new IllegalStateException("Negative size: " + key + "=" + value);
}
return result;
}
裡面其實就是調用sizeOf()方法，返回sizeOf計算的大小。
上面就是LruCache的基本內容，下面就需要提供LruCache的核心功能了。
（4）put方法緩存數據
首先看一下它的源碼實現：
/**
* 給對應key緩存value，並且將該value移動到鏈表的尾部。
*/
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
synchronized (this) {
// 記錄 put 的次數
putCount++;
// 通過鍵值對，計算出要保存對象value的大小，並更新當前緩存大小
size += safeSizeOf(key, value);
/*
* 如果 之前存在key，用新的value覆蓋原來的數據， 並返回 之前key 的value
* 記錄在 previous
*/
previous = map.put(key, value);
// 如果之前存在key，並且之前的value不為null
if (previous != null) {
// 計算出 之前value的大小，因為前面size已經加上了新的value數據的大小，此時，需要再次更新size，減去原來value的大小
size -= safeSizeOf(key, previous);
}
}
// 如果之前存在key，並且之前的value不為null
if (previous != null) {
/*
* previous值被剔除了，此次添加的 value 已經作為key的 新值
* 告訴 自定義 的 entryRemoved 方法
*/
entryRemoved(false, key, previous, value);
}
//裁剪緩存容量（在當前緩存數據大小超過了總容量maxSize時，才會真正去執行LRU）
trimToSize(maxSize);
return previous;
}
可以看到，put()方法主要有以下幾步：
1）key和value判空，說明LruCache中不允許key和value為null；
2）通過safeSizeOf()獲取要加入對象數據的大小，並更新當前緩存數據的大小；
3）將新的對象數據放入到緩存中，即調用LinkedHashMap的put方法，如果原來存在該key時，直接替換掉原來的value值，並返回之前的value值，得到之前value的大小，更新當前緩存數據的size大小；如果原來不存在該key，則直接加入緩存即可；
4）清理緩存空間，如下；
（5）trimToSize()清理緩存空間
當我們加入一個數據時（put），為了保證當前數據的緩存所占大小沒有超過我們指定的總大小，通過調用trimToSize()來對緩存空間進行管理控制。如下：
public void trimToSize(int maxSize) {
/*
* 循環進行LRU，直到當前所占容量大小沒有超過指定的總容量大小
*/
while (true) {
K key;
V value;
synchronized (this) {
// 一些異常情況的處理
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(
getClass().getName() + ".sizeOf() is reporting inconsistent results!");
}
// 首先判斷當前緩存數據大小是否超過了指定的緩存空間總大小。如果沒有超過，即緩存中還可以存入數據，直接跳出循環，清理完畢
if (size <= maxSize || map.isEmpty()) {
break;
}
/**
* 執行到這，表示當前緩存數據已超過了總容量，需要執行LRU，即將最近最少使用的數據清除掉，直到數據所占緩存空間沒有超標;
* 根據前面的原理分析，知道，在鏈表中，鏈表的頭結點是最近最少使用的數據，因此，最先清除掉鏈表前面的結點
*/
Map.Entry toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
map.remove(key);
// 移除掉後，更新當前數據緩存的大小
size -= safeSizeOf(key, value);
// 更新移除的結點數量
evictionCount++;
}
/*
* 通知某個結點被移除，類似於回調
*/
entryRemoved(true, key, value, null);
}
}
trimToSize()方法的作用就是為了保證當前數據的緩存大小不能超過我們指定的緩存總大小，如果超過了，就會開始移除最近最少使用的數據，直到size符合要求。trimToSize()方法在put()的時候一定會調用，在get()的時候有可能會調用。
（6）get方法獲取緩存數據
get方法源碼如下：
/**
* 根據key查詢緩存，如果該key對應的value存在於緩存，直接返回value；
* 訪問到這個結點時，LinkHashMap會將它移動到雙向循環鏈表的的尾部。
* 如果如果沒有緩存的值，則返回null。（如果開發者重寫了create()的話，返回創建的value）
*/
public final V get(K key) {
if (key == null) {
throw new NullPointerException("key == null");
}
V mapValue;
synchronized (this) {
// LinkHashMap 如果設置按照訪問順序的話，這裡每次get都會重整數據順序
mapValue = map.get(key);
// 計算 命中次數
if (mapValue != null) {
hitCount++;
return mapValue;
}
// 計算 丟失次數
missCount++;
}
/*
* 官方解釋：
* 嘗試創建一個值，這可能需要很長時間，並且Map可能在create()返回的值時有所不同。如果在create()執行的時
* 候，用這個key執行了put方法，那麼此時就發生了沖突，我們在Map中刪除這個創建的值，釋放被創建的值，保留put進去的值。
*/
V createdValue = create(key);
if (createdValue == null) {
return null;
}
/***************************
* 不覆寫create方法走不到下面 *
***************************/
/*
* 正常情況走不到這裡
* 走到這裡的話 說明 實現了自定義的 create(K key) 邏輯
* 因為默認的 create(K key) 邏輯為null
*/
synchronized (this) {
// 記錄 create 的次數
createCount++;
// 將自定義create創建的值，放入LinkedHashMap中，如果key已經存在，會返回 之前相同key 的值
mapValue = map.put(key, createdValue);
// 如果之前存在相同key的value，即有沖突。
if (mapValue != null) {
/*
* 有沖突
* 所以 撤銷 剛才的 操作
* 將 之前相同key 的值 重新放回去
*/
map.put(key, mapValue);
} else {
// 拿到鍵值對，計算出在容量中的相對長度，然後加上
size += safeSizeOf(key, createdValue);
}
}
// 如果上面 判斷出了 將要放入的值發生沖突
if (mapValue != null) {
/*
* 剛才create的值被刪除了，原來的 之前相同key 的值被重新添加回去了
* 告訴 自定義 的 entryRemoved 方法
*/
entryRemoved(false, key, createdValue, mapValue);
return mapValue;
} else {
// 上面 進行了 size += 操作 所以這裡要重整長度
trimToSize(maxSize);
return createdValue;
}
}
get()方法的思路就是：
1）先嘗試從map緩存中獲取value，即mapVaule = map.get(key);如果mapVaule != null，說明緩存中存在該對象，直接返回即可；
2）如果mapVaule == null，說明緩存中不存在該對象，大多數情況下會直接返回null；但是如果我們重寫了create()方法，在緩存沒有該數據的時候自己去創建一個，則會繼續往下走，中間可能會出現沖突，看注釋；
3）注意：在我們通過LinkedHashMap進行get(key)或put(key,value)時都會對鏈表進行調整，即將剛剛訪問get或加入put的結點放入到鏈表尾部。
（7）entryRemoved()
entryRemoved的源碼如下：
/**
* 1.當被回收或者刪掉時調用。該方法當value被回收釋放存儲空間時被remove調用
* 或者替換條目值時put調用，默認實現什麼都沒做。
* 2.該方法沒用同步調用，如果其他線程訪問緩存時，該方法也會執行。
* 3.evicted=true：如果該條目被刪除空間 （表示 進行了trimToSize or remove） evicted=false：put沖突後 或 get裡成功create後
* 導致
* 4.newValue!=null，那麼則被put()或get()調用。
*/
protected void entryRemoved(boolean evicted, K key, V oldValue, V newValue) {
}
可以發現entryRemoved方法是一個空方法，說明這個也是讓開發者自己根據需求去重寫的。entryRemoved()主要作用就是在結點數據value需要被刪除或回收的時候，給開發者的回調。開發者就可以在這個方法裡面實現一些自己的邏輯：
（1）可以進行資源的回收；
（2）可以實現二級內存緩存，可以進一步提高性能，思路如下：重寫LruCache的entryRemoved()函數，把刪除掉的item，再次存入另外一個LinkedHashMapLruCache 自身並沒有釋放內存，只是 LinkedHashMap中將數據移除了，如果數據還在別的地方被引用了，還是有洩漏問題，還需要手動釋放內存；
覆寫entryRemoved方法能知道 LruCache 數據移除是是否發生了沖突（沖突是指在map.put()的時候，對應的key中是否存在原來的值），也可以去手動釋放資源；
可以看到，緩存目錄中有一堆文件名很長的文件，這些文件就是我們緩存的一張張圖片數據，在最後有一個文件名journal的文件，這個journal文件是DiskLruCache的一個日志文件，即保存著每張緩存圖片的操作記錄，journal文件正是實現DiskLruCache的核心。看到出現了journal文件，基本可以說明這個APP使用了DiskLruCache緩存策略。
根據對LruCache的分析，要實現LRU，最重要的是要有一種數據結構能夠基於訪問順序來保存緩存中的對象，LinkedHashMap是一種非常合適的數據結構，為此，DiskLruCache也選擇了LinkedHashMap作為維護訪問順序的數據結構，但是，對於DiskLruCache來說，單單LinkedHashMap是不夠的，因為我們不能像LruCache一樣，直接將數據放置到LinkedHashMap的value中，也就是處於內存當中，在DiskLruCache中，數據是緩存到了本地文件，這裡的LinkedHashMap中的value只是保存的是value的一些簡要信息Entry，如唯一的文件名稱、大小、是否可讀等信息，如：
private final class Entry {
private final String key;
/** Lengths of this entry's files. */
private final long[] lengths;
/** True if this entry has ever been published */
private boolean readable;
/** The ongoing edit or null if this entry is not being edited. */
private Editor currentEditor;
/** The sequence number of the most recently committed edit to this entry. */
private long sequenceNumber;
private Entry(String key) {
this.key = key;
this.lengths = new long[valueCount];
}
public String getLengths() throws IOException {
StringBuilder result = new StringBuilder();
for (long size : lengths) {
result.append(' ').append(size);
}
return result.toString();
}
/**
* Set lengths using decimal numbers like "10123".
*/
private void setLengths(String[] strings) throws IOException {
if (strings.length != valueCount) {
throw invalidLengths(strings);
}
try {
for (int i = 0; i < strings.length; i++) {
lengths[i] = Long.parseLong(strings[i]);
}
} catch (NumberFormatException e) {
throw invalidLengths(strings);
}
}
private IOException invalidLengths(String[] strings) throws IOException {
throw new IOException("unexpected journal line: " + Arrays.toString(strings));
}
public File getCleanFile(int i) {
return new File(directory, key + "." + i);
}
public File getDirtyFile(int i) {
return new File(directory, key + "." + i + ".tmp");
}
}
DiskLruCache中對於LinkedHashMap定義如下：
