LinkedHashSet

ℹ️定位说明

Set 系列第 2 篇。HashSet 加一条双向链表记住插入顺序——"去重且保序"的唯一解。底层是 LinkedHashMap，读法同源。

LinkedHashSet 是 Java 集合框架中 Set 接口的一个实现类，它继承自 HashSet 并通过 哈希表 + 双向链表 维护元素的插入顺序，兼具高效性与有序性。

一、核心原理与数据结构

1. 底层实现

基于 LinkedHashMap：

LinkedHashSet 继承自 HashSet，但通过构造函数指定使用 LinkedHashMap 作为底层存储。关键源码如下：

// LinkedHashSet 构造函数
public LinkedHashSet() {
    super(16, .75f, true); // 调用父类 HashSet 的构造函数
}

// HashSet 中对应的构造函数
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

这里的 dummy 参数仅用于区分不同构造函数，实际创建的是 LinkedHashMap 实例。

双向链表维护顺序：

LinkedHashMap 在 HashMap 的基础上增加了双向链表，每个节点（Entry）包含前驱（before）和后继（after）指针。源码中的节点定义：

// LinkedHashMap 中的 Entry 节点继承自 HashMap.Node
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 双向链表指针
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

链表的头尾节点由 LinkedHashMap 的 head 和 tail 维护：

// LinkedHashMap 维护双向链表的头尾节点
transient LinkedHashMap.Entry<K,V> head; // 链表头节点
transient LinkedHashMap.Entry<K,V> tail; // 链表尾节点

2. 插入与遍历逻辑（源码详解）

插入元素：

LinkedHashSet 的插入逻辑继承自 HashSet，最终调用 LinkedHashMap 的 put() 方法。关键步骤：

哈希定位：通过 hashCode() 计算哈希值，确定存储桶位置。
节点插入：若发生哈希冲突，新节点会被添加到链表尾部（而非随机位置）。
链表维护：插入成功后，LinkedHashMap 会将新节点链接到双向链表的尾部。

源码片段（LinkedHashMap 的节点插入逻辑）：

// LinkedHashMap 重写了 newNode() 方法，用于创建带双向链表指针的节点
Node<K,V> newNode(int hash, K key, V value, Node<K,V> e) {
    LinkedHashMap.Entry<K,V> p =
        new LinkedHashMap.Entry<K,V>(hash, key, value, e);
    linkNodeLast(p); // 将新节点链接到链表尾部
    return p;
}

// 将节点链接到链表尾部
private void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
    LinkedHashMap.Entry<K,V> last = tail;
    tail = p;
    if (last == null)
        head = p; // 若链表为空，新节点既是头节点也是尾节点
    else {
        p.before = last; // 新节点的前驱指向原尾节点
        last.after = p;  // 原尾节点的后继指向新节点
    }
}

遍历元素：

LinkedHashSet 的迭代器直接沿双向链表顺序访问，而非按哈希表的桶顺序。源码如下：

// LinkedHashMap 的迭代器实现
public final Iterator<K> iterator() {
    return new LinkedKeyIterator();
}

// 链表迭代器，直接遍历双向链表
final class LinkedKeyIterator extends LinkedHashIterator
    implements Iterator<K> {
    public final K next() { return nextNode().getKey(); }
}

// LinkedHashIterator 的核心逻辑
abstract class LinkedHashIterator {
    LinkedHashMap.Entry<K,V> next; // 下一个节点
    LinkedHashMap.Entry<K,V> current; // 当前节点

    LinkedHashIterator() {
        next = head; // 从链表头开始
        expectedModCount = modCount;
        current = null;
    }

    final LinkedHashMap.Entry<K,V> nextNode() {
        LinkedHashMap.Entry<K,V> e = next;
        if (e == null)
            throw new NoSuchElementException();
        current = e;
        next = e.after; // 直接通过后继指针访问下一个节点
        return e;
    }
}

关键点：

迭代器初始化时指向链表头节点（head）。
每次调用 next() 时，直接通过 after 指针访问下一个节点，保证按插入顺序遍历。

3. 插入顺序演示

LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("B");
set.add("A");
set.add("C");

// 遍历结果与插入顺序一致
for (String s : set) {
    System.out.print(s + " "); // 输出：B A C
}

底层链表结构示意图：

head → B ↔ A ↔ C ← tail

遍历时直接沿链表顺序（B → A → C）访问，与插入顺序完全一致。

4. 与 LinkedHashMap 的联动

LinkedHashMap 的 accessOrder 参数控制链表维护的是插入顺序还是访问顺序：

