LinkedHashMap：插入顺序的 HashMap
LinkedHashMap 是什么
一句话：HashMap + 双向链表。
它继承自 HashMap，但额外维护了一条双向链表，记录每个 key 的插入顺序（或者访问顺序）。所以它既有 HashMap 的 O(1) 性能，又有顺序。
java
public class LinkedHashMap<K, V> extends HashMap<K, V> {
// 双向链表的头尾
transient LinkedHashMap.Entry<K, V> head;
transient LinkedHashMap.Entry<K, V> tail;
// true = 访问顺序（LRU），false = 插入顺序（默认）
final boolean accessOrder;
}为什么需要双向链表
HashMap 的遍历顺序是 hashCode 分布决定的——无序。
如果想要「插入顺序」，需要额外的数据结构来记录：
┌─────────────────────────────────────────────────────────┐
│ HashMap 的存储（无序） │
├─────────────────────────────────────────────────────────┤
│ │
│ bucket[2] → "C" │
│ bucket[5] → "A" → "B" │
│ bucket[8] → "D" │
│ │
│ 遍历：取决于桶的内部顺序，A, C, B, D 或其他顺序 │
│ │
└─────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────┐
│ LinkedHashMap 的存储（有序） │
├─────────────────────────────────────────────────────────┤
│ │
│ HashMap 结构（O(1) 查找）： │
│ bucket[2] → "C" │
│ bucket[5] → "A" │
│ bucket[8] → "D" │
│ │
│ 双向链表结构（顺序）： │
│ head ↔ "A" ↔ "C" ↔ "B" ↔ "D" ↔ tail │
│ │
│ 遍历：按链表顺序 → A, C, B, D │
│ │
└─────────────────────────────────────────────────────────┘每个节点同时存在于两个结构中：桶里（用于哈希查找）和链表里（用于顺序遍历）。
LinkedHashMap vs HashMap
java
Map<String, Integer> hash = new HashMap<>();
Map<String, Integer> linked = new LinkedHashMap<>();
hash.put("c", 3); hash.put("a", 1); hash.put("b", 2);
linked.put("c", 3); linked.put("a", 1); linked.put("b", 2);
System.out.println("HashMap: " + hash); // 无序，如 {a=1, b=2, c=3}
System.out.println("LinkedHashMap: " + linked); // {c=3, a=1, b=2} 严格按插入顺序| 特性 | HashMap | LinkedHashMap |
|---|---|---|
| 去重 | ✅ | ✅ |
| 插入顺序 | ❌ | ✅ |
| get/put 性能 | O(1) | O(1)（稍慢一点） |
| 遍历性能 | O(n) | O(n)（按插入顺序） |
| 内存占用 | 较低 | 较高（额外链表指针） |
| null key/value | ✅ | ✅ |
两种模式
插入顺序（默认）
java
LinkedHashMap<String, Integer> insertOrder = new LinkedHashMap<>();
insertOrder.put("first", 1);
insertOrder.put("second", 2);
insertOrder.put("third", 3);
System.out.println(insertOrder); // {first=1, second=2, third=3}访问顺序（LRU 缓存模式）
传入 accessOrder = true 后，每次 get 或 put 都会把该节点移到链表末尾：
java
LinkedHashMap<String, Integer> accessOrder = new LinkedHashMap<>(16, .75f, true);
accessOrder.put("a", 1);
accessOrder.put("b", 2);
accessOrder.put("c", 3);
System.out.println("初始: " + accessOrder);
// {a=1, b=2, c=3}
accessOrder.get("a"); // 访问 a
System.out.println("访问后: " + accessOrder);
// {b=2, c=3, a=1} ← a 被移到最后
accessOrder.get("b"); // 访问 b
System.out.println("再次访问: " + accessOrder);
// {c=3, a=1, b=2} ← b 被移到最后链表头部是最久未访问的，尾部是最近访问的。
经典应用：LRU 缓存
利用 removeEldestEntry 实现自动淘汰最老元素的缓存：
java
public class LRUCache<K, V> extends LinkedHashMap<K, V> {
private final int capacity;
public LRUCache(int capacity) {
// accessOrder = true 启用访问顺序
// removeEldestEntry 在 put 后自动调用
super(16, .75f, true);
this.capacity = capacity;
}
@Override
protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
return size() > capacity; // 超过容量就删除最老的
}
}使用示例
java
LRUCache<String, String> cache = new LRUCache<>(3);
cache.put("A", "a");
cache.put("B", "b");
cache.put("C", "c");
System.out.println("初始: " + cache); // {A=a, B=b, C=c}
cache.get("A"); // 访问 A，A 移到最后
System.out.println("访问 A 后: " + cache); // {B=b, C=c, A=a}
cache.put("D", "d"); // 添加 D，容量超了
System.out.println("添加 D 后: " + cache); // {C=c, A=a, D=d}
// B 被淘汰了（最久未访问）典型应用场景
场景 1：去除重复但保持顺序
java
// 去除重复 URL，保留第一次出现的顺序
List<String> urls = Arrays.asList(
"page1.html", "page2.html", "page1.html", "page3.html", "page2.html"
);
Map<String, String> uniqueUrls = new LinkedHashMap<>();
for (String url : urls) {
uniqueUrls.putIfAbsent(url, url); // 只保留第一次出现的
}
System.out.println(uniqueUrls.keySet());
// [page1.html, page2.html, page3.html]场景 2：FIFO 队列
java
LinkedHashMap<String, String> fifo = new LinkedHashMap<>(16, .75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > 5; // 最多保留 5 个
}
};
// 每次添加超过 5 个，自动删除最老的场景 3：用户行为记录
java
// 记录用户最近访问的 10 个页面
LinkedHashMap<String, LocalDateTime> recentPages =
new LinkedHashMap<>(16, .75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > 10;
}
};
recentPages.put(page, LocalDateTime.now());
// 自动保留最近 10 个页面性能代价
LinkedHashMap 比 HashMap 稍慢，因为每次插入/删除都要维护双向链表：
java
// 内存开销对比（10 万元素）
HashMap<Integer, Integer> hash = new HashMap<>();
LinkedHashMap<Integer, Integer> linked = new LinkedHashMap<>();
// hash：约 4.8 MB
// linked：约 6.4 MB（双向链表指针额外开销）| 操作 | HashMap | LinkedHashMap |
|---|---|---|
| get | O(1) | O(1) |
| put | O(1) | O(1)（稍慢） |
| remove | O(1) | O(1)（稍慢） |
| 遍历 | O(n)（无序） | O(n)（按顺序） |
LinkedHashSet 和 LinkedHashMap 的关系
LinkedHashSet 的底层就是 LinkedHashMap：
java
public class LinkedHashSet<E> extends HashSet<E> {
public LinkedHashSet() {
// 底层创建 LinkedHashMap
super(16, .75f, true);
}
}所以 LinkedHashSet 的有序性原理和 LinkedHashMap 完全一样——都是靠双向链表维持顺序。
总结
| 要点 | 说明 |
|---|---|
| 本质 | HashMap + 双向链表 |
| 核心能力 | 去重 + 保持插入顺序 / 访问顺序 |
| 两种模式 | 插入顺序（默认）/ 访问顺序（LRU） |
| LRU 实现 | accessOrder = true + removeEldestEntry |
| 性能代价 | 比 HashMap 稍慢，内存多约 30% |
| 适用场景 | 去重保序、缓存、按顺序遍历 |
一句话：LinkedHashMap 是 HashMap 的「有序版本」——用约 30% 的额外内存，换来了遍历的有序性。