LRU算法（Last Recently Used），是緩存淘汰算法的其中一種，即最近最久未使用。
在操作系統(tǒng)的內(nèi)存管理中，有一類很重要的算法就是內(nèi)存頁面置換算法（包括FIFO，LRU,LFU等幾種常見頁面置換算法）。
事實(shí)上，Cache算法和內(nèi)存頁面置換算法的核心思想是一樣的：都是在給定一個(gè)限定大小的空間的前提下，設(shè)計(jì)一個(gè)原則如何來更新和訪問其中的元素。
下面說一下LRU算法的核心思想，LRU算法的設(shè)計(jì)原則是：
如果一個(gè)數(shù)據(jù)在最近一段時(shí)間沒有被訪問到，那么在將來它被訪問的可能性也很小。也就是說，當(dāng)限定的空間已存滿數(shù)據(jù)時(shí)，應(yīng)當(dāng)把最久沒有被訪問到的數(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：控制訪問順序。用于設(shè)置LinkedHashMap在調(diào)用 get() 之后的操作。如果設(shè)置為true，則每次調(diào)用get后會(huì)將該元素移動(dòng)到末尾
* removeEldestEntry：默認(rèn)返回為false，在調(diào)用 afterNodeInsertion()的內(nèi)部，調(diào)用該方法。也就是說，每次添加元素之后，檢查并移除最后一個(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);
}
}
// 訪問Node之后的操作，可以看到，當(dāng)設(shè)置了accessOrder以后，訪問元素之后，會(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），通過源碼注釋可以知道，這個(gè)表示元素的訪問模式。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){
// 先把原來node的前后連起來，如果前后不為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)自測通過
測試代碼：
@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
