一、LRU與LFU的概念

1. LRU（Least Recently Used，最近最少使用）

LRU是一種緩存淘汰策略，核心思想是：當緩存空間滿時，優先淘汰最久未被訪問的元素。

• 基于“最近使用的元素在未來更可能被再次使用”的假設。
• 例如：緩存容量為3，訪問順序為A→B→C→A→D，當加入D時緩存滿，最久未被訪問的是B，因此淘汰B。

2. LFU（Least Frequently Used，最不經常使用）

LFU是另一種緩存淘汰策略，核心思想是：當緩存空間滿時，優先淘汰訪問次數最少的元素；若訪問次數相同，則淘汰最久未被訪問的元素。

• 基于“使用頻率高的元素在未來更可能被再次使用”的假設。
• 例如：緩存容量為3，訪問次數：A(3次)、B(2次)、C(2次)（C比B更久未訪問），加入D時，B和C次數最少，淘汰更久未訪問的C。

二、LinkedHashMap的特性

LinkedHashMap 是 HashMap 的子類，其核心特性是維護了一個雙向鏈表，記錄Entry的插入順序或訪問順序，這為實現LRU提供了天然支持。

• 構造函數參數 accessOrder：true 表示按訪問順序排序（每次get/put操作會將元素移到鏈表末尾）；false（默認）表示按插入順序排序。
• 方法 removeEldestEntry(Map.Entry<K,V> eldest)：當此方法返回 true 時，LinkedHashMap 會自動刪除最老的Entry（鏈表頭部元素）。

三、用LinkedHashMap實現LRU

利用 LinkedHashMap 的 accessOrder=true 特性（訪問順序排序），配合重寫 removeEldestEntry 方法（當容量超限則刪除最老元素），即可實現LRU。

實現代碼：

import java.util.LinkedHashMap;
import java.util.Map;public class LRUCache<K, V> extends LinkedHashMap<K, V> {private final int capacity; // 緩存容量// 構造函數：指定容量、負載因子、訪問順序模式public LRUCache(int capacity) {super(capacity, 0.75f, true); // accessOrder=true：按訪問順序排序this.capacity = capacity;}// 重寫此方法：當Entry數量超過容量時，返回true，自動刪除最老元素@Overrideprotected boolean removeEldestEntry(Map.Entry<K, V> eldest) {return size() > capacity;}// 測試public static void main(String[] args) {LRUCache<Integer, String> cache = new LRUCache<>(3);cache.put(1, "A");cache.put(2, "B");cache.put(3, "C");System.out.println(cache); // {1=A, 2=B, 3=C}（插入順序）cache.get(1); // 訪問1，移到末尾System.out.println(cache); // {2=B, 3=C, 1=A}cache.put(4, "D"); // 容量超限，刪除最老元素2System.out.println(cache); // {3=C, 1=A, 4=D}}
}

原理說明：

• accessOrder=true 確保每次訪問（get 或 put）的元素被移到鏈表末尾（成為“最新”元素）。
• 鏈表頭部始終是“最久未被訪問”的元素，當 size() > capacity 時，removeEldestEntry 返回 true，自動刪除頭部元素，實現LRU淘汰。

四、用LinkedHashMap實現LFU

LFU需要跟蹤元素的訪問次數，以及同次數下的最近訪問時間，LinkedHashMap 本身不直接支持頻率排序，需結合額外結構輔助實現：

1. 用 Map<K, Integer> 記錄每個key的訪問次數（頻率）。
2. 用 Map<Integer, LinkedHashMap<K, V>> 按頻率分組：key為頻率，value為該頻率下的元素（按訪問順序排序，用于同頻率下淘汰最久未訪問元素）。
3. 維護一個變量記錄當前最小頻率，方便快速找到需淘汰的組。

實現代碼：

