LRU緩存淘汰算法的詳細介紹與具體實現

? ? ? ?LRU（Least Recently Used，最近最少使用）是一種基于時間局部性原理的緩存淘汰策略。其核心思想是：最近被訪問的數據在未來更可能被再次使用，而最久未被訪問的數據應優先被淘汰，從而在有限的緩存空間內保留高價值數據。

數據結構設計

LRU通過哈希表 + 雙向鏈表實現高效操作：

1.雙向鏈表（DlinkedNode）：維護數據訪問順序，鏈表頭部為最新訪問節點，尾部為最久未使用節點；

2.哈希表（HashMap）：存儲鍵與鏈表節點的映射，支持以O(1)的時間復雜度定位節點，使插入、查詢、刪除操作均能快速完成。

圖解：?

關鍵操作流程

1.數據訪問（get方法）：

· 若數據存在于緩存（哈希表命中）：

? · 從雙向鏈表中移除該節點；

? · 將該節點插入鏈表頭部。

· 若數據不存在（未命中）：返回默認值-1。

2.數據插入（put方法）：

· 若鍵已存在：

? · 更新節點值；

? · 移動節點至鏈表頭部。

· 若鍵不存在：

? · 緩存已滿時，刪除尾部節點（最久未使用）并移除哈希表對應鍵；

? · 創建新節點插入鏈表頭部，并存入哈希表。

LRU的功能特性

?1.添加元素：將新元素插入到隊頭（表示最近使用）；

2.訪問/更新元素：將元素從原來的位置刪除，再插入到隊頭（更新使用時間）；

3.淘汰元素：當size > capacity，即容量不足時，刪除隊尾元素（最久未使用）。

LRU算法題實戰

