LRU是Least Recently Used的縮寫，即最近最少使用，是一種常用的頁面置換算法，選擇最近最久未使用的頁面予以淘汰。當限定的空間已存滿數據時，應當把最久沒有被訪問到的數據淘汰。
簡單描述一下在《操作系統》這本書里面對于LRU算法的解說。
假定系統為某進程分配了3個物理塊，進程運行時的頁面走向為 7 0 1 2 0 3 0 4，開始時3個物理塊均為空，那么LRU 算法是如下工作的：
這就是最基本的LRU的磁盤調度邏輯，該算法運用領域比較廣泛比如redis的內存淘汰策略等等，該算法也是面試中面試官常常用來考驗面試者代碼能力和對LRU算法的正確理解。
以下我主要以為雙向鏈表+HashMap的方式手撕一個時間復雜度為O(1)的LRU算法。
在JAVA中，其實LinkedHashMap已經實現了LRU緩存淘汰算法，需要在構造方法第三個參數傳入true( accessOrder = true;)，表示按照時間順序訪問。可以直接繼承LinkedHashMap來實現。
public class LRULinkedHashMap<K, V> extends LinkedHashMap<K, V> {
private int capacity;
LRULinkedHashMap(int capacity) {
//true是表示按照訪問時間排序,
super(capacity, 0.75f, true);
//傳入指定的緩存最大容量
this.capacity = capacity;
}
/**
* 實現LRU的關鍵方法，如果map里面的元素個數大于了緩存最大容量，則刪除鏈表的頂端元素
*/
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
算法設計思路
- 訪問某個節點時，將其從原來的位置刪除，并重新插入到鏈表頭部。
- 這樣就能保證鏈表尾部存儲的就是最近最久未使用的節點，當節點數量大于緩存最大空間時就淘汰鏈表尾部的節點。
- 為了使刪除操作時間復雜度為 O(1)，就不能采用遍歷的方式找到某個節點。
- HashMap 存儲著 Key 到節點的映射，通過 Key 就能以 O(1) 的時間得到節點，然后再以 O(1) 的時間將其從雙向隊列中刪除。
一.構建雙向鏈表Node節點
/**
* 定義雙向鏈表其中K為Map中的K 降低查找時間復雜度
*/
class Node {
K k;
V v;
Node pre;
Node next;
Node(K k, V v) {
this.k = k;
this.v = v;
}
}
二.定義變量
//定義緩存大小
private int size;
// 存儲K和Node節點的映射 Node中會存放KV
private HashMap<K, Node> map;
private Node head;
private Node tail;
三.初始化結構體
XLRUCache(int size) {
this.size = size;
map = new HashMap<>();
}
四.添加元素
/**
* 添加元素
* 1.元素存在，將元素移動到隊尾
* 2.不存在，判斷鏈表是否滿。
* 如果滿，則刪除隊首（head）元素，新元素放入隊尾元素
* 如果不滿，放入隊尾（tail）元素
*/
public void put(K key, V value) {
Node node = map.get(key);
if (node != null) {
//更新值
node.v = value;
moveNodeToTail(node);
} else {
Node newNode = new Node(key, value);
//鏈表滿，需要刪除首節點
if (map.size() == size) {
Node delHead = removeHead();
map.remove(delHead.k);
}
addLast(newNode);
map.put(key, newNode);
}
}
- 移動元素到鏈表尾部
public void moveNodeToTail(Node node) {
if (tail == node) {
return;
}
// 頭節點直接置空
if (head == node) { // 備注一
head = node.next;
head.pre = null;
} else { // 備注一
node.pre.next = node.next;
node.next.pre = node.pre;
}
// 備注三
node.pre = tail;
node.next = null;
tail.next = node;
tail = node;
}
- 看備注一&備注三如下圖
- 看備注二&備注三如下圖
- 刪除頭節點
public Node removeHead() {
// 空鏈表
if (head == null) {
return null;
}
Node res = head;
// 只有一個節點
if (head == tail) {
head = null;
tail = null;
} else {
// 多個節點
head = res.next;
head.pre = null;
res.next = null;
}
return res;
}
map.remove(delHead.k): 刪除Map中的Kv映射關系
- 添加新節點
public void addLast(Node newNode) {
// 添加節點為空節點直接返回
if (newNode == null) {
return;
}
// 如果鏈表為空則直接添加
if (head == null) {
head = newNode;
tail = newNode;
} else {
// 不為空則尾部添加
tail.next = newNode;
newNode.pre = tail;
tail = newNode;
}
}
如果鏈表為空則將該元素設置成表頭元素同時也是表尾元素。
五.獲取元素
public V get(K key) {
Node node = map.get(key);
if (node != null) {
moveNodeToTail(node);
return node.v;
}
return null;
}
調度訪問后的節點需要移動到鏈表尾部。
完整代碼
import java.util.HashMap;
/**
* @Auther: Xianglei
* @Company:
* @Date: 2020/6/27 14:52
* @Version 1.0
*/
public class XLRUCache<K, V> {
private int size;
// 存儲K和Node節點的映射 Node中會存放KV
private HashMap<K, Node> map;
private Node head;
private Node tail;
XLRUCache(int size) {
this.size = size;
map = new HashMap<>();
}
/**
* 添加元素
* 1.元素存在，將元素移動到隊尾
* 2.不存在，判斷鏈表是否滿。
* 如果滿，則刪除隊首元素，放入隊尾元素，刪除更新哈希表
* 如果不滿，放入隊尾元素，更新哈希表
*/
public void put(K key, V value) {
Node node = map.get(key);
if (node != null) {
//更新值
node.v = value;
moveNodeToTail(node);
} else {
Node newNode = new Node(key, value);
//鏈表滿，需要刪除首節點
if (map.size() == size) {
Node delHead = removeHead();
map.remove(delHead.k);
}
addLast(newNode);
map.put(key, newNode);
}
}
public V get(K key) {
Node node = map.get(key);
if (node != null) {
moveNodeToTail(node);
return node.v;
}
return null;
}
public void addLast(Node newNode) {
if (newNode == null) {
return;
}
if (head == null) {
head = newNode;
tail = newNode;
} else {
tail.next = newNode;
newNode.pre = tail;
tail = newNode;
}
}
public void moveNodeToTail(Node node) {
if (tail == node) {
return;
}
if (head == node) {
head = node.next;
head.pre = null;
} else {
node.pre.next = node.next;
node.next.pre = node.pre;
}
node.pre = tail;
node.next = null;
tail.next = node;
tail = node;
}
public Node removeHead() {
if (head == null) {
return null;
}
Node res = head;
if (head == tail) {
head = null;
tail = null;
} else {
head = res.next;
head.pre = null;
res.next = null;
}
return res;
}
/**
* 定義雙向鏈表
*/
class Node {
K k;
V v;
Node pre;
Node next;
Node(K k, V v) {
this.k = k;
this.v = v;
}
}
}
測試
至此，你應該已經掌握 LRU 算i法的思想和實現過程了，這里面最重要的一點是理清楚雙向鏈表和HasMap的映射關系以及節點移動操作。自此，你知道為什么用雙向鏈表了嗎？
更多精彩好文盡在： Java編程之道
