LRU （Least Recently Used） 是一種緩存失效策略壁却，即指定最大緩存 item 的數(shù)量，在緩存數(shù)量不足時將最近最少使用的緩存淘汰掉。
不失一般的逊桦，我們假定對緩存主要有兩種操作：
- PUT泣栈，即將數(shù)據(jù)放入緩存中卜高；
- GET，即嘗試從緩存中獲取數(shù)據(jù)南片。
以上兩種操作都會被視為使用了緩存掺涛，當(dāng)緩存空間不足時，將最近最少使用的數(shù)據(jù)從緩存中移除疼进。使用 JAVA薪缆，我們應(yīng)當(dāng)如何實現(xiàn)以上的需求呢？
利用 HashMap 和 雙向鏈表實現(xiàn)
思考上述需求后伞广，可以有一個簡單的解決思路：利用 HashMap 存儲緩存數(shù)據(jù)拣帽，而后將數(shù)據(jù)節(jié)點組成一個雙向鏈表，每次 PUT 或 GET 操作后都將操作涉及到的緩存數(shù)據(jù)節(jié)點插入鏈表的尾部嚼锄，那么在緩存已滿需要淘汰數(shù)據(jù)時就可以將鏈表頭部指向的數(shù)據(jù)節(jié)點刪除了减拭。代碼如下：
public class LRUCache<K, V> {
private int capacity;
private Map<K, Node<K, V>> cacheData;
private Node<K, V> head;
private Node<K, V> tail;
private static class Node<K, V> {
private K key;
private V value;
private Node<K, V> pre;
private Node<K, V> next;
private Node(K key, V value) {
this.key = key;
this.value = value;
}
}
public LRUCache(int capacity) {
if (capacity <= 0) {
throw new InvalidParameterException("capacity 必須大于0");
}
this.capacity = capacity;
//初始化 HashMap 大小為 capacity, 負載因子為 0.75
this.cacheData = new HashMap<>(this.capacity, 0.75f);
// sentinel 方便處理
this.head = new Node<>(null, null);
this.tail = new Node<>(null, null);
this.head.next = this.tail;
this.tail.pre = this.head;
}
public void put(K key, V value) {
if (null == key) {
throw new NullPointerException("key 不能為 null");
}
Node<K, V> node = cacheData.get(key);
//第一次 PUT 生成node
if (null == node) {
node = new Node<>(key, value);
} else {
deQueue(node);
}
//放入尾部
putToTail(node);
//是否需要淘汰數(shù)據(jù)
removeLruIfNecessary();
//放入緩存中
cacheData.put(key, node);
}
/**
* 刪除最近最少使用的數(shù)據(jù)
*/
private void removeLruIfNecessary() {
if (cacheData.size() >= capacity) {
Node<K, V> remove = head.next;
//從鏈表中移除
deQueue(remove);
cacheData.remove(remove.key);
}
}
public V get(K key) {
if (null == key) {
throw new NullPointerException("key 不能為 null");
}
Node<K, V> node = cacheData.get(key);
if (null == node) {
return null;
}
//從鏈表中移除
deQueue(node);
//加入鏈表尾部
putToTail(node);
return node.value;
}
private void deQueue(Node<K, V> node) {
node.pre.next = node.next;
node.next.pre = node.pre;
node.next = node.pre = null;
}
private void putToTail(Node<K, V> node) {
node.pre = tail.pre;
node.next = tail;
node.pre.next = node;
tail.pre = node;
}
}
進行簡單的測試：
public static void main(String[] args) {
LRUCache<Integer, Integer> lruCache = new LRUCache<>(10);
for (int i = 0; i < 20; i++) {
lruCache.put(i, i);
}
for (int j = 19; j >= 10; j--) {
lruCache.get(j);
}
}
利用LinkedHashMap 實現(xiàn)
上面的實現(xiàn)其實還是有些復(fù)雜，其實 JDK 中的 LinkedHashMap 早就幫我們實現(xiàn)好了需要的功能区丑。LinkedHashMap 是HashMap 的一個子類拧粪，保存了記錄的插入順序修陡，在用 Iterator 遍歷 LinkedHashMap 時，先得到的記錄肯定是先插入的.也可以在構(gòu)造時用帶參數(shù)既们，按照應(yīng)用次數(shù)排序濒析。
使用 LinkedHashMap 構(gòu)造 LRU cache的代碼如下：
public class LRUCache<K, V> {
private LinkedHashMap<K, V> linkedHashMap;
public LRUCache(int capacity) {
linkedHashMap = new LinkedHashMap<K, V>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
};
}
public void put(K key, V value) {
linkedHashMap.put(key, value);
}
public V get(K key) {
return linkedHashMap.get(key);
}
}
可以看到，只需要指定構(gòu)造函數(shù)的 accessOrder 為true啥纸，再重寫 LinkedHashMap 的 removeEldestEntry 方法号杏，使其在容量超過預(yù)設(shè)大小時刪除最老元素即可。
