LinkedHashSet 与有序去重 | JavaSE

LinkedHashSet 与有序去重

一、学习目标

完成本章学习后，你应该能够：

  • 能够解释 LinkedHashSet 与 HashSet 的关系。
  • 能够说明 LinkedHashSet 为什么既能去重，又具有确定的元素遇见顺序。
  • 能够解释 LinkedHashSet 中“哈希表 + 双向链表”的协作关系。
  • 能够区分“插入顺序”“排序”两个完全不同的概念。
  • 能够根据业务需求在 HashSet、LinkedHashSet 之间进行选择。
  • 能够使用 LinkedHashSet 完成“去重并保留首次出现顺序”的实际任务。
  • 能够使用 JDK 21 中 LinkedHashSet 的首尾与反向视图能力。

二、核心知识

2.1 LinkedHashSet 是什么

LinkedHashSet<E> 是 Set 集合体系中的一个实现类。

基本使用方式：

Set<String> set = new LinkedHashSet<>();

它同时具有两个非常重要的特点：

去重
+
保持明确的元素遇见顺序

例如：

Set<String> set = new LinkedHashSet<>();

set.add("Java");
set.add("MySQL");
set.add("Redis");
set.add("Java");
set.add("Spring");

System.out.println(set);

最终集合中：

  • 第二个 "Java" 不会形成新的重复元素；
  • 遍历时仍然按照元素第一次加入集合时的顺序出现。

所以可以先记住：

LinkedHashSet
= HashSet 的去重能力
+ 确定的遇见顺序

2.2 LinkedHashSet 与 HashSet 的继承关系

LinkedHashSet 本身继承自 HashSet。

可以简化理解为：

Set
 ↑
HashSet
 ↑
LinkedHashSet

所以 LinkedHashSet 并不是完全重新设计了一套去重机制。

它仍然沿用了 HashSet 背后的：

哈希表
hashCode
equals

等机制。

也就是说：

LinkedHashSet 判断元素是否重复的核心逻辑，与 HashSet 属于同一套哈希集合机制。

上一章学习的：

hashCode()
equals()
哈希碰撞
哈希表

仍然成立。

LinkedHashSet 主要是在这个基础上进一步解决：

元素应该按照什么顺序被遍历？

2.3 LinkedHashSet 的核心结构

原始教学资料中将其概括为：

哈希表
+
双向链表

这个模型非常适合入门理解。

假设依次添加：

Java
MySQL
Redis
Spring

哈希表负责：

元素应该保存到哪个桶
是否已经存在
contains / add / remove 等哈希操作

而额外维护的双向链接关系负责：

Java ⇄ MySQL ⇄ Redis ⇄ Spring

从而记录元素的遇见顺序。

可以画成：

             哈希表
               │
       ┌───────┼────────┐
       ↓       ↓        ↓
      ...     ...      ...
       │       │        │
      Java    Redis    MySQL
       │
       └── 哈希结构负责快速定位


同时：

Java ⇄ MySQL ⇄ Redis ⇄ Spring
 ↑                         ↑
最早                     最晚

双向链接负责维护顺序

因此：

哈希表负责“快”和“唯一”，双向链表负责“顺序”。

这是理解 LinkedHashSet 最重要的模型。

2.4 什么叫“遇见顺序”

JDK 21 对集合顺序使用了一个很重要的术语：

遇见顺序（Encounter Order）

可以理解为：

当程序遍历集合时，元素按照什么确定顺序依次被遇到。

例如：

LinkedHashSet<String> set = new LinkedHashSet<>();

set.add("Java");
set.add("MySQL");
set.add("Redis");

普通插入情况下，遇见顺序为：

Java → MySQL → Redis

因此：

for (String value : set) {
    System.out.println(value);
}

会按照这条确定的顺序进行遍历。

2.5 “有序”不等于“自动排序”

这是 LinkedHashSet 最容易混淆的地方。

例如添加：

LinkedHashSet<Integer> set = new LinkedHashSet<>();

set.add(30);
set.add(10);
set.add(20);

LinkedHashSet 表达的是：

30 → 10 → 20

而不是：

10 → 20 → 30

所以：

LinkedHashSet 的有序

指：

有确定的遇见顺序。

而 TreeSet 的：

排序

指：

根据元素比较规则重新确定大小顺序。

二者完全不同。

可以先形成：