LCR 031. LRU 緩存 - 力扣（LeetCode）LCR 031. LRU 緩存 - 運用所掌握的數據結構，設計和實現一個? LRU (Least Recently Used，最近最少使用) 緩存機制 [https://baike.baidu.com/item/LRU] 。實現 LRUCache 類： * LRUCache(int capacity) 以正整數作為容量?capacity 初始化 LRU 緩存 * int get(int key) 如果關鍵字 key 存在于緩存中，則返回關鍵字的值，否則返回 -1 。 * void put(int key, int value)?如果關鍵字已經存在，則變更其數據值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新數據之前刪除最久未使用的數據值，從而為新的數據值留出空間。?示例：輸入["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"][[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]輸出[null, null, null, 1, null, -1, null, -1, 3, 4]解釋LRUCache lRUCache = new LRUCache(2);lRUCache.put(1, 1); // 緩存是 {1=1}lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}lRUCache.get(1); // 返回 1lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，緩存是 {1=1, 3=3}lRUCache.get(2); // 返回 -1 (未找到)lRUCache.put(4, 4); // 該操作會使得關鍵字 1 作廢，緩存是 {4=4, 3=3}lRUCache.get(1); // 返回 -1 (未找到)lRUCache.get(3); // 返回 3lRUCache.get(4); // 返回 4?提示： * 1 <= capacity <= 3000 * 0 <= key <= 10000 * 0 <= value <= 105 * 最多調用 2 * 105 次 get 和 put?進階：是否可以在?O(1) 時間復雜度內完成這兩種操作？?注意：本題與主站 146?題相同：https://leetcode-cn.com/problems/lru-cache/ [https://leetcode-cn.com/problems/lru-cache/]?https://leetcode.cn/problems/OrIXps/題目描述：

運用所掌握的數據結構，設計和實現一個LRU (Least Recently Used，最近最少使用) 緩存機制。

實現?LRUCache?類：

LRUCache(int capacity)?以正整數作為容量?capacity?初始化 LRU 緩存。
int get(int key)?如果關鍵字?key?存在于緩存中，則返回關鍵字的值，否則返回?-1?。
void put(int key, int value)?如果關鍵字已經存在，則變更其數據值；如果關鍵字不存在，則插入該組「關鍵字-值」。當緩存容量達到上限時，它應該在寫入新數據之前刪除最久未使用的數據值，從而為新的數據值留出空間。

示例：

輸入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解釋
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 緩存是 {1=1}
lRUCache.put(2, 2); // 緩存是 {1=1, 2=2}
lRUCache.get(1);??? // 返回 1
lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，緩存是 {1=1, 3=3}
lRUCache.get(2);??? // 返回 -1 (未找到)
lRUCache.put(4, 4); // 該操作會使得關鍵字 1 作廢，緩存是 {4=4, 3=3}
lRUCache.get(1);??? // 返回 -1 (未找到)
lRUCache.get(3);??? // 返回 3
lRUCache.get(4);??? // 返回 4

提示：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多調用?2 * 10 ^ 5?次?get?和?put?

class LRUCache {

? ? public LRUCache(int capacity) {

? ? ? ?

? ? }

? ?

? ? public int get(int key) {

? ? ? ?

? ? }

? ?

? ? public void put(int key, int value) {

? ? ? ?

? ? }

}

/**

?* Your LRUCache object will be instantiated and called as such:

?* LRUCache obj = new LRUCache(capacity);

?* int param_1 = obj.get(key);

?* obj.put(key,value);

?*/

首先需要定義雙向鏈表節點類：

1.定義雙向鏈表節點類，包含key（對應哈希表的鍵）、val（緩存實際要存儲的值）、prev（雙向鏈表節點的前驅節點）、next（雙向鏈表節點的后繼節點），并提供用于初始化的無參構造方法和可用于賦值的有參構造方法。

// 雙向鏈表節點類
class DlinkedNode {int key; // 鍵int val; // 值DlinkedNode prev; // 前驅節點DlinkedNode next; // 后繼節點public DlinkedNode() { // 無參構造方法}public DlinkedNode(int key, int val) { // 有參構造方法this.key = key;this.val = val;}
}

2.定義了LRU的核心成員變量，包含負責快速查找的哈希表map（通過key獲取節點DlinkedNode）、虛擬頭尾節點head和tail（簡化對邊界的處理，避免鏈表為空、插入第一個節點、刪除最后一個節點的指針操作）、size（記錄緩存中實際的節點數，用于判斷是否需要淘汰數據）、capacity（緩存的最大容量，由用戶設定），共同實現LRU“快速訪問 + 動態維護順序 + 容量管理”的核心需求。

// 哈希表（鍵，雙向鏈表節點），用于快速查找節點
private Map<Integer, DlinkedNode> map = new HashMap<>();
// 虛擬頭節點，簡化邊界操作
private DlinkedNode head;
// 虛擬尾節點
private DlinkedNode tail;
// 當前元素數量
private int size;
// 緩存最大容量
private int capacity;

?3.讓當前節點的前驅節點的后繼指針指向當前節點的后繼節點，讓當前節點的后繼節點的前驅指針指向當前節點的前驅節點，即繞過當前節點，從雙向鏈表中移除node節點。

// 從雙向鏈表中刪除指定節點（跳過當前節點）
private void remove(DlinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;
}

4.首先讓新節點的前驅指針指向虛擬頭節點head，然后讓新節點的后繼指針指向head原本的下一個節點，再讓原第一個節點head.next的前驅指針轉而指向新節點，最后讓虛擬頭節點head的后繼指針指向新節點，目的是將指定節點插入到虛擬頭節點head之后，作為鏈表的第一個實際節點。

// 將節點插入到雙向鏈表的頭部
private void insertToHead(DlinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;
}

5.調用remove(node)方法，將node節點從當前所在的位置從雙向鏈表中移除（斷開與前后的連接），調用insertToHead(node)方法，將剛才刪除的節點重新插入到雙向鏈表的頭部（建立該節點與原頭節點的連接）。

// 將節點移動到雙向鏈表的頭部
private void moveToHead(DlinkedNode node) {remove(node); // 先刪除后插入insertToHead(node);
}

6.首先定位尾部節點，tail為虛擬尾節點，真正的尾部節點為尾指針的前一個節點（tail.prev），用target保存這個要刪除的有效節點，再調用remove(target)刪除節點，最后返回target。

// 刪除尾部節點
private DlinkedNode removeTail() {DlinkedNode target = tail.prev;remove(target);return target;
}

7.初始方法LRUCache：

this.size = 0;

?表示當前緩存中存儲的有效數據數量為0（初始為空）。

?this.capacity = capacity;

?記錄緩存的最大容量（即最多能存儲的數據個數），由外部傳入并賦值。

head = new DlinkedNode();

tail = new DlinkedNode();

?創建兩個虛擬節點，分別作為鏈表的頭哨兵和尾哨兵。

head.next = tail;

tail.prev = head;

連接頭哨兵和尾哨兵，形成一個初始的完整閉環空鏈表結構。

// LRU初始化
public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new DlinkedNode();tail = new DlinkedNode();head.next = tail;tail.prev = head;
}

