LinkedHashSet/LinkedHashMap

1. 什么是 LinkedHashSet 和 LinkedHashMap？

在 Java 标准库中，Set 和 Map 有多种实现。最常见的是 HashSet 和 HashMap。这些结构通过哈希提供对元素的快速访问，但 在遍历元素时不保证任何顺序。当遍历顺序很重要时——LinkedHashSet 和 LinkedHashMap 就派上用场了。

• LinkedHashSet 是一种会记住元素插入顺序的 Set。
• LinkedHashMap 是一种会记住键–值对插入顺序（或可选的访问顺序）的 Map。

它们在内部与“普通”的 HashSet/HashMap 类似，但额外维护了一个双向链表来记录元素顺序。

2. 插入顺序与访问顺序

插入顺序

默认情况下，LinkedHashSet 和 LinkedHashMap 保证在遍历时（for-each/迭代器）按元素被添加的顺序返回。

Set<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");
for (String s : set) {
    System.out.println(s);
}
// 输出: A B C

Map<Integer, String> map = new LinkedHashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");
for (Integer key : map.keySet()) {
    System.out.println(key + " -> " + map.get(key));
}
// 输出: 1 -> one, 2 -> two, 3 -> three

访问顺序（仅适用于 LinkedHashMap）

LinkedHashMap 支持按 最近访问 排序（access order）。在创建时将构造函数的第三个参数设为 true，则每次访问元素（get/put）时，它都会被移动到链表末尾。

Map<Integer, String> lruMap = new LinkedHashMap<>(16, 0.75f, true);
lruMap.put(1, "one");
lruMap.put(2, "two");
lruMap.put(3, "three");

lruMap.get(2); // 访问键 2

for (Integer key : lruMap.keySet()) {
    System.out.println(key);
}
// 输出: 1 3 2（2 在最后，因为刚被访问）

通过 removeEldestEntry 实现 LRU 缓存

LinkedHashMap 的一大“亮点”是可以轻松实现 LRU 缓存（Least Recently Used，最近最少使用）。只需重写方法 removeEldestEntry(Map.Entry<K,V> eldest)：当其返回 true 时，在插入新元素时会删除最“老”的元素。

class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxSize;

    public LRUCache(int maxSize) {
        super(maxSize, 0.75f, true); // true — 按访问顺序
        this.maxSize = maxSize;
    }

    @Override
    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return size() > maxSize;
    }
}

// 用法:
LRUCache<Integer, String> cache = new LRUCache<>(3);
cache.put(1, "one");
cache.put(2, "two");
cache.put(3, "three");
cache.get(1); // 将 1 变为“最新”
cache.put(4, "four"); // 将会移除 2（最旧）
System.out.println(cache.keySet()); // [3, 1, 4]

3. 内存与性能成本: LinkedHashSet/LinkedHashMap vs HashSet/HashMap

内部机制

内部几乎与普通的 HashSet/HashMap 相同，但每个元素还保存在一个双向链表中。这个额外的结构用来“记住”插入/访问顺序。

内存开销

由于每个节点都包含 prev/next 指针，会占用更多内存。对于数百万个元素时差异明显；对于常见任务，这是为获得确定性顺序而付出的合理代价。

性能开销

基本的插入/查找/删除操作仍然是摊还 O(1)。遍历会因为链表的维护稍慢一些，但在大多数情况下差异很小。而“删除最旧元素”（LRU）这一场景非常高效，因为“最老”的元素始终位于链表头部。

总结：如果顺序重要——请选择 LinkedHashSet/LinkedHashMap。如果想节省内存且不需要顺序——用 HashSet/HashMap 即可。

4. 缓存、确定性输出、稳定测试

缓存（LRU）

LinkedHashMap 是实现有限大小且能自动删除“旧”元素的缓存的理想基础。它常用于各类库/框架，以及文件、图像、计算结果等场景。

确定性输出

在报告、导出、序列化等需要可预测数据呈现的场景中，请使用 LinkedHashSet/LinkedHashMap。对测试尤为重要——不同次运行之间顺序不会“乱跳”。

稳定的测试

在单元测试中，常需要比较期望的集合与实际结果。如果顺序不受保证，测试可能会“抖动”。使用带链接的实现——确定性可以带来稳定性。

示例: 比较 HashMap 和 LinkedHashMap

Map<Integer, String> hashMap = new HashMap<>();
Map<Integer, String> linkedMap = new LinkedHashMap<>();

for (int i = 1; i <= 5; i++) {
    hashMap.put(i, "val" + i);
    linkedMap.put(i, "val" + i);
}

System.out.println(hashMap.keySet());   // 顺序可能是任意的！
System.out.println(linkedMap.keySet()); // 始终为 1, 2, 3, 4, 5

5. 用于队列时的 LinkedList vs ArrayDeque

LinkedList

• 实现了接口 List、Deque、Queue。
• 双向链表：在头尾插入/删除很快。
• 可用作队列（FIFO）、栈（LIFO）、双端队列。

ArrayDeque

• 实现了 Deque、Queue（但不是 List）。
• 基于数组，会自动扩容。
• 在队列/栈操作上通常比 LinkedList 更快，开销更小。
• 不支持元素 null。

何时使用哪一个？

• 队列和栈——几乎总是 ArrayDeque。
• 中间位置有大量插入/删除且还需要列表特性——LinkedList。
• 带顺序的 Set/Map——LinkedHashSet/LinkedHashMap。

示例: 任务队列

Queue<String> queue = new ArrayDeque<>();
queue.add("task1");
queue.add("task2");
System.out.println(queue.poll()); // task1

示例: 栈

Deque<String> stack = new ArrayDeque<>();
stack.push("first");
stack.push("second");
System.out.println(stack.pop()); // second

结论:
— 对于队列和栈——ArrayDeque。
— 对于在中间频繁插入的列表——LinkedList。
— 对于 Set/Map 且需要顺序——LinkedHashSet/LinkedHashMap。

6. 使用 LinkedHashSet/LinkedHashMap 时的常见错误

错误 №1：以为 HashSet/HashMap 会保留顺序。
HashSet/HashMap 不保证顺序。如果顺序很重要——请使用 LinkedHashSet/LinkedHashMap。

错误 №2：用 LinkedHashMap 做缓存却不重写 removeEldestEntry。
要实现 LRU 必须重写 removeEldestEntry，否则映射会无限增长。

错误 №3：不必要地用 LinkedList 实现队列/栈。
在大多数情况下 ArrayDeque 更快且更省资源。

错误 №4：指望 LinkedHashMap 会排序。
LinkedHashMap 只保留插入/访问顺序，不会按键排序。需要排序时请用 TreeMap。

错误 №5：向 ArrayDeque 添加 null。
ArrayDeque 不支持 null 元素——会抛出 NullPointerException。

错误 №6：比较集合时忽略顺序差异。
将 LinkedHashSet/LinkedHashMap 与普通的 HashSet/HashMap 比较时，要考虑元素顺序的不同。