| 集合 | 顺序语义 | | --------------- | -------------------- | | HashSet | 不保证确定的遇见顺序 | | LinkedHashSet | 通常保持插入遇见顺序 | | TreeSet | 根据比较规则排序 |

2.6 重复添加是否改变位置

考虑：

LinkedHashSet<String> set = new LinkedHashSet<>();

set.add("Java");
set.add("MySQL");
set.add("Redis");

set.add("Java");

普通：

add("Java")

并不会：

删除原来的 Java
再把 Java 放到最后

因为这个元素已经存在。

普通重复 add() 不会改变其原有插入顺序。

因此最终仍然是：

Java → MySQL → Redis

而不是：

MySQL → Redis → Java

三、使用方法

3.1 创建 LinkedHashSet

导包：

import java.util.LinkedHashSet;
import java.util.Set;

创建：

Set<String> set = new LinkedHashSet<>();

如果需要使用 LinkedHashSet 自身或 JDK 21 SequencedSet 的顺序相关能力，也可以直接：

LinkedHashSet<String> set = new LinkedHashSet<>();

3.2 添加元素

LinkedHashSet<String> technologies = new LinkedHashSet<>();

technologies.add("Java");
technologies.add("Spring");
technologies.add("MySQL");
technologies.add("Redis");

遍历：

for (String technology : technologies) {
    System.out.println(technology);
}

会按照确定的遇见顺序访问元素。

3.3 去重并保留首次出现顺序

这是 LinkedHashSet 最经典的业务场景。

原始数据：

List<String> data = List.of(
        "Java",
        "MySQL",
        "Java",
        "Redis",
        "Spring",
        "MySQL"
);

直接：

LinkedHashSet<String> set = new LinkedHashSet<>(data);

System.out.println(set);

得到的逻辑结果为：

Java
MySQL
Redis
Spring

两个需求同时满足：

删除重复元素
+
保留第一次出现的顺序

3.4 转回 List

有时我们的业务需要：

  1. 先去重；
  2. 再继续使用 List。

可以：

List<String> data = List.of(
        "Java",
        "MySQL",
        "Java",
        "Redis"
);

LinkedHashSet<String> uniqueSet = new LinkedHashSet<>(data);

List<String> result = new ArrayList<>(uniqueSet);

此时：

List
↓
LinkedHashSet 去重
↓
重新转 List

是一种非常常见的数据处理思路。

3.5 使用 contains

LinkedHashSet 仍然属于哈希集合。

因此：

set.contains("Java");

仍然非常适合成员判断。

例如：

if (technologies.contains("Java")) {
    System.out.println("包含 Java 技术");
}

3.6 使用 remove

technologies.remove("Redis");

删除元素后，它也会从：

哈希结构

以及：

顺序链接结构

中移除。

四、原理与进阶

4.1 为什么 LinkedHashSet 会多占一些内存

HashSet 主要关心：

哈希
+
元素
+
桶结构

而 LinkedHashSet 为了额外维护顺序，还必须记录：

前一个元素是谁
后一个元素是谁

可以抽象成：

┌──────────┬──────────┬──────────┐
│ before   │   data   │  after   │
└──────────┴──────────┴──────────┘

因此与 HashSet 相比，它需要额外的链接信息。

这意味着：

顺序不是免费的。

LinkedHashSet 用额外内存和维护成本换取了确定的遇见顺序。

4.2 为什么 LinkedHashSet 的遍历非常稳定

HashSet 的内部 table 可能：

  • 扩容；
  • 元素重新分布；
  • 哈希桶发生变化。

因此不能依赖其遍历顺序。

而 LinkedHashSet 额外维护了一条元素之间的链接关系。

因此遍历时主要根据：

遇见顺序链

向后访问。

可以理解为：

first
 ↓
A ⇄ B ⇄ C ⇄ D
            ↑
           last

这使元素顺序不依赖“它当前在哪一个哈希桶”。

4.3 LinkedHashSet 与 LinkedList 不一样

两个类名字中都有：

Linked

但不要把它们混为一谈。

LinkedList

核心数据结构：

双向链表

主要解决：

List
Deque
首尾操作

LinkedHashSet

核心结构：

哈希表
+
用于维护顺序的双向链接

主要解决：

Set 去重
+
确定的遇见顺序

因此：

LinkedList

不是哈希集合。

而：

LinkedHashSet

仍然属于哈希 Set。