插入顺序（默认）：新元素插入到链表尾部，元素修改不影响顺序。
访问顺序（accessOrder = true）：每次访问元素（如 get()）会将该元素移至链表尾部。

LinkedHashSet 使用的是 插入顺序，若需访问顺序，可直接使用 LinkedHashMap 的键集合：

LinkedHashMap<String, Object> map = new LinkedHashMap<>(16, 0.75f, true);
Set<String> accessOrderedSet = map.keySet(); // 访问顺序的 Set

LinkedHashSet 通过 LinkedHashMap 的双向链表特性，在保持 HashSet 高效性的同时，实现了元素插入顺序的维护。其核心优势在于遍历性能稳定（O (n)）且顺序可控，适用于需要去重并保留插入顺序的场景（如日志处理、缓存淘汰）。

二、关键特性

1. 有序性

插入顺序维护：遍历时元素按插入顺序返回，不随元素修改或扩容改变。

  LinkedHashSet<String> set = new LinkedHashSet<>();
  set.add("A");
  set.add("B");
  set.add("C");
  System.out.println(set); // 输出 [A, B, C]（与插入顺序一致）

与 TreeSet 的区别：TreeSet 按元素自然顺序（或定制顺序）排序，而 LinkedHashSet 仅维护插入顺序，不排序。

2. 性能表现

时间复杂度：插入、删除、查询操作的时间复杂度均为 O(1)，与 HashSet 相同。
空间开销：每个元素需额外维护前驱 / 后继指针，内存占用略高于 HashSet。

3. 线程安全性

非线程安全：多线程环境下需手动同步（如使用 Collections.synchronizedSet() 包装）。

三、适用场景

1. 需保留顺序的数据去重

典型场景：日志记录去重（需保留时间顺序）、过滤重复请求（按请求顺序）。

  List<String> logs = Arrays.asList("ERROR", "INFO", "ERROR", "WARN");
  LinkedHashSet<String> uniqueLogs = new LinkedHashSet<>(logs);
  System.out.println(uniqueLogs); // 输出 [ERROR, INFO, WARN]（保留首次出现顺序）

2. LRU 缓存实现

利用访问顺序：通过构造函数 new LinkedHashSet<>(initialCapacity, loadFactor, true) 启用访问顺序（最近访问的元素移至尾部），结合 removeEldestEntry() 可实现 LRU 缓存淘汰策略。

3. 有序集合运算

交集、并集、差集：在保证元素唯一性的同时，结果保持原始顺序。

  LinkedHashSet<Integer> setA = new LinkedHashSet<>(Arrays.asList(1, 2, 3));
  LinkedHashSet<Integer> setB = new LinkedHashSet<>(Arrays.asList(3, 4, 5));
  setA.removeAll(setB); // 差集操作后，setA 为 [1, 2]（保持原顺序）

四、与其他 Set 实现类对比

维度	HashSet	LinkedHashSet	TreeSet
数据结构	哈希表（HashMap）	哈希表 + 双向链表（LinkedHashMap）	红黑树（TreeMap）
元素顺序	无序（不可预测）	按插入顺序有序	按自然顺序或定制顺序排序
null 支持	允许 1 个 null	允许 1 个 null	不允许 null
插入性能	O (1)（略快）	O (1)（维护链表开销）	O (log n)（需平衡树结构）
遍历效率	取决于哈希分布	稳定 O (n)（按链表顺序）	O (n)（中序遍历红黑树）
适用场景	快速去重、无需顺序	需保留顺序的去重场景	需排序的场景（如数值范围查询）

五、注意事项与最佳实践

初始化容量与负载因子
- 若已知元素数量，建议通过构造函数指定初始容量（如 new LinkedHashSet<>(100)），减少扩容次数。
自定义对象的哈希与相等
- 与 HashSet 相同，需重写 equals() 和 hashCode() 方法以保证唯一性。
遍历顺序与性能
- 遍历效率高于 TreeSet（无需排序），但低于 HashSet（需维护链表）。
避免误用场景
- 若需频繁随机访问元素，建议用 ArrayList；若需排序，用 TreeSet。

总结

`LinkedHashSet` 是有序性与高效性的折中方案，适合需要保留元素插入顺序的去重场景（如日志处理、缓存淘汰）。相比 `HashSet`，它通过双向链表维护顺序，空间和插入性能略低；相比 `TreeSet`，它不支持排序，但遍历效率更高。合理选择 `Set` 实现类，可在保证数据唯一性的同时，满足特定的业务需求。

⬅️ HashSet 🏠 00-Java ➡️ TreeSet

02-LinkedHashSet