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