【面试场景题】通过LinkedHashMap来实现LRU与LFU

一、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更精准但实现复杂，适合对访问频率敏感的场景。