LRU（Least Recently Used）作為最經典的緩存淘汰策略之一，廣泛應用于操作系統、數據庫、Web框架等場景。本文我將深入解析LRU緩存的核心原理、數據結構設計、算法實現及優化策略，結合Java代碼實現，幫你掌握高性能緩存系統的設計方法。

一、LRU緩存核心概念

1.1 LRU策略定義

LRU緩存通過維護一個「最近使用」的順序列表，當緩存容量已滿時，主動淘汰最近最少使用的元素，為新元素騰出空間。其核心思想是：優先保留近期使用過的數據，淘汰長時間未訪問的數據。

1.2 應用場景

• 瀏覽器緩存：存儲最近訪問的網頁資源，加速頁面加載
• 數據庫查詢緩存：緩存高頻訪問的SQL結果，減少數據庫壓力
• Java內存管理：JVM堆內存中的LRU機制優化對象回收
• 分布式系統：Redis的allkeys-lru策略提升熱點數據訪問效率

1.3 核心操作要求

• get(key)：獲取指定鍵的值，若存在則返回并標記為最近使用，時間復雜度O(1)
• put(key, value)：插入或更新鍵值對，若容量不足則淘汰最近最少使用的鍵，時間復雜度O(1)

二、數據結構設計：雙向鏈表+哈希表

2.1 為什么選擇雙向鏈表？

• 有序性維護：鏈表天然支持順序訪問，方便將最近使用的節點移動到頭部
• 快速刪除：雙向鏈表可在O(1)時間內刪除任意節點（需前驅節點指針）
• 高效插入：新節點始終插入頭部，舊節點淘汰從尾部移除

2.2 為什么結合哈希表？

• 快速定位：哈希表存儲鍵到節點的映射，實現O(1)時間的存在性檢查
• 解耦數據：鏈表維護順序，哈希表維護鍵的索引，分工明確

2.3 節點結構設計（雙向鏈表）

class Node {int key;        // 鍵（用于哈希表定位）int value;      // 值Node prev;      // 前驅節點Node next;      // 后繼節點public Node(int key, int value) {this.key = key;this.value = value;}
}

2.4 LRU緩存的邏輯結構

哈希表 (key -> Node)↓
雙向鏈表（頭節點=最近使用，尾節點=最久未使用）
head <-> node1 <-> node2 <-> ... <-> tail

三、核心算法實現

3.1 初始化參數

import java.util.HashMap;public class LRUCache {private HashMap<Integer, Node> cache;  // 鍵到節點的映射private int capacity;                 // 緩存容量private Node head;                    // 最近使用節點（頭節點）private Node tail;                    // 最久未使用節點（尾節點）public LRUCache(int capacity) {this.capacity = capacity;cache = new HashMap<>(capacity);// 初始化虛擬頭尾節點，簡化邊界處理head = new Node(-1, -1);tail = new Node(-1, -1);head.next = tail;tail.prev = head;}
}

3.2 get方法實現（獲取并更新順序）

public int get(int key) {if (!cache.containsKey(key)) {return -1;}Node node = cache.get(key);// 將節點移動到頭部removeNode(node);addToHead(node);return node.value;
}// 私有方法：刪除任意節點
private void removeNode(Node node) {Node prevNode = node.prev;Node nextNode = node.next;prevNode.next = nextNode;nextNode.prev = prevNode;
}// 私有方法：將節點插入頭部
private void addToHead(Node node) {node.next = head.next;node.prev = head;head.next.prev = node;head.next = node;
}

3.3 put方法實現（插入/更新+淘汰策略）