4.4 JDK 21：LinkedHashSet 成为 SequencedSet

JDK 21 对 Java Collections Framework 增加了：

SequencedCollection
SequencedSet
SequencedMap

用于统一表达：

具有确定遇见顺序的集合。

在 JDK 21 中，LinkedHashSet 实现了：

SequencedSet<E>

因此它拥有统一的：

getFirst()
getLast()

removeFirst()
removeLast()

addFirst()
addLast()

reversed()

等顺序操作。

4.5 JDK 21 的 addFirst()

例如：

LinkedHashSet<String> set = new LinkedHashSet<>();

set.add("Java");
set.add("MySQL");
set.add("Redis");

set.addFirst("Spring");

遇见顺序变成：

Spring → Java → MySQL → Redis

如果元素原本已经存在：

set.addFirst("Redis");

则 JDK 21 的 LinkedHashSet 可以把已经存在的 Redis：

重新定位到最前面

而不会产生重复元素。

4.6 JDK 21 的 addLast()

同理：

set.addLast("Java");

如果 Java 已经存在，可以把 Java 调整到：

遇见顺序最后

而不是保存第二个 Java。

因此要区分：

add(e)

与：

addFirst(e)
addLast(e)

普通 add() 重复插入不会改变原位置。

但 JDK 21 的显式首尾定位 API 可以调整已有元素的位置。

4.7 reversed() 是反向视图

JDK 21：

SequencedSet<String> reversed = set.reversed();

它返回的是：

反向顺序视图（Reverse-Ordered View）

例如原集合：

Java → MySQL → Redis

反向视图：

Redis → MySQL → Java

注意它不是简单地：

复制一个完全独立的新集合

而是一个与原集合有关联的视图。

这类“集合视图”思想后续在 Map、排序集合中还会反复出现。

五、实践应用

5.1 博客标签去重

例如用户输入：

Java
Spring
Java
MySQL
Redis
Spring

业务要求：

同一标签只出现一次
+
按照用户第一次添加顺序展示

那么 LinkedHashSet 非常适合。

Set<String> tags = new LinkedHashSet<>();

5.2 搜索关键词去重

用户搜索：

Java
Spring
MySQL
Java
Redis

如果业务需要：

去除重复搜索词，同时保留首次搜索顺序。

LinkedHashSet 可以直接表达这种模型。

5.3 数据清洗

原始数据：

A
B
A
C
D
B

要求输出：

A
B
C
D

核心需求就是：

Distinct
+
Stable Encounter Order

LinkedHashSet 是非常直接的实现方式。

5.4 HashSet 还是 LinkedHashSet

如果业务：

只需要去重
不关心顺序

优先考虑：

HashSet

如果：

需要去重
+
需要确定的遇见顺序

考虑：

LinkedHashSet

所以选型思路是：

顺序不重要
    ↓
HashSet

顺序重要
    ↓
LinkedHashSet

六、常见问题

6.1 LinkedHashSet 是排序集合吗？

不是。

LinkedHashSet 保留的是确定的：

遇见/插入顺序

而不是根据大小自动排序。

自动排序主要是：

TreeSet

的职责。

6.2 LinkedHashSet 能保存重复元素吗？

不能。

因为它仍然属于：

Set

而且继承了 HashSet 的哈希去重机制。

6.3 LinkedHashSet 如何判断重复？

仍然依赖哈希 Set 的对象相等机制。

对于 HashSet/LinkedHashSet 中的自定义对象，通常需要正确设计：

equals()
hashCode()

双向链表本身并不负责判断对象重复。

6.4 双向链表是否负责元素查找？

不是主要职责。

LinkedHashSet 中：

哈希表

负责高效定位和去重。

而：

双向链接结构

主要负责：

维护遇见顺序

不要把两套结构的职责搞反。

6.5 为什么不全部使用 LinkedHashSet，而要保留 HashSet？

因为 LinkedHashSet：

需要维护额外顺序信息

意味着：

  • 更多内存；
  • 更多结构维护工作。

如果业务完全不需要确定顺序，就没有必要为这个能力支付额外成本。

6.6 LinkedHashSet 的重复 add 会把元素移到最后吗？

普通：

add(e)

不会。

如果元素已经存在，普通重复添加不会改变原遇见位置。

但在 JDK 21 中：

addFirst(e)
addLast(e)

可以显式重新定位已有元素。

