LinkedHashMap
LinkedHashMap 是 HashMap 的有序版本。它在哈希表基础上额外维护一条双向链表，使遍历顺序可以保持为插入顺序或访问顺序。
它最常见的用途有两个：
- 需要像
HashMap一样快速查找，但遍历时保持稳定顺序。 - 基于访问顺序实现简单 LRU 缓存。
# 1. 核心特点
| 特点 | 说明 |
|---|---|
继承 HashMap | 哈希定位、扩容、冲突处理基本沿用 HashMap |
| 维护双向链表 | 额外记录节点顺序 |
| 默认插入顺序 | 遍历顺序等于首次插入顺序 |
| 可配置访问顺序 | accessOrder=true 时访问过的节点移动到尾部 |
允许 null key/value | 与 HashMap 类似 |
| 非线程安全 | 并发写入需要额外同步 |
示例：
Map<String, Integer> map = new LinkedHashMap<>();
map.put("B", 2);
map.put("A", 1);
map.put("C", 3);
System.out.println(map.keySet()); // [B, A, C]
同样的数据放入 HashMap，遍历顺序不应依赖。
# 2. 底层结构
LinkedHashMap = HashMap 桶结构 + 双向链表。
Hash 表视角：
table[0] -> Node
table[1] -> Node -> Node
table[2] -> null
顺序链表视角：
head <-> Entry1 <-> Entry2 <-> Entry3 <-> tail
节点比 HashMap.Node 多两个指针：
LinkedHashMap.Entry
├─ hash
├─ key
├─ value
├─ next 哈希桶链表指针
├─ before 顺序链表前驱
└─ after 顺序链表后继
两套链路解决两个问题：
| 链路 | 作用 |
|---|---|
next | 解决哈希桶冲突 |
before/after | 维护遍历顺序 |
# 3. 插入顺序
默认构造的 LinkedHashMap 使用插入顺序。
Map<String, Integer> map = new LinkedHashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("A", 100);
System.out.println(map.keySet()); // [A, B]
覆盖已有 key 的 value，不会改变该 key 的插入位置。
插入流程：
put(A)
│
├─ HashMap 桶中放入节点
└─ 顺序链表尾部追加节点
put(B)
│
├─ HashMap 桶中放入节点
└─ 顺序链表尾部追加节点
结构：
head -> A -> B -> tail
# 4. 访问顺序
构造函数第三个参数为 true 时，使用访问顺序。
LinkedHashMap<String, Integer> map =
new LinkedHashMap<>(16, 0.75f, true);
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);
map.get("A");
System.out.println(map.keySet()); // [B, C, A]
访问顺序逻辑：
访问前：
A -> B -> C
get(A) 后：
B -> C -> A
会触发访问顺序调整的方法包括 get、getOrDefault、put 命中已有 key 等。访问顺序模式下，读取也可能改变内部结构，因此迭代时要格外小心。
# 5. LRU 缓存
LinkedHashMap 可以通过访问顺序和 removeEldestEntry 实现简单 LRU。
public class LruCache<K, V> extends LinkedHashMap<K, V> {
private final int maxSize;
public LruCache(int maxSize) {
super(16, 0.75f, true);
this.maxSize = maxSize;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > maxSize;
}
}
使用：
Map<Integer, String> cache = new LruCache<>(3);
cache.put(1, "A");
cache.put(2, "B");
cache.put(3, "C");
cache.get(1);
cache.put(4, "D");
System.out.println(cache.keySet()); // [3, 1, 4]，2 被淘汰
LRU 过程：
初始：
1 -> 2 -> 3
get(1)：
2 -> 3 -> 1
put(4)，超过容量：
3 -> 1 -> 4
淘汰最老的 2
注意：这种 LRU 不是线程安全的，也不包含过期时间、权重、异步刷新等高级缓存能力。复杂缓存应使用成熟缓存库或专门组件。
# 6. removeEldestEntry 触发时机
removeEldestEntry 在插入新节点后被调用。
put 新元素
│
▼
插入 HashMap 桶
│
▼
追加到顺序链表尾部
│
▼
调用 removeEldestEntry
│
├─ true：删除 head
└─ false：保留
它不会在 get 时直接触发淘汰。
# 7. 与 HashMap 对比
| 对比项 | HashMap | LinkedHashMap |
|---|---|---|
| 查找性能 | 平均 O(1) | 平均 O(1)，略有链表维护开销 |
| 遍历顺序 | 不保证 | 插入顺序或访问顺序 |
| 内存占用 | 较低 | 更高，每个节点多 before/after |
| 典型场景 | 普通映射 | 有序映射、LRU |
如果不关心遍历顺序，使用 HashMap；如果输出结果、配置项、日志字段等需要稳定顺序，使用 LinkedHashMap。
# 8. 与 TreeMap 对比
| 对比项 | LinkedHashMap | TreeMap |
|---|---|---|
| 顺序依据 | 插入顺序或访问顺序 | key 的排序规则 |
| 底层结构 | 哈希表 + 双向链表 | 红黑树 |
| 查询复杂度 | 平均 O(1) | O(log n) |
| 范围查询 | 不支持 | 支持 |
| 典型场景 | 保持输入顺序 | 按 key 排序和区间操作 |
需要“原来怎么放，遍历就怎么出”时用 LinkedHashMap；需要“按大小排序”时用 TreeMap。
# 9. JSON 与接口返回顺序
很多接口返回 JSON 时，希望字段顺序或分组顺序稳定：
Map<String, Object> result = new LinkedHashMap<>();
result.put("code", 0);
result.put("message", "success");
result.put("data", data);
这样序列化时通常能按插入顺序输出。虽然 JSON 语义上对象字段不应依赖顺序，但稳定顺序有助于日志、调试和人工阅读。
# 10. 常见坑
# 10.1 误以为 HashMap 顺序稳定
即使某些小数据下 HashMap 看起来有顺序，也不要依赖。JDK 版本、容量、hash 分布、扩容都会影响遍历顺序。
# 10.2 访问顺序模式下 get 会改变顺序
LinkedHashMap<String, Integer> map =
new LinkedHashMap<>(16, 0.75f, true);
在这种模式下，get 会把节点移动到尾部，可能影响遍历和 fail-fast。
# 10.3 LRU 不是并发缓存
基于 LinkedHashMap 的 LRU 简洁，但没有并发控制。多线程使用需要同步，复杂场景应使用成熟缓存方案。
# Tips 快问快答
Q：LinkedHashMap 为什么有序？
A：它在 HashMap 桶结构之外维护了一条双向链表。
Q：默认顺序是什么？ A：默认是插入顺序。
Q：访问顺序怎么开启？
A：使用 new LinkedHashMap<>(capacity, loadFactor, true)。
Q：覆盖已有 key 会改变插入顺序吗？ A：插入顺序模式下不会改变原位置。
Q：访问顺序模式下 get 会改变结构吗？
A：会，访问的节点会移动到链表尾部。
Q：LinkedHashMap 查询复杂度是多少？
A：平均 O(1)，但比 HashMap 多一点链表维护开销。
Q：实现 LRU 的关键是什么？
A：开启访问顺序，并重写 removeEldestEntry。
Q：LRU 淘汰在什么时候触发？ A：通常在插入新元素后触发。
Q：需要按 key 排序应该用它吗？
A：不应该，按 key 排序用 TreeMap。
Q：LinkedHashMap 线程安全吗？
A：不安全，多线程访问需要同步或使用其他并发方案。