---
url: https://www.chenlj.top/md/java-base/collections/LinkedHashSet.md
---
# LinkedHashSet 源码解析

## 简介

`LinkedHashSet` 继承自 `HashSet`，在保持「元素不可重复」的同时，**维护了元素的插入顺序**（迭代顺序 == 插入顺序）。

它的实现与 `HashSet` 几乎一样「偷懒」：**底层包装的是 `LinkedHashMap`**（`accessOrder = false`），利用 `LinkedHashMap` 的双向链表来记录插入次序。

* 不是线程安全的。
* 允许一个 `null`，去重同样依赖 `hashCode()` / `equals()`。
* 与 `HashSet` 相比多了「保序」能力，但内存占用略高（要维护链表指针）。

> 若想实现「访问顺序（LRU）」的 Set，标准库没有现成类，可基于 `LinkedHashMap` 自己实现（类似 `LinkedHashMap` 实现 LRU 的思路）。

## 底层数据结构分析

`LinkedHashSet` 自身没有任何新字段，唯一的区别在构造器：`HashSet` 提供了一个包级私有构造，让它创建的是 `LinkedHashMap` 而非 `HashMap`。

```java
// HashSet 的包级私有构造：dummy 参数仅用于区分，真正的逻辑是创建 LinkedHashMap
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
```

`LinkedHashSet` 正是调用了上面的构造：

```java
public LinkedHashSet(int initialCapacity, float loadFactor) {
    super(initialCapacity, loadFactor, true); // 第三个参数 true 触发 LinkedHashMap
}
```

于是 `add` / `remove` / `contains` 与 `HashSet` 完全一致，只是底层从 `HashMap` 换成了 `LinkedHashMap`，迭代时会按双向链表顺序输出。

## 核心成员变量

```java
// 没有新增字段，全部复用父类 HashSet 的 map（实际是 LinkedHashMap 实例）
// private transient HashMap<E,Object> map;
```

## 源码分析

### 写入：add

`add` 完全继承自 `HashSet`（委托给 `LinkedHashMap.put`）：

```java
public boolean add(E e) {
    return map.put(e, PRESENT) == null; // map 实为 LinkedHashMap
}
```

因为 `LinkedHashMap` 在插入新 key 时会把它接到双向链表尾部，所以迭代时元素按**插入顺序**排列。

### 迭代顺序

```java
// LinkedHashSet 的迭代直接复用 LinkedHashMap 的 keySet 顺序
public Iterator<E> iterator() {
    return map.keySet().iterator(); // 按链表顺序遍历
}
```

## 与 HashSet / TreeSet 的对比

| 维度 | HashSet | LinkedHashSet | TreeSet |
| --- | --- | --- | --- |
| 底层 | HashMap | LinkedHashMap | TreeMap |
| 顺序 | 无序 | **插入顺序** | key 有序 |
| 允许 null | 允许 | 允许 | 否（自然排序下） |
| 复杂度 | 平均 O(1) | 平均 O(1) | O(log n) |

## 经典 Demo

```java
import java.util.LinkedHashSet;

public class LinkedHashSetDemo {
    public static void main(String[] args) {
        LinkedHashSet<String> set = new LinkedHashSet<>();
        set.add("c"); set.add("a"); set.add("b");
        System.out.println(set); // [c, a, b] 严格保持插入顺序
    }
}
```