LRU（Least recently used，最近最少使用）算法是目前廣泛使用的緩存淘汰算法。算法思想是如果數(shù)據(jù)最近被訪問(wèn)（讀或?qū)懀?，那么將?lái)被訪問(wèn)的概率也更高。所以長(zhǎng)期不被訪問(wèn)的數(shù)據(jù)將會(huì)被淘汰。
LeetCode的146題要求實(shí)現(xiàn)這一算法。
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);
}
}
上面這段代碼可以繼續(xù)優(yōu)化。
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本就可以按照訪問(wèn)訪問(wèn)順序排序，當(dāng)時(shí)沒(méi)有注意到這個(gè)構(gòu)造方法。其余代碼略去。
從LinkedHashMap的構(gòu)造方法來(lái)看，可以分成兩類：按插入順序排序，按訪問(wèn)順序排序。
我的提交代碼非常依賴LinkedHashMap這種數(shù)據(jù)結(jié)構(gòu)，從類名上看來(lái)，它和HashMap必然有所關(guān)系。其實(shí)它是HashMap的子類，在HashMap基礎(chǔ)上增加排序功能，讓輸出順序與插入順序或者訪問(wèn)順序相同，即最后一個(gè)插入（或訪問(wèn)）的元素最后一個(gè)輸出。
HashMap的實(shí)現(xiàn)依賴鏈表數(shù)組（數(shù)組的每個(gè)元素是鏈表），但里面的元素是無(wú)序的。LinkedHashMap在其基礎(chǔ)之上，增加了一個(gè)鏈表來(lái)記錄元素的順序。
通過(guò)對(duì)比這兩類，完美體現(xiàn)了面向?qū)ο缶幊痰睦^承機(jī)制，需要深刻體會(huì)！
學(xué)習(xí)一個(gè)類的最基本最重要的方法就是JDK文檔。一段官方文檔，勝過(guò)千句啰嗦。
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還可以在某種特點(diǎn)條件下removeEldestEntry，這也是實(shí)現(xiàn)LRU算法的一個(gè)關(guān)鍵。
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.
常見(jiàn)用法：
private static final int MAX_ENTRIES = 100;
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > MAX_ENTRIES;
}
原題：LRU Cache