import java.util.*;public class LFUCache<K, V> {private final int capacity; // 緩存容量private final Map<K, Integer> keyToFreq; // 記錄key的訪問次數private final Map<Integer, LinkedHashMap<K, V>> freqToEntries; // 按頻率分組，每組內按訪問順序排序private int minFreq; // 當前最小頻率public LFUCache(int capacity) {this.capacity = capacity;this.keyToFreq = new HashMap<>();this.freqToEntries = new HashMap<>();this.minFreq = 0;}// 獲取元素public V get(K key) {if (!keyToFreq.containsKey(key)) {return null;}// 1. 增加訪問頻率int oldFreq = keyToFreq.get(key);int newFreq = oldFreq + 1;keyToFreq.put(key, newFreq);// 2. 從舊頻率組中移除，加入新頻率組LinkedHashMap<K, V> oldEntries = freqToEntries.get(oldFreq);V value = oldEntries.remove(key);// 若舊頻率組為空，且是最小頻率，更新minFreqif (oldEntries.isEmpty()) {freqToEntries.remove(oldFreq);if (oldFreq == minFreq) {minFreq = newFreq;}}// 新頻率組不存在則創建（按訪問順序排序）freqToEntries.computeIfAbsent(newFreq, k -> new LinkedHashMap<>(capacity, 0.75f, true)).put(key, value);return value;}// 放入元素public void put(K key, V value) {if (capacity <= 0) return;// 若key已存在，先更新值并觸發get（更新頻率）if (keyToFreq.containsKey(key)) {freqToEntries.get(keyToFreq.get(key)).put(key, value); // 更新值get(key); // 觸發頻率更新return;}// 若緩存滿，淘汰最不經常使用的元素（最小頻率組中最老的）if (keyToFreq.size() >= capacity) {LinkedHashMap<K, V> minFreqEntries = freqToEntries.get(minFreq);// 移除最小頻率組中最老的元素（鏈表頭部）K eldestKey = minFreqEntries.keySet().iterator().next();minFreqEntries.remove(eldestKey);keyToFreq.remove(eldestKey);// 若最小頻率組為空，移除該組if (minFreqEntries.isEmpty()) {freqToEntries.remove(minFreq);}}// 新增元素：頻率為1，加入頻率1的組int newFreq = 1;keyToFreq.put(key, newFreq);freqToEntries.computeIfAbsent(newFreq, k -> new LinkedHashMap<>(capacity, 0.75f, true)).put(key, value);minFreq = newFreq; // 新元素頻率為1，最小頻率更新為1}// 測試public static void main(String[] args) {LFUCache<Integer, String> cache = new LFUCache<>(3);cache.put(1, "A"); // 頻率：1→{1:A}，min=1cache.put(2, "B"); // 頻率：1→{1:A,2:B}，min=1cache.put(3, "C"); // 頻率：1→{1:A,2:B,3:C}，min=1cache.get(1); // 1的頻率變為2，min仍為1cache.get(1); // 1的頻率變為3，min仍為1cache.put(4, "D"); // 緩存滿，淘汰min=1中最老的2（1和2都在頻率1組，2更早未訪問）System.out.println(cache.get(2)); // null（已被淘汰）System.out.println(cache.get(1)); // A（存在）}
}

原理說明：

• 頻率跟蹤：keyToFreq 記錄每個key的訪問次數，每次 get/put 會更新頻率。
• 分組管理：freqToEntries 按頻率分組，每組用 LinkedHashMap（accessOrder=true）記錄元素，確保同頻率下最久未訪問的元素在鏈表頭部，便于淘汰。
• 淘汰邏輯：當緩存滿時，找到最小頻率 minFreq，從對應組中移除最老元素（鏈表頭部），若組為空則移除該組并更新 minFreq。

總結

策略	核心邏輯	LinkedHashMap的作用	實現復雜度
LRU	淘汰最久未訪問元素	利用 accessOrder=true 維護訪問順序，重寫 removeEldestEntry 實現自動淘汰	簡單
LFU	淘汰訪問次數最少（同次數則最久未訪問）的元素	作為頻率分組內的容器，維護同頻率元素的訪問順序	較復雜（需額外結構跟蹤頻率）

LRU實現簡單、性能好，適合大多數場景；LFU更精準但實現復雜，適合對訪問頻率敏感的場景。