8.LRU的get()方法詳解：

通過哈希表的key查找對應的雙向鏈表節點node，如果node為空，說明緩存中沒有該鍵對應的記錄，返回-1，如果node存在，調用moveToHead(node)將該節點移動到雙向鏈表的頭部，再返回找到的節點存儲的值。

// 獲取LRU中指定鍵的值
public int get(int key) {DlinkedNode node = map.get(key);if (node == null) return -1; // 節點不存在moveToHead(node); // 節點存在，標記為最近使用return node.val;
}

9.LRU的put()方法詳解：?

DlinkedNode node = map.get(key);

通過map.get(key)查找鍵對應的節點node。

DlinkedNode newNode = new DlinkedNode(key, value);

map.put(key, newNode);

insertToHead(newNode);

size++;

若鍵不存在，創建新節點newNode，存儲鍵值對(key, value)，將新節點存入哈希表（方便后續查找使用），再調用insertToHead(newNode)將新節點插入雙向鏈表頭部，緩存當前大小size自增+1。

if (size > capacity) {?
? ? DlinkedNode del = removeTail();
? ? map.remove(del.key);
? ? size--;
}?

若鍵不存在，當size > capacity時，調用removeTail()刪除雙向鏈表的尾部節點，并刪除哈希表中該節點的鍵，最后size自減-1，保證緩存大小不超過容量。

node.val = value;

moveToHead(node);

若鍵已存在，更新節點的值，用value覆蓋原來的val，再調用moveToHead(node)方法將該節點移向雙向鏈表的頭部，哈希表會自動同步此處的更新，無需額外操作。

// 向LRU中插入或更新鍵值對
public void put(int key, int value) {DlinkedNode node = map.get(key);if (node == null) {DlinkedNode newNode = new DlinkedNode(key, value);map.put(key, newNode);insertToHead(newNode);size++;if (size > capacity) { // 超出容量則需淘汰最久未使用的元素DlinkedNode del = removeTail();map.remove(del.key);size--;}} else { // 節點存在，更新值并移到頭部node.val = value;moveToHead(node);}
}

LRU實現完整源碼：

class DlinkedNode {int key;int val;DlinkedNode prev; DlinkedNode next; public DlinkedNode() { }public DlinkedNode(int key, int val) { this.key = key;this.val = val;}
}class LRUCache {private Map<Integer, DlinkedNode> map = new HashMap<>();private DlinkedNode head;private DlinkedNode tail;private int size;private int capacity;public LRUCache(int capacity) {this.size = 0;this.capacity = capacity;head = new DlinkedNode();tail = new DlinkedNode();head.next = tail;tail.prev = head;}public int get(int key) {DlinkedNode node = map.get(key);if (node == null) return -1; moveToHead(node); return node.val;}public void put(int key, int value) {DlinkedNode node = map.get(key);if (node == null) {DlinkedNode newNode = new DlinkedNode(key, value);map.put(key, newNode);insertToHead(newNode);size++;if (size > capacity) { DlinkedNode del = removeTail();map.remove(del.key);size--;}} else { node.val = value;moveToHead(node);}}private void remove(DlinkedNode node) {node.prev.next = node.next;node.next.prev = node.prev;}private void insertToHead(DlinkedNode node) {node.prev = head;node.next = head.next;head.next.prev = node;head.next = node;}private void moveToHead(DlinkedNode node) {remove(node);insertToHead(node);}private DlinkedNode removeTail() {DlinkedNode target = tail.prev;remove(target);return target;}
}

代碼直觀理解：

LRU的優勢分析

1.貼合數據訪問的局部性特點：實際中數據訪問常呈現短期集中的熱點（如當前操作的數據），LRU優先保留近期被訪問的數據，能高效命中這些短期高頻使用的數據，符合實際場景的訪問規律。
2.動態響應性好：當訪問模式變化（如新熱點出現），可快速淘汰舊冷門數據，為新數據騰空間，適應變化靈活。
3.實現高效低成本：通過哈希表+雙向鏈表，可在O(1)時間完成查找、更新和淘汰操作，無需復雜統計，資源消耗低。
4.命中率較優：相比FIFO（先進先出），避免盲目淘汰有用老數據，相比LFU（最不經常使用），更易更新新熱點，在多數場景下命中率較高，平衡實用與性能。