#LinkedHashMap 实现 LRU
面试官问："LinkedHashMap 是什么？"
候选人小柳答："LinkedHashMap 是保证插入顺序的 HashMap。"
面试官追问："底层是怎么实现的？"
小柳说："用的是双向链表？"
面试官追问："怎么用它实现 LRU 缓存？"
小柳答不上来。
【面试官心理】 LinkedHashMap 的访问顺序特性是实现 LRU 缓存的关键。能说出 removeEldestEntry 重写和访问顺序维护的候选人，说明对数据结构的实际应用有理解。
#一、LinkedHashMap 底层结构 🔴
// LinkedHashMap 继承 HashMap
public class LinkedHashMap<K, V> extends HashMap<K, V> {
// 双向链表的头尾节点
transient LinkedHashMap.Entry<K, V> head;
transient LinkedHashMap.Entry<K, V> tail;
// 访问顺序模式（默认 false：插入顺序）
final boolean accessOrder;
// 节点继承 HashMap.Node，多了前后指针
static class Entry<K, V> extends HashMap.Node<K, V> {
LinkedHashMap.Entry<K, V> before; // 前驱
LinkedHashMap.Entry<K, V> after; // 后继
}
}#1.1 数据结构图
LinkedHashMap 结构：
┌─────────────────────────────────────────────────────────┐
│ HashMap 部分 │
│ ┌─────────┬─────────┬─────────┬─────────┐ │
│ │ table[] │ size │ modCount│ ... │ │
│ └────┬────┴────┬────┴─────────┴─────────┘ │
│ │ │ │
│ ▼ ▼ │
│ ┌─────────┐ ┌─────────┐ ┌─────────┐ │
│ │ Node(A) │ │ Node(B) │ │ Node(C) │ ← 哈希桶数组 │
│ └────┬────┘ └────┬────┘ └────┬────┘ │
└───────┼───────────┼───────────┼───────────────────────────┘
│ │ │
▼ ▼ ▼
┌─────────────────────────────────────┐
│ 双向链表（维护顺序） │
│ head ←→ [A] ←→ [B] ←→ [C] ← tail │
└─────────────────────────────────────┘#二、两种顺序模式 🔴
// 插入顺序（默认）
Map<String, Integer> map1 = new LinkedHashMap<>();
map1.put("a", 1);
map1.put("b", 2);
map1.put("c", 3);
// 遍历顺序：a → b → c（插入顺序）
// 访问顺序
Map<String, Integer> map2 = new LinkedHashMap<>(16, 0.75f, true);
map2.put("a", 1);
map2.put("b", 2);
map2.put("c", 3);
map2.get("a"); // 访问 a
map2.get("b"); // 访问 b
// 遍历顺序：c → a → b
// 访问后，该节点移到链表尾部#三、LRU 缓存实现 🔴
#3.1 重写 removeEldestEntry
class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int maxCapacity;
public LRUCache(int maxCapacity) {
super(16, 0.75f, true); // 访问顺序模式
this.maxCapacity = maxCapacity;
}
// 当 size > maxCapacity 时，返回 true 删除最老的元素
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxCapacity;
}
}
// 使用
LRUCache<String, Integer> cache = new LRUCache<>(3);
cache.put("a", 1);
cache.put("b", 2);
cache.put("c", 3);
cache.put("d", 4); // 自动删除 "a"（最老的）
cache.get("b"); // 访问 b，b 移到链表尾部
cache.put("e", 5); // 自动删除 "c"（最老的）
// 缓存内容：b, d, e#3.2 完整实现
import java.util.*;
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;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
// 安全的 get：不影响缓存顺序
public V get(K key) {
return super.get(key);
}
// 安全的 put
public V put(K key, V value) {
return super.put(key, value);
}
}#四、访问顺序的工作原理 🟡
// LinkedHashMap 的 get 方法
public V get(Object key) {
Node<K, V> e;
if ((e = getNode(hash(key), key)) == null) return null;
// 如果是访问顺序模式，移动到链表尾部
if (accessOrder)
afterNodeAccess(e);
return e.value;
}
// afterNodeAccess 方法
void afterNodeAccess(Node<K, V> e) {
LinkedHashMap.Entry<K, V> last;
if (accessOrder && (last = tail) != e) {
// 将节点移到链表尾部
LinkedHashMap.Entry<K, V> p = (LinkedHashMap.Entry<K, V>) e;
// ... 链表调整代码
tail = p;
}
}#五、与 HashMap 的对比 🟡
| 维度 | HashMap | LinkedHashMap |
|---|---|---|
| 底层结构 | 哈希桶 + 链表/红黑树 | HashMap + 双向链表 |
| 遍历顺序 | 无固定顺序 | 插入顺序或访问顺序 |
| 额外开销 | 无 | 每个节点多两个指针（before/after） |
| 适用场景 | 普通 kv 存储 | 需要顺序、LRU 缓存 |
#六、追问升级
面试官："为什么 LinkedHashMap 的 removeEldestEntry 在 put 后调用而不是 get 后？"
// 因为 get 不一定意味着"最近使用"
// 只有 put 才会增加元素，可能触发容量超限
// get 只是调整访问顺序，不会改变 size
// 如果要在 get 时删除，可以用 removeEldestEntry 配合手动调用
// 但这不是标准用法