6.7 LinkedHashSet 是线程安全的吗？

不是。

普通 LinkedHashSet：

不是同步集合

多线程并发修改需要采用专门的同步策略或并发集合。

七、练习与验收

7.1 知识问答

  1. LinkedHashSet 属于什么集合体系？
  2. LinkedHashSet 与 HashSet 有什么继承关系？
  3. LinkedHashSet 为什么能够去重？
  4. LinkedHashSet 为什么能够保持确定的遇见顺序？
  5. 哈希表在 LinkedHashSet 中负责什么？
  6. 双向链接结构负责什么？
  7. LinkedHashSet 的“有序”和 TreeSet 的“排序”有什么区别？
  8. 普通重复调用 add() 是否会改变已有元素顺序？
  9. LinkedHashSet 相比 HashSet 为什么需要更多内存？
  10. 什么业务适合 LinkedHashSet？
  11. 什么业务更适合 HashSet？
  12. JDK 21 的 SequencedSet 解决了什么问题？
  13. addFirst()、addLast() 与普通 add() 有什么区别？
  14. reversed() 返回的是独立复制还是反向视图？

7.2 代码阅读

不运行下面代码：

LinkedHashSet<String> set = new LinkedHashSet<>();

set.add("Java");
set.add("MySQL");
set.add("Java");
set.add("Redis");
set.add("Spring");
set.add("MySQL");

System.out.println(set);

回答：

  1. 最终有几个元素？
  2. 哪些元素属于重复添加？
  3. 最终遍历顺序如何判断？
  4. 第二次添加 "Java" 是否会把 Java 移动到末尾？
  5. 如果改成 HashSet，还有哪些结论仍然成立？哪些不再能保证？

7.3 手写代码

任务一：去重并保留顺序

给定：

List<String> data = List.of(
        "Java",
        "Python",
        "Java",
        "C++",
        "Python",
        "Go"
);

要求：

  • 使用 LinkedHashSet 去重；
  • 保留元素首次出现顺序；
  • 遍历结果；
  • 最后转回 ArrayList。

任务二：博客标签

实现博客标签集合：

Java
Spring
MySQL
Java
Redis
Spring

要求：

  • 标签不可重复；
  • 保留用户首次添加顺序；
  • 支持判断标签是否存在；
  • 支持删除标签；
  • 最终输出所有标签。

任务三：JDK 21 顺序操作

创建：

LinkedHashSet<String>

加入：

A B C D

然后分别练习：

getFirst()
getLast()
addFirst()
addLast()
removeFirst()
removeLast()
reversed()

并在纸上记录每一步集合的遇见顺序。

7.4 Debug

下面程序的业务需求是：

去重后必须保留输入顺序。

程序却写成：

Set<String> result = new HashSet<>();

for (String value : source) {
    result.add(value);
}

回答：

  1. 代码能否完成去重？
  2. 哪里不符合业务要求？
  3. 为什么 HashSet 不是最准确的数据结构？
  4. 应改成什么？
  5. 修改后是否还需要自己手写重复检查逻辑？

7.5 综合训练

设计一个“关键词历史”系统。

原始关键词：

Java
Spring
MySQL
Java
Redis
Spring
Docker

需求：

  • 同一关键词只保留一次；
  • 默认按照第一次出现顺序展示；
  • 可以判断关键词是否存在；
  • 可以删除关键词；
  • JDK 21 下可以把某个已有关键词显式移动到最前；
  • 可以查看反向顺序。

要求：

  1. 选择数据结构；
  2. 说明选择理由；
  3. 完成完整代码；
  4. 说明普通 add() 和 addFirst() 的不同业务含义。

7.6 本章验收

关闭资料和 AI 自动补全：

  • [ ] 能解释 LinkedHashSet = 哈希去重 + 确定遇见顺序。
  • [ ] 能画出“哈希表 + 双向链接”的结构模型。
  • [ ] 能区分哈希结构和双向链接结构的职责。
  • [ ] 能区别“有序”和“排序”。
  • [ ] 能说出 HashSet 与 LinkedHashSet 的选型原则。
  • [ ] 能独立完成“去重并保留首次出现顺序”。
  • [ ] 能解释 LinkedHashSet 的额外内存成本。
  • [ ] 能使用 JDK 21 的 addFirst、addLast、reversed。
  • [ ] 能解释普通重复 add 为什么不改变元素位置。