LinkedHashSet：插入顺序的代价
LinkedHashSet 是什么
一句话：HashSet + 插入顺序。
它继承自 HashSet，但额外维护了一条双向链表，记录元素的插入顺序。所以它既有 HashSet 的 O(1) 性能，又保持了插入顺序。
java
public class LinkedHashSet<E> extends HashSet<E> {
// 关键：accessOrder = false → 维护插入顺序
// 如果 accessOrder = true → 维护访问顺序（LRU 缓存）
public LinkedHashSet() {
super(16, .75f, true); // 调用 HashSet 的特殊构造函数
}
}第三个参数 true 启用 LinkedHashMap 作为底层存储，而不是普通的 HashMap。
为什么需要双向链表
HashSet 的遍历顺序是 hashCode 分布决定的——无序。
如果想要「插入顺序」，需要额外的数据结构来记录：
┌─────────────────────────────────────────────────────────┐
│ HashSet 的存储（无序） │
├─────────────────────────────────────────────────────────┤
│ │
│ bucket[2] → "A" │
│ bucket[5] → "C" → "B" │
│ bucket[8] → "D" │
│ │
│ 遍历顺序：取决于桶的内部顺序，可能是 A, C, B, D │
│ │
└─────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────┐
│ LinkedHashSet 的存储（有序） │
├─────────────────────────────────────────────────────────┤
│ │
│ HashMap 结构（去重）： │
│ bucket[2] → "A" │
│ bucket[5] → "C" │
│ bucket[8] → "D" │
│ │
│ 双向链表结构（顺序）： │
│ head ↔ "A" ↔ "C" ↔ "B" ↔ "D" ↔ tail │
│ │
│ 遍历顺序：按链表，A, C, B, D │
│ │
└─────────────────────────────────────────────────────────┘每个节点同时存在于两个结构中：桶里（用于哈希查找）和链表里（用于顺序遍历）。
LinkedHashSet vs HashSet
java
Set<String> hash = new HashSet<>();
Set<String> linked = new LinkedHashSet<>();
List.of("c", "a", "b").forEach(s -> {
hash.add(s);
linked.add(s);
});
System.out.println("HashSet: " + hash); // 无序，如 [a, b, c]
System.out.println("LinkedHashSet: " + linked); // [c, a, b] 严格按插入顺序| 特性 | HashSet | LinkedHashSet |
|---|---|---|
| 去重 | ✅ | ✅ |
| 插入顺序 | ❌ | ✅ |
| add/contains 性能 | O(1) | O(1)（稍慢一点） |
| 遍历性能 | O(n) | O(n) |
| 内存占用 | 较低 | 较高（额外链表） |
| null 支持 | ✅ 一个 null | ✅ 一个 null |
LinkedHashSet 的两种模式
插入顺序（默认）
java
LinkedHashSet<String> insertOrder = new LinkedHashSet<>();
insertOrder.add("first");
insertOrder.add("second");
insertOrder.add("third");
System.out.println(insertOrder); // [first, second, third]访问顺序（LRU 缓存模式）
传入 accessOrder = true 后，访问元素会把元素移到链表末尾：
java
LinkedHashSet<String> accessOrder = new LinkedHashSet<>(16, .75f, true);
accessOrder.add("A");
accessOrder.add("B");
accessOrder.add("C");
accessOrder.contains("A"); // 访问 A
accessOrder.contains("B"); // 访问 B
System.out.println(accessOrder);
// 输出：[C, A, B] ← 访问过的移到了后面
// 最前面的是最久未访问的这种模式常用于 LRU 缓存实现：
java
// 简单 LRU 缓存示例
LinkedHashSet<Integer> cache = new LinkedHashSet<>(3, .75f, true) {
@Override
protected boolean removeEldestEntry eldest) {
return size() > 3; // 超过 3 个元素就删除最老的
}
};
cache.add(1);
cache.add(2);
cache.add(3);
cache.add(1); // 重新访问 1
cache.add(4); // 添加 4，此时 size > 3，最老的（2）被删除
System.out.println(cache); // [1, 3, 4]性能代价
LinkedHashSet 比 HashSet 慢一点，因为它要多维护一条链表：
java
// 内存开销对比
HashSet<Integer> hash = new HashSet<>();
LinkedHashSet<Integer> linked = new LinkedHashSet<>();
// 添加 10 万元素后
// hash：约 2.4 MB
// linked：约 4.8 MB（双向链表指针额外开销）| 操作 | HashSet | LinkedHashSet |
|---|---|---|
| add | O(1) | O(1)（稍慢） |
| remove | O(1) | O(1)（稍慢） |
| contains | O(1) | O(1) |
| 遍历 | O(n) | O(n)（按插入顺序） |
典型应用场景
场景 1：去重且保持顺序
java
// 去除重复但保留第一次出现的顺序
List<String> raw = Arrays.asList("b", "a", "c", "a", "d", "b");
Set<String> unique = new LinkedHashSet<>(raw);
System.out.println(unique); // [b, a, c, d]场景 2：记录访问顺序
java
// 记录用户访问历史（最近访问的放后面）
LinkedHashSet<String> history = new LinkedHashSet<>();
history.add("page1");
history.add("page2");
history.add("page3");
history.add("page1"); // 重新访问 page1
System.out.println(history); // [page2, page3, page1]场景 3：LRU 缓存
java
// 基于 LinkedHashSet 的 LRU 缓存
class LRUCache<K> {
private final int capacity;
private final LinkedHashMap<K, V> map;
public LRUCache(int capacity) {
this.capacity = capacity;
this.map = new LinkedHashMap<>(capacity, .75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > LRUCache.this.capacity;
}
};
}
public V get(K key) { return map.get(key); }
public void put(K key, V value) { map.put(key, value); }
}总结
| 要点 | 说明 |
|---|---|
| 本质 | HashSet + 双向链表 |
| 核心能力 | 去重 + 保持插入顺序 |
| 两种模式 | 插入顺序（默认）/ 访问顺序（LRU） |
| 性能代价 | 比 HashSet 慢一点，内存多一倍 |
| 适用场景 | 去重 + 保序、LRU 缓存、访问历史 |
一句话：LinkedHashSet 用额外的内存换来了顺序——如果你需要插入顺序，它是最佳选择。