LRU算法，最近最少使用原則，如果要實現(xiàn)該算法，可以借助LinkedHashMap數(shù)據(jù)結構，LinkedHashMap繼承HashMap，底層使用哈希表和雙向鏈表來保存所有元素，使用LinkedHashMap可以確保元素按照順序進行存儲。

默認情況下，LinkedHashMap是按照元素的添加順序存儲，也可以啟用按照訪問順序存儲，即最近讀取的數(shù)據(jù)放在最前面，最早讀取的數(shù)據(jù)放在最后面，然后它還有一個判斷是否刪除最老數(shù)據(jù)的方法，默認是返回false，即不刪除數(shù)據(jù)。

下面就基于這兩種存儲方式，簡單展示一下如何實現(xiàn)LRU算法：

一、基于按添加順序存儲的方式實現(xiàn)LRU：

public class LRUTest {int capacity;LinkedHashMap<Integer, Integer> cache;LRUTest(int capacity){cache = new LinkedHashMap<>();this.capacity = capacity;}//訪問元素public int get(int key){if(!cache.containsKey(key)){return -1;}//存在，先從鏈表頭部刪除刪除，在插入到鏈表尾部int val = cache.get(key);cache.remove(key);cache.put(key, val);return val;}//添加元素public void put(int key, int val){if(cache.containsKey(key)){cache.remove(key);}//如果鏈表已經(jīng)滿了，則刪除頭部節(jié)點if(cache.size() == capacity){Set<Integer> keySet = cache.keySet();Iterator<Integer> iterator = keySet.iterator();cache.remove(iterator.next());}cache.put(key, val);} }

二、基于按訪問順序存儲的方式實現(xiàn)LRU：

該方式的核心就是繼承LinkedHashMap，并設置LinkedHashMap的accessOrder參數(shù)為true，然后重寫LinkedHashMap的removeEldestEntry()方法。

public class LRUTest extends LinkedHashMap<String, String> {private int capacity;/*** 當LinkedHashMap的accessOrder參數(shù)為true時，即會按照訪問順序排序，最近訪問的放在最前，最早訪問的放在后面*/public LRUTest(int capacity) {super(16, 0.75f, true);this.capacity = capacity;}/*** LinkedHashMap自帶的判斷是否刪除最老的元素方法，默認返回false，即不刪除老數(shù)據(jù)*/@Overrideprotected boolean removeEldestEntry(Map.Entry<String, String> eldest){return size() > capacity;} }

測試方法：

public static void main(String[] args){Map<String, String> linkedHashMap = new LRUTest(6);linkedHashMap.put("1", "1");linkedHashMap.put("2", "2");linkedHashMap.put("3", "3");linkedHashMap.put("4", "4");linkedHashMap.put("5", "5");linkedHashMap.put("6", "6");linkedHashMap.put("7", "7");linkedHashMap.put("8", "8");linkedHashMap.put("9", "9");System.out.println("size="+linkedHashMap.size());System.out.println(linkedHashMap.get("8"));linkedHashMap.forEach((k,v) ->{System.out.print(k + ":"+ v +" ");});System.out.println();System.out.println("size="+linkedHashMap.size());}

輸出結果：

size=6 8 4:4 5:5 6:6 7:7 9:9 8:8 size=6

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的使用LinkedHashMap实现LRU算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。