image
原文鏈接：https://wangwei.one/posts/java-algoDS-LRU-implement-by-linkedlist.html
前面，我們學(xué)習(xí)了 鏈表 的實現(xiàn)，今天我們來學(xué)習(xí)鏈表的一個經(jīng)典的應(yīng)用場景——LRU淘汰算法。
緩存是一種提高數(shù)據(jù)讀取性能的技術(shù)，在硬件設(shè)計、軟件開發(fā)中都有著非常廣泛的應(yīng)用，比如常見的 CPU 緩存、數(shù)據(jù)庫緩存、瀏覽器緩存等等。
緩存的大小有限，當(dāng)緩存被用滿時，哪些數(shù)據(jù)應(yīng)該被清理出去，哪些數(shù)據(jù)應(yīng)該被保留？這就需要緩存淘汰策略來決定。常見的策略有三種：先進(jìn)先出策略 FIFO（First In，F(xiàn)irst Out）、最少使用策略 LFU（Least Frequently Used）、最近最少使用策略 LRU（Least Recently Used），本篇將介紹LRU策略算法。
LRU Cache
這一算法的核心思想是，當(dāng)緩存數(shù)據(jù)達(dá)到預(yù)設(shè)的上限后，會優(yōu)先淘汰掉近期最少使用的緩存對象。
思路
LRU淘汰算法涉及數(shù)據(jù)的添加與刪除，出于性能考慮，采用鏈表來進(jìn)行實現(xiàn)，思路如下：
- 維護(hù)一個雙向鏈表用于存放緩存數(shù)據(jù)，越接近鏈表尾部的數(shù)據(jù)表示越少被使用到。
- 放入一個數(shù)據(jù)時，如果數(shù)據(jù)已存在則將其移動到鏈表頭部，并更新Key所對應(yīng)的Value值，如果不存在，則：
- 如果緩存容量已達(dá)到最大值，則將鏈表尾部節(jié)點刪除掉，將新的數(shù)據(jù)放入鏈表頭部；
- 如果緩存容量未達(dá)到最大值，則直接將新的數(shù)據(jù)放入鏈表頭部；
- 查詢一個數(shù)據(jù)時，遍歷整個鏈表，如果能查詢到對應(yīng)的數(shù)據(jù)，則將其移動到鏈表頭部；如果查詢不到則返回
null；- 由于遍歷鏈表的時間復(fù)雜度為
O(n)，我們可以使用散列表HashMap來記錄每個Key所對應(yīng)的Node節(jié)點，將時間復(fù)雜度降為O(1)。
- 由于遍歷鏈表的時間復(fù)雜度為
LRU-Cache
代碼
package one.wangwei.algorithms.utils;
import java.util.HashMap;
import java.util.Map;
/**
* LRU Cache
*
* @author https://wangwei.one
* @date 2019/01/29
*/
public class LRUCache<K, V> {
private int capacity;
private Node head;
private Node tail;
private Map<K, Node> nodeMap;
public LRUCache(int capacity) {
this.capacity = capacity;
this.nodeMap = new HashMap<>(capacity);
}
/**
* Get Key
*
* @param key
* @return
*/
public V get(K key) {
Node existNode = nodeMap.get(key);
if (existNode == null) {
return null;
}
remove(existNode);
addFirst(existNode);
return existNode.value;
}
/**
* Add Key-Value
*
* @param key
* @param value
*/
public void put(K key, V value) {
Node existNode = nodeMap.get(key);
if (existNode == null) {
Node newNode = new Node(key, value);
if (nodeMap.size() >= capacity) {
removeLast();
}
addFirst(newNode);
}
else {
// update the value
existNode.value = value;
remove(existNode);
addFirst(existNode);
}
}
/**
* remove node
*
* @param node
*/
private void remove(Node node) {
Node prev = node.prev;
Node next = node.next;
if (prev == null) {
head = next;
} else {
prev.next = next;
}
if (next == null) {
tail = prev;
} else {
next.prev = prev;
}
nodeMap.remove(node.key);
}
/**
* add first node
*
* @param node
*/
private void addFirst(Node node) {
// don't forget set node prev pointer to null !
node.prev = null;
if (head == null) {
head = tail = node;
} else {
node.next = head;
head.prev = node;
head = node;
}
nodeMap.put(node.key, node);
}
/**
* remove last
*/
private void removeLast() {
if (tail == null) {
return;
}
// remove key from map
nodeMap.remove(tail.key);
// remove node from linked list
Node prev = tail.prev;
if (prev != null) {
prev.next = null;
tail = prev;
} else {
head = tail = null;
}
}
private class Node {
private K key;
private V value;
private Node prev;
private Node next;
private Node(K key, V value) {
this.key = key;
this.value = value;
}
}
}
LeetCode上相關(guān)的練習(xí)題：Leetcode 146. LRU Cache
性能測試：LeetCode上運行時間為88ms，超過了 43.42% 的Java代碼。