public void put(int key, int value) {if (cache.containsKey(key)) {// 更新值并移動到頭部Node node = cache.get(key);node.value = value;removeNode(node);addToHead(node);return;}if (cache.size() == capacity) {// 淘汰尾節點（最久未使用）Node lastNode = tail.prev;cache.remove(lastNode.key);removeNode(lastNode);}// 插入新節點到頭部Node newNode = new Node(key, value);cache.put(key, newNode);addToHead(newNode);
}

3.4 復雜度分析

• 時間復雜度：
  get和put操作均通過哈希表定位節點（O(1)），雙向鏈表的刪除和插入操作均為O(1)，總體時間復雜度O(1)
• 空間復雜度：
  存儲所有節點的空間為O(capacity)，哈希表和鏈表的額外空間為O(capacity)，總體空間復雜度O(capacity)

四、邊界處理與優化技巧

4.1 虛擬頭尾節點設計

• 作用：避免處理頭節點和尾節點的null指針邊界問題
• 實現：初始化兩個虛擬節點，頭節點的next指向最近使用節點，尾節點的prev指向最久未使用節點

4.2 容量為1的極端情況

// 測試用例：容量為1時，每次put都會淘汰舊節點
LRUCache cache = new LRUCache(1);
cache.put(1, 10);  // 緩存：{1:10}
cache.put(2, 20);  // 淘汰1，緩存：{2:20}
System.out.println(cache.get(1));  // 輸出-1

4.3 線程安全優化

• 問題：上述實現非線程安全，多線程環境下需加鎖
• 解決方案：
  使用synchronized修飾get/put方法，或基于ReentrantLock實現：

private final ReentrantLock lock = new ReentrantLock();public int get(int key) {lock.lock();try {// 原有邏輯} finally {lock.unlock();}
}

五、Java內置實現：LinkedHashMap

5.1 利用LinkedHashMap實現LRU

import java.util.LinkedHashMap;public class LRUCacheJava {private LinkedHashMap<Integer, Integer> cache;private int capacity;public LRUCacheJava(int capacity) {this.capacity = capacity;// accessOrder=true表示按訪問順序排序（最近訪問的在尾部）cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {@Overrideprotected boolean removeEldestEntry(java.util.Map.Entry<Integer, Integer> eldest) {return size() > capacity;}};}public int get(int key) {return cache.getOrDefault(key, -1);}public void put(int key, int value) {cache.put(key, value);}
}

5.2 LinkedHashMap原理

• 數據結構：哈希表+雙向鏈表（維護插入順序或訪問順序）
• 淘汰策略：重寫removeEldestEntry方法，容量超標時淘汰最舊節點
• 性能對比：比手動實現稍慢（封裝帶來的開銷），但代碼更簡潔

六、分布式LRU緩存設計（進階）

6.1 一致性哈希算法

• 問題：分布式環境中緩存節點動態變化時的鍵分布問題
• 解決方案：
  通過一致性哈希將鍵映射到節點，節點增減時僅影響相鄰節點，減少緩存失效

6.2 緩存穿透與雪崩

• 緩存穿透：查詢不存在的鍵導致大量數據庫訪問
  解決方案：緩存空值或布隆過濾器
• 緩存雪崩：大量緩存同時失效導致請求積壓
  解決方案：設置隨機過期時間+多級緩存

6.3 典型架構

客戶端 <-> 負載均衡 <-> 緩存集群（每個節點實現LRU）↓數據源（數據庫/文件系統）

LRU總結

LRU的優缺點

優點	缺點
實現相對簡單	無法處理突發訪問模式
適合時間局部性數據	對空間局部性支持差
平均性能穩定	可能淘汰高頻低最近使用數據

適用場景

• 優先使用：數據訪問符合時間局部性（如歷史記錄、用戶行為數據）
• 謹慎使用：數據訪問模式頻繁變化（如實時統計類數據）
• 結合使用：與LFU（最少頻率使用）策略結合，提升復雜場景性能

優化建議

1. 預加載熱點數據：初始化時加載高頻訪問數據
2. 限制最大容量：避免內存溢出，結合監控動態調整容量
3. 異步淘汰：將淘汰操作放到后臺線程執行，減少主線程阻塞

That’s all, thanks for reading!
覺得有用就點個贊、收進收藏夾吧！關注我，獲取更多干貨～