起飛，手擼了一個 LRU 緩存，源碼原來這麼簡單！

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