起飛，手擼了一個 LRU 緩存，源碼原來這么簡單！
LRU 介紹
LRU是 Least Recently Used 的縮寫，即最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。
簡單的說就是，對于一組數(shù)據(jù)，例如：int[] a = {1,2,3,4,5,6}，如果1,2這幾個數(shù)字經(jīng)常被使用，那么會排在3,4,5,6的后面，數(shù)組變成如下：int[] a = {3,4,5,6,1,2}，如果一個數(shù)字，經(jīng)常不被使用，就會排在最前面!
LRU 算法，一般用于熱點數(shù)據(jù)的查詢，比如新聞信息，越是能被用戶看得多的新聞，越有可能被別的用戶所看到，對于那種基本沒人訪問的新聞，基本都類似存入大海!
在 Java 中，就有這么一個集合類實現(xiàn)了這個功能，它就是LinkedHashMap!
LinkedHashMap 介紹
我們都知道，在java集合中，LinkedHashMap 繼承自 HashMap，底層是一個雙向鏈表的數(shù)據(jù)結構，與 HashMap 不同的是，LinkedHashMap 初始化階段有個參數(shù)accessOrder，默認是false。
public class LinkedHashMap<K,V>
extends HashMap<K,V>
implements Map<K,V>{
/**雙向鏈表的頭節(jié)點*/
transient LinkedHashMap.Entry<K,V> head;
/**雙向鏈表的尾節(jié)點*/
transient LinkedHashMap.Entry<K,V> tail;
/**
* 1、如果accessOrder為true的話，則會把訪問過的元素放在鏈表后面，放置順序是訪問的順序
* 2、如果accessOrder為false的話，則按插入順序來遍歷
*/
final boolean accessOrder;
}
如果傳入的是true，則會把最近訪問過的元素放在鏈表后面，放置順序是訪問的順序，測試如下：
public static void main(String[] args) {
//accessOrder默認為false
Map<String, String> accessOrderFalse = new LinkedHashMap<>();
accessOrderFalse.put("1","1");
accessOrderFalse.put("2","2");
accessOrderFalse.put("3","3");
accessOrderFalse.put("4","4");
System.out.println("acessOrderFalse："+accessOrderFalse.toString());
//accessOrder設置為true
Map<String, String> accessOrderTrue = new LinkedHashMap<>(16, 0.75f, true);
accessOrderTrue.put("1","1");
accessOrderTrue.put("2","2");
accessOrderTrue.put("3","3");
accessOrderTrue.put("4","4");
accessOrderTrue.get("2");//獲取鍵2
accessOrderTrue.get("3");//獲取鍵3
System.out.println("accessOrderTrue："+accessOrderTrue.toString());
}
輸出結果如下：
acessOrderFalse：{1=1, 2=2, 3=3, 4=4}
accessOrderTrue：{1=1, 4=4, 2=2, 3=3}
可以得知，當我們將accessOrder設置為true的時候，經(jīng)常被訪問的元素會放入前面!
我們利用這個特性，使用 LinkedHashMap 來實現(xiàn)一個 LRU 緩存，操作如下：
- 創(chuàng)建一個 LinkedHashMap 對象，將accessOrder設置為true;
- 設定 LinkedHashMap 的容量為n，超過這個值就刪除多余的元素;
- 重寫 LinkedHashMap 中removeEldestEntry()方法;
其中removeEldestEntry()表示，如果返回的是true，就會移除最近不被使用的元素，如果返回false，不做任何操作，這個方法每次在add()的時候就會調用。
創(chuàng)建一個 LRU 緩存類，內容如下：
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
//創(chuàng)建一個容量為3的LinkedHashMap
private static final int MAX_SIZE = 3;
/**
* 重寫LinkedHashMap中removeEldestEntry方法
* @param eldest
* @return
*/
protected boolean removeEldestEntry(Map.Entry eldest) {
//如果容器中的元素個數(shù)大于MAX_SIZE，在每次添加元素的時候，移除容器中最近不被使用的元素
return size() > MAX_SIZE;
}
public LRULinkedHashMap() {
//設置LinkedHashMap初始化容量，負載因子為0.75f，accessOrder設置為true
super(MAX_SIZE, 0.75f, true);
}
}
測試使用：
public static void main(String[] args) {
LRULinkedHashMap<String,String> cache = new LRULinkedHashMap<String,String>();
cache.put("1","a");
cache.put("2","b");
cache.put("3","c");
System.out.println("初始cache內容：" + cache.toString());
cache.get("2");
System.out.println("查詢key為2的元素之后，cache內容：" + cache.toString());
cache.put("4","d");
System.out.println("添加新的元素之后，cache內容：" + cache.toString());
}
輸出結果如下：
初始cache內容：{1=a, 2=b, 3=c}
查詢key為2的元素之后，cache內容：{1=a, 3=c, 2=b}
添加新的元素之后，cache內容：{3=c, 2=b, 4=d}
初始cache內容：{1=a, 2=b, 3=c}查詢key為2的元素之后，cache內容：{1=a, 3=c, 2=b}添加新的元素之后，cache內容：{3=c, 2=b, 4=d}
