---
title: "02-LinkedHashSet"
created: 2025-12-02
tags:
  - Java
---
# LinkedHashSet

> [!note] 定位说明
> Set 系列第 2 篇。HashSet 加一条双向链表记住插入顺序——**"去重且保序"的唯一解**。底层是 LinkedHashMap，读法同源。

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

### **一、核心原理与数据结构**

#### **1. 底层实现**

**基于 LinkedHashMap**：

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

```java
// 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`）指针。源码中的节点定义：

```java
// 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` 维护：

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

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

**插入元素**：

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

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

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

```java
// 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` 的迭代器直接沿双向链表顺序访问，而非按哈希表的桶顺序。源码如下：

```java
// 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. 插入顺序演示**

```java
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` 的键集合：

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

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

### **二、关键特性**

#### **1. 有序性**

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

```java
  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. 需保留顺序的数据去重**

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

```java
  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. 有序集合运算**

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

```java
  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)（中序遍历红黑树） |
| **适用场景** | 快速去重、无需顺序 | 需保留顺序的去重场景 | 需排序的场景（如数值范围查询） |

### **五、注意事项与最佳实践**

1. **初始化容量与负载因子**

   - 若已知元素数量，建议通过构造函数指定初始容量（如 `new LinkedHashSet<>(100)`），减少扩容次数。
2. **自定义对象的哈希与相等**

   - 与 `HashSet` 相同，需重写 `equals()` 和 `hashCode()` 方法以保证唯一性。
3. **遍历顺序与性能**

   - 遍历效率高于 `TreeSet`（无需排序），但低于 `HashSet`（需维护链表）。
4. **避免误用场景**

   - 若需频繁随机访问元素，建议用 `ArrayList`；若需排序，用 `TreeSet`。

### **总结**

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