一、什么是緩存
這里說的緩存是一種廣義的概念耍属，在計算機存儲層次結(jié)構(gòu)中矾兜，低一層的存儲器都可以看做是高一層的緩存损趋。比如Cache是內(nèi)存的緩存，內(nèi)存是硬盤的緩存椅寺，硬盤是網(wǎng)絡(luò)的緩存等等浑槽。
緩存可以有效地解決存儲器性能與容量的這對矛盾，但絕非看上去那么簡單返帕。如果緩存算法設(shè)計不當(dāng)桐玻，非但不能提高訪問速度，反而會使系統(tǒng)變得更慢荆萤。
從本質(zhì)上來說镊靴，緩存之所以有效是因為程序和數(shù)據(jù)的局部性（locality）。程序會按固定的順序執(zhí)行链韭，數(shù)據(jù)會存放在連續(xù)的內(nèi)存空間并反復(fù)讀寫偏竟。這些特點使得我們可以緩存那些經(jīng)常用到的數(shù)據(jù)，從而提高讀寫速度敞峭。
緩存的大小是固定的踊谋，它應(yīng)該只保存最常被訪問的那些數(shù)據(jù)。然而未來不可預(yù)知旋讹，我們只能從過去的訪問序列做預(yù)測殖蚕，于是就有了各種各樣的緩存替換策略。本文介紹一種簡單的緩存策略骗村，稱為最近最少使用（LRU嫌褪，Least Recently Used）算法呀枢。
二胚股、LRU的實現(xiàn)
我們以內(nèi)存訪問為例解釋緩存的工作原理。假設(shè)緩存的大小固定裙秋，初始狀態(tài)為空琅拌。每發(fā)生一次讀內(nèi)存操作，首先查找待讀取的數(shù)據(jù)是否存在于緩存中摘刑，若是进宝，則緩存命中，返回數(shù)據(jù)枷恕；若否党晋，則緩存未命中，從內(nèi)存中讀取數(shù)據(jù)，并把該數(shù)據(jù)添加到緩存中未玻。向緩存添加數(shù)據(jù)時灾而，如果緩存已滿，則需要刪除訪問時間最早的那條數(shù)據(jù)扳剿，這種更新緩存的方法就叫做LRU旁趟。
實現(xiàn)LRU時，我們需要關(guān)注它的讀性能和寫性能庇绽，理想的LRU應(yīng)該可以在O(1)的時間內(nèi)讀取一條數(shù)據(jù)或更新一條數(shù)據(jù)锡搜，也就是說讀寫的時間復(fù)雜度都是O(1)。
此時很容易想到使用HashMap瞧掺，根據(jù)數(shù)據(jù)的鍵訪問數(shù)據(jù)可以達到O(1)的速度耕餐。但是更新緩存的速度卻無法達到O(1)，因為需要確定哪一條數(shù)據(jù)的訪問時間最早夸盟，這需要遍歷所有緩存才能找到蛾方。
因此，我們需要一種既按訪問時間排序上陕，又能在常數(shù)時間內(nèi)隨機訪問的數(shù)據(jù)結(jié)構(gòu)桩砰。
這可以通過HashMap+雙向鏈表實現(xiàn)。HashMap保證通過key訪問數(shù)據(jù)的時間為O(1)释簿，雙向鏈表則按照訪問時間的順序依次穿過每個數(shù)據(jù)亚隅。之所以選擇雙向鏈表而不是單鏈表，是為了可以從中間任意結(jié)點修改鏈表結(jié)構(gòu)庶溶，而不必從頭結(jié)點開始遍歷煮纵。
如下圖所示，黑色部分為HashMap的結(jié)構(gòu)偏螺，紅色箭頭則是雙向鏈表的正向連接（逆向連接未畫出）行疏。可以清晰地看到套像，數(shù)據(jù)的訪問順序是1->3->5->6->10酿联。我們只需要在每次訪問過后改變鏈表的連接順序即可。
實現(xiàn)代碼如下：
/**
* @author wjg
*
* LRU（Least Recently Used）緩存算法
* 使用HashMap+雙向鏈表夺巩，使get和put的時間復(fù)雜度達到O(1)贞让。
* 讀緩存時從HashMap中查找key，更新緩存時同時更新HashMap和雙向鏈表柳譬，雙向鏈表始終按照訪問順序排列喳张。
*
*/
public class LRUCache {
/**
* @param args
* 測試程序，訪問順序為[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]美澳，其中成對的數(shù)調(diào)用put销部，單個數(shù)調(diào)用get摸航。
* get的結(jié)果為[1],[-1],[-1],[3],[4]，-1表示緩存未命中舅桩，其它數(shù)字表示命中忙厌。
*/
public static void main(String[] args) {
LRUCache cache = new LRUCache(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1));
cache.put(3, 3);
System.out.println(cache.get(2));
cache.put(4, 4);
System.out.println(cache.get(1));
System.out.println(cache.get(3));
System.out.println(cache.get(4));
}
// 緩存容量
private final int capacity;
// 用于加速緩存項隨機訪問性能的HashMap
private HashMap<Integer, Entry> map;
// 雙向鏈表頭結(jié)點，該側(cè)的緩存項訪問時間較早
private Entry head;
// 雙向鏈表尾結(jié)點江咳，該側(cè)的緩存項訪問時間較新
private Entry tail;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<Integer, Entry>((int)(capacity / 0.75 + 1), 0.75f);
head = new Entry(0, 0);
tail = new Entry(0, 0);
head.next = tail;
tail.prev = head;
}
/**
* 從緩存中獲取key對應(yīng)的值逢净，若未命中則返回-1
* @param key 鍵
* @return key對應(yīng)的值，若未命中則返回-1
*/
public int get(int key) {
if (map.containsKey(key)) {
Entry entry = map.get(key);
popToTail(entry);
return entry.value;
}
return -1;
}
/**
* 向緩存中插入或更新值
* @param key 待更新的鍵
* @param value 待更新的值
*/
public void put(int key, int value) {
if (map.containsKey(key)) {
Entry entry = map.get(key);
entry.value = value;
popToTail(entry);
}
else {
Entry newEntry = new Entry(key, value);
if (map.size() >= capacity) {
Entry first = removeFirst();
map.remove(first.key);
}
addToTail(newEntry);
map.put(key, newEntry);
}
}
/**
* 緩存項的包裝類歼指，包含鍵爹土、值、前驅(qū)結(jié)點踩身、后繼結(jié)點
* @author wjg
*
*/
class Entry {
int key;
int value;
Entry prev;
Entry next;
Entry(int key, int value) {
this.key = key;
this.value = value;
}
}
// 將entry結(jié)點移動到鏈表末端
private void popToTail(Entry entry) {
Entry prev = entry.prev;
Entry next = entry.next;
prev.next = next;
next.prev = prev;
Entry last = tail.prev;
last.next = entry;
tail.prev = entry;
entry.prev = last;
entry.next = tail;
}
// 移除鏈表首端的結(jié)點
private Entry removeFirst() {
Entry first = head.next;
Entry second = first.next;
head.next = second;
second.prev = head;
return first;
}
// 添加entry結(jié)點到鏈表末端
private void addToTail(Entry entry) {
Entry last = tail.prev;
last.next = entry;
tail.prev = entry;
entry.prev = last;
entry.next = tail;
}
}
每個方法和成員變量前都有中文注釋胀茵，不必過多解釋。
值得一提的是挟阻，Java API中其實已經(jīng)有數(shù)據(jù)類型提供了我們需要的功能琼娘，就是LinkedHashMap這個類。該類內(nèi)部也是采用HashMap+雙向鏈表實現(xiàn)的附鸽。使用這個類實現(xiàn)LRU就簡練多了脱拼。
/**
*
* 一個更簡單實用的LRUCache方案，使用LinkedHashMap即可實現(xiàn)坷备。
* LinkedHashMap提供了按照訪問順序排序的方案熄浓，內(nèi)部也是使用HashMap+雙向鏈表。
* 只需要重寫removeEldestEntry方法省撑，當(dāng)該方法返回true時赌蔑，LinkedHashMap會刪除最舊的結(jié)點。
*
* @author wjg
*
*/
public class LRUCacheSimple {
/**
* @param args
*/
public static void main(String[] args) {
LRUCacheSimple cache = new LRUCacheSimple(2);
cache.put(1, 1);
cache.put(2, 2);
System.out.println(cache.get(1));
cache.put(3, 3);
System.out.println(cache.get(2));
cache.put(4, 4);
System.out.println(cache.get(1));
System.out.println(cache.get(3));
System.out.println(cache.get(4));
}
private LinkedHashMap<Integer, Integer> map;
private final int capacity;
public LRUCacheSimple(int capacity) {
this.capacity = capacity;
map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > capacity;
}
};
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void put(int key, int value) {
map.put(key, value);
}
}
只需要覆寫LinkedHashMap的removeEldestEntry方法竟秫，在緩存已滿的情況下返回true娃惯，內(nèi)部就會自動刪除最老的元素。
感興趣的同學(xué)可以做一下LeetCode 146. LRU Cache這道題肥败，嘗試一下如何實現(xiàn)這個算法趾浅。
完整版代碼LRUCache.java收錄在GitHub倉庫Algorithms中，歡迎大家下載試用拙吉。
參考資料
Cache replacement policies WikiPedia
146. LRU Cache LeetCode
Laziest implementation: Java's LinkedHashMap takes care of everything sky-xu
