利用LinkedHashMap的访问顺序实现高效LRU缓存
深入理解LinkedHashMap的访问顺序机制
Java中的LinkedHashMap在继承HashMap的基础上，通过维护一个双向链表来保持元素的插入或访问顺序。其核心特性之一是accessOrder参数，用于控制节点的排序行为。
- 当
accessOrder = false（默认）时，按元素插入时间排序，最早插入的位于链表前端。 - 当
accessOrder = true时，每次对已存在键执行get或put操作后，该条目将被移动到链表末尾，体现"最近使用"的优先级。
这种行为使得LinkedHashMap天然适合作为LRU（Least Recently Used）缓存的基础结构。
典型使用示例
LinkedHashMap<Integer, String> lruCache = new LinkedHashMap<>(16, 0.75f, true);
lruCache.put(1, "First");
lruCache.put(2, "Second");
lruCache.get(1); // 触发访问重排
// 输出顺序：2 → 1（最新访问的在最后）
for (Map.Entry<Integer, String> entry : lruCache.entrySet()) {
System.out.println(entry.getKey() + " -> " + entry.getValue());
}
在此例中，调用get(1)后，键1对应的节点被移至链表尾部，表示它是最新的访问项。
内部机制与关键方法解析
当accessOrder启用时，所有访问操作都会触发链表更新。其核心逻辑由afterNodeAccess()方法实现：
void afterNodeAccess(Node<K,V> e) {
if (accessOrder && (tail != e)) {
unlink(e);
linkNodeLast(e);
}
}
该方法在每次访问命中时检查是否需要调整位置。若当前节点不是尾节点，则将其从原位置断开并插入链表末尾，从而保证最久未使用的元素始终位于头部。
| 操作 | 插入顺序模式 | 访问顺序模式 |
|---|---|---|
| 新增键 | 添加至末尾 | 添加至末尾 |
| 查询已有键 | 不变 | 移至末尾 |
| 更新键值 | 不变 | 移至末尾 |
这确保了链表头部永远指向最久未使用的条目，便于后续淘汰。
基于removeEldestEntry实现自动淘汰
LinkedHashMap提供了一个受保护的方法removeEldestEntry，可在每次插入新元素后被调用，决定是否移除最旧条目。
protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
return size() > MAX_SIZE;
}
通过重写此方法，可以定义自定义的淘汰策略。例如，当缓存大小超过预设上限时返回true，系统将自动删除链表头节点。
该机制仅在启用访问顺序模式下生效，且必须显式覆盖方法以启用淘汰逻辑。
与手动实现的性能对比
虽然LinkedHashMap提供了便捷的LRU支持，但在某些场景下仍需权衡：
| 特性 | LinkedHashMap | 手动双向链表 |
|---|---|---|
| 时间复杂度 | O(1) | O(1) |
| 内存占用 | 较高（封装开销） | 可控（可定制节点） |
| 扩展能力 | 有限 | 高（可添加额外字段） |
对于需要高度定制化的缓存系统（如支持权重、超时、统计等），建议自行构建包含哈希表和双向链表的结构。
实战应用：构建一个轻量级LRU缓存
以下是一个基于LinkedHashMap的简化实现：
public class SimpleLRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public SimpleLRUCache(int capacity) {
super(capacity, 0.75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity;
}
}
使用方式：
SimpleLRUCache<String, String> cache = new SimpleLRUCache<>(5);
cache.put("a", "value1");
cache.put("b", "value2");
cache.get("a"); // a 被标记为最近使用
cache.put("c", "value3"); // 容量满，淘汰最久未使用项
该实现简洁高效，适用于大多数通用缓存场景。
