LeetCode LRU演算法

05-13

LRU（Least recently used，最近最少使用）演算法是目前廣泛使用的緩存淘汰演算法。演算法思想是如果數據最近被訪問（讀或寫），那麼將來被訪問的概率也更高。所以長期不被訪問的數據將會被淘汰。

LeetCode的146題要求實現這一演算法。

public class LRUCache { private final int capacity; private Map<Integer, Integer> map; public LRUCache(int capacity) { this.capacity = capacity; this.map = new LinkedHashMap<Integer, Integer>() { private static final long serialVersionUID = 23L; @Override protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) { return size() > LRUCache.this.capacity; } }; } public int get(int key) { Integer value = map.get(key); if (value != null) { map.remove(key); map.put(key, value); } else { value = -1; } return value; } public void put(int key, int value) { if (map.containsKey(key)) { map.remove(key); } map.put(key, value); }}

從當時的運行效果來看，幾乎完美。但LeetCode的cases可能發生變動，現在重新提交這段代碼，效果就大不如從前了。

上面這段代碼可以繼續優化。

public LRUCache(int capacity) { this.capacity = capacity; this.map = new LinkedHashMap<Integer, Integer>(32, 0.75f, true) { private static final long serialVersionUID = 23L; @Override protected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) { return size() > LRUCache.this.capacity; } };}

LinkedHashMap本就可以按照訪問訪問順序排序，當時沒有注意到這個構造方法。其餘代碼略去。

從LinkedHashMap的構造方法來看，可以分成兩類：按插入順序排序，按訪問順序排序。

我的提交代碼非常依賴LinkedHashMap這種數據結構，從類名上看來，它和HashMap必然有所關係。其實它是HashMap的子類，在HashMap基礎上增加排序功能，讓輸出順序與插入順序或者訪問順序相同，即最後一個插入（或訪問）的元素最後一個輸出。

HashMap的實現依賴鏈表數組（數組的每個元素是鏈表），但裡面的元素是無序的。LinkedHashMap在其基礎之上，增加了一個鏈表來記錄元素的順序。

通過對比這兩類，完美體現了面向對象編程的繼承機制，需要深刻體會！

學習一個類的最基本最重要的方法就是JDK文檔。一段官方文檔，勝過千句啰嗦。

Hash table and linked list implementation of the Map interface, with predictable iteration order. This implementation differs from HashMap in that it maintains a doubly-linked list running through all of its entries.

LinkedHashMap還可以在某種特點條件下removeEldestEntry，這也是實現LRU演算法的一個關鍵。

Returns true if this map should remove its eldest entry. This method is invoked by put and putAll after inserting a new entry into the map. It provides the implementor with the opportunity to remove the eldest entry each time a new one is added. This is useful if the map represents a cache: it allows the map to reduce memory consumption by deleting stale entries.

常見用法：

private static final int MAX_ENTRIES = 100;protected boolean removeEldestEntry(Map.Entry eldest) { return size() > MAX_ENTRIES;}

原題：LRU Cache

參考資料：LinkedHashMap (Java Platform SE 8 )