LRU算法（Last Recently Used）题涨，是緩存淘汰算法的其中一種，即最近最久未使用锄贼。
在操作系統(tǒng)的內(nèi)存管理中曲稼，有一類很重要的算法就是內(nèi)存頁(yè)面置換算法（包括FIFO榴都，LRU,LFU等幾種常見頁(yè)面置換算法）待锈。
事實(shí)上，Cache算法和內(nèi)存頁(yè)面置換算法的核心思想是一樣的：都是在給定一個(gè)限定大小的空間的前提下嘴高，設(shè)計(jì)一個(gè)原則如何來(lái)更新和訪問(wèn)其中的元素炉擅。
下面說(shuō)一下LRU算法的核心思想辉懒，LRU算法的設(shè)計(jì)原則是：
如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒有被訪問(wèn)到，那么在將來(lái)它被訪問(wèn)的可能性也很小谍失。也就是說(shuō)眶俩，當(dāng)限定的空間已存滿數(shù)據(jù)時(shí)，應(yīng)當(dāng)把最久沒有被訪問(wèn)到的數(shù)據(jù)淘汰
這里提供兩種使用Java的實(shí)現(xiàn)方式
使用LinkedHashMap
具體實(shí)現(xiàn)源碼：
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int CACHE_SIZE;
/**
* 構(gòu)造器快鱼，構(gòu)造緩存的大小颠印，即最多能緩存多少參數(shù)
*
* 初始化的 initialCapacity 結(jié)果+1，是為了在cacheSize小于0.75時(shí)除的結(jié)果為0抹竹，但是這時(shí)候要有能存儲(chǔ)的元素线罕，所以+1
* accessOrder：控制訪問(wèn)順序。用于設(shè)置LinkedHashMap在調(diào)用 get() 之后的操作窃判。如果設(shè)置為true钞楼，則每次調(diào)用get后會(huì)將該元素移動(dòng)到末尾
* removeEldestEntry：默認(rèn)返回為false，在調(diào)用 afterNodeInsertion()的內(nèi)部袄琳，調(diào)用該方法询件。也就是說(shuō)，每次添加元素之后唆樊，檢查并移除最后一個(gè)元素
*
*
* @param cacheSize
*/
public LRUCache(int cacheSize) {
super((int) Math.ceil(cacheSize / 0.75)+1, 0.75F, true);
CACHE_SIZE = cacheSize;
}
/**
* 重寫removeEldestEntry
* 當(dāng)map中的數(shù)據(jù)大于指定緩存大小的時(shí)候宛琅，就刪除最老的數(shù)據(jù)
* @param eldest
* @return
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > CACHE_SIZE;
}
}
LinkedHashMap中關(guān)鍵方法的源碼：
// 添加Node之后的操作，可以看到調(diào)用了 removeEldestEntry逗旁，移除頭部元素
void afterNodeInsertion(boolean evict) { // possibly remove eldest
LinkedHashMap.Entry<K,V> first;
if (evict && (first = head) != null && removeEldestEntry(first)) {
K key = first.key;
removeNode(hash(key), key, null, false, true);
}
}
// 訪問(wèn)Node之后的操作嘿辟，可以看到，當(dāng)設(shè)置了accessOrder以后片效，訪問(wèn)元素之后红伦，會(huì)把該Node放到尾部
void afterNodeAccess(Node<K,V> e) { // move node to last
LinkedHashMap.Entry<K,V> last;
if (accessOrder && (last = tail) != e) {
LinkedHashMap.Entry<K,V> p =
(LinkedHashMap.Entry<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;
}
}
可以看到，LinkedHashMap事實(shí)上已經(jīng)提供了內(nèi)存置換的功能淀衣，我們利用了其中內(nèi)置的功能并重寫了部分方法后色建，實(shí)現(xiàn)了LRUCache。
需要注意兩點(diǎn)：
1舌缤、構(gòu)造器中調(diào)用父方法的第三個(gè)參數(shù) accessOrder（默認(rèn)為false），通過(guò)源碼注釋可以知道某残，這個(gè)表示元素的訪問(wèn)模式国撵。true為access-order，false為insertion-order
當(dāng)accessOrder=true時(shí)玻墅，用于搭配方法 removeEldestEntry(Map.Entry<K, V> eldest) 使用介牙。
2、受保護(hù)方法 removeEldestEntry(Map.Entry<K, V> eldest)澳厢，用于判斷是否移除最老一個(gè)元素环础。使得Cache可以在元素滿之后移除最老的元素囚似。
使用HashMap 編碼實(shí)現(xiàn)LRUCache
具體實(shí)現(xiàn)源碼：
public class LRUCacheCustom<K,V> {
// 雙鏈表
static class CacheNode{
CacheNode before;
CacheNode after;
Object key;
Object val;
public CacheNode(){}
}
/** 頭節(jié)點(diǎn) */
private CacheNode head;
/** 尾節(jié)點(diǎn) */
private CacheNode tail;
/** 最大元素?cái)?shù) */
private int maxCapacity;
/** 用于存儲(chǔ)節(jié)點(diǎn)數(shù)據(jù) */
private HashMap<K, CacheNode> caches;
/** 初始化 */
public LRUCacheCustom(int maxCapacity){
this.maxCapacity = maxCapacity;
caches = new HashMap<>(maxCapacity);
head = new CacheNode();
tail = new CacheNode();
head.after = tail;
tail.before = head;
}
public void put(K k, V v){
CacheNode node = caches.get(k);
if(node == null){
node = new CacheNode();
node.key = k;
}
node.val = v;
moveToFirst(node);
caches.put(k, node);
if(caches.size() > maxCapacity){
caches.remove(tail.before.key);
removeLast();
}
}
public V get(K k){
CacheNode node = caches.get(k);
if(node == null){
return null;
}
Object val = node.val;
moveToFirst(node);
return (V) val;
}
public void removeLast(){
CacheNode last = tail.before;
CacheNode secondLast = tail.before.before;
secondLast.after = tail;
tail.before = secondLast;
// 手動(dòng)釋放內(nèi)存
caches.remove(last.key);
last = null;
}
public void moveToFirst(CacheNode node){
// 先把原來(lái)node的前后連起來(lái)，如果前后不為null的話线得。（注意順序不能錯(cuò)）
CacheNode nodeBefore = node.before;
if(node.after != null){
node.after.before = nodeBefore;
}
if(nodeBefore != null ){
nodeBefore.after = node.after;
}
// 然后把node放前面
CacheNode tmp = head.after;
head.after = node;
node.before = head;
tmp.before = node;
node.after = tmp;
}
@Override
public String toString() {
return caches.toString();
}
public String getCache(){
StringBuilder bu = new StringBuilder();
CacheNode dummy = head;
while(dummy.after != null){
bu.append("{key=" + dummy.key);
bu.append(", val=" + dummy.val);
bu.append("\n -->");
dummy = dummy.after;
}
return bu.toString();
}
}
以上代碼我已經(jīng)自測(cè)通過(guò)
測(cè)試代碼：
@Test
public void lruCacheTest(){
LRUCacheCustom cacheCustom = new LRUCacheCustom(3);
cacheCustom.put(1,"AAA");
cacheCustom.put(2,"BBB");
cacheCustom.put(3,"CCC");
System.out.println(cacheCustom.getCache()); // 3 2 1
cacheCustom.put(4,"DDD");
System.out.println(cacheCustom.getCache()); // 4 3 2
// get(2) 將2提升到頂部
cacheCustom.get(2);
System.out.println(cacheCustom.getCache()); // 2 4 3
cacheCustom.put(5,"DDD");
System.out.println(cacheCustom.getCache()); // 5 2 4
}
參考：
LRU Cache
