HashSet、TreeSet 与集合排序

S1-018建议学进阶约 60 分钟JDK 21编程语言基础 · 集合

1. 本节定位

《List、Set、Map》讲了 Set 的语义（不重复），本节看它的三种实现，以及一个必须掌握的技能：给对象排序。

排序涉及 Comparable 与 Comparator 两个接口——它们的分工（自然序 vs 自定义序）在后面的 Stream 排序、TreeMap、甚至排行榜业务里都会用到。

2. 学习目标

完成本节后，你应该能够：

说出 HashSet / LinkedHashSet / TreeSet 在顺序与性能上的差别；
按"要不要顺序、要不要排序、要不要缓存友好"选对 Set；
用 Comparator.comparing().thenComparing().reversed() 写出多字段排序；
说清 Comparable 与 Comparator 的分工；
解释 TreeSet 判断重复用的是 compareTo 而不是 equals，并知道它带来的风险。

3. 前置知识检查

知道 HashSet 去重依赖 equals / hashCode 吗？（《equals、hashCode 与对象比较》）
会遍历集合吗？（《List、Set、Map》）

4. 为什么需要这个知识

Set 的三种实现功能上都能去重，但顺序与性能完全不同：

java

List<String> source = List.of("banana", "apple", "cherry", "apple");

new HashSet<>(source)         → [banana, apple, cherry]     顺序不可预测
new LinkedHashSet<>(source)   → [banana, apple, cherry]     保持插入顺序
new TreeSet<>(source)         → [apple, banana, cherry]     按字母排序

前两个例子"恰好"输出相同——这是 HashSet 最坑的地方：它的顺序看起来稳定，但你不该依赖它（数据量、哈希实现一变，顺序就变）。

排序则更常见：排行榜、按时间倒序、多字段排序（先按分数、分数相同按姓名）。这些都得靠 Comparator。

5. 核心概念

5.1 三种 Set 实现

实现	底层结构	顺序	查找性能	适用场景
`HashSet`	`HashMap`	不保证	O(1)	只需去重、最常用
`LinkedHashSet`	`LinkedHashMap`	插入顺序	O(1)	去重且要可预测输出
`TreeSet`	红黑树	排序	O(log n)	去重且要排序

选型顺序：

text

只需要去重           → HashSet（最快）
去重 + 输出要稳定     → LinkedHashSet
去重 + 需要排序       → TreeSet

一个实用建议

写单元测试时，用 HashSet 断言结果会因为顺序不同而失败。此时要么改用 LinkedHashSet，要么在断言里先排序——让测试结果可复现，是测试设计的基本要求。

5.2 排序的两个接口

java

// Comparable：类自己声明"我按什么排序"（自然序）
public class Student implements Comparable<Student> {
    @Override
    public int compareTo(Student other) {
        return Integer.compare(score, other.score);
    }
}

// Comparator：外部指定排序规则（可以有无数种）
Comparator<Student> byScoreDesc = Comparator.comparingInt(Student::score).reversed();
students.sort(byScoreDesc);

	`Comparable`	`Comparator`
位置	类自己实现	外部传入
数量	只能有一个	可以有无数个
用途	定义"默认怎么排"	定义"这次按什么排"
典型	`String`、`Integer`、`LocalDate`	业务排序、多字段排序

判断标准：如果这个类有一个"天经地义"的排序方式，就实现 Comparable；否则用 Comparator 在需要的场合传。实践中 Comparator 用得更多，因为它不侵入类的定义。

5.3 Comparator 的常用组合

java

// 单字段升序
Comparator.comparingInt(Student::score)

// 单字段降序
Comparator.comparingInt(Student::score).reversed()

// 多字段：先按分数降序，分数相同按姓名升序
Comparator.comparingInt(Student::score).reversed()
          .thenComparing(Student::name)

// 处理 null
Comparator.nullsLast(Comparator.comparing(Student::name))

// 字符串忽略大小写
String.CASE_INSENSITIVE_ORDER

顺序很关键：.reversed() 只反转它之前的规则。所以

java

Comparator.comparingInt(Student::score).reversed().thenComparing(Student::name)

是"分数降序、姓名升序"；如果写成 .thenComparing(...).reversed()，两条规则会一起被反转。

5.4 自然序的两个陷阱

java

List<String> words = new ArrayList<>(List.of("banana", "apple", "Cherry"));
Collections.sort(words);
// [Cherry, apple, banana]   ← 大写字母排在前面！

原因：String 的自然序按字符的 Unicode 码点比较，大写字母（65-90）小于小写字母（97-122）。

需要忽略大小写时：

java

words.sort(String.CASE_INSENSITIVE_ORDER);
// [apple, banana, Cherry]

5.5 TreeSet 的去重规则（重要）

TreeSet 判断"是否重复"用的是 compareTo（或 Comparator）返回是否为 0，而不是 equals：

java

Set<Student> byScore = new TreeSet<>(Comparator.comparingInt(Student::score));
byScore.add(new Student("张三", 90));
byScore.add(new Student("王五", 90));      // 分数相同 → 被判为重复，不加入
byScore.size();                            // 1（不是 2！）

风险：这与 HashSet 的行为不一致，容易造成"数据莫名丢失"。规则：

用 TreeSet 时，比较器必须能区分所有"你认为是不同"的对象；
需要按某字段排序但保留所有对象时，用 List + sort，而不是 TreeSet。

6. 递进示例

6.1 最小示例：三种 Set 的顺序差异

java

List<String> source = List.of("banana", "apple", "cherry", "apple");
System.out.println(new LinkedHashSet<>(source));   // [banana, apple, cherry]
System.out.println(new TreeSet<>(source));         // [apple, banana, cherry]

6.2 业务示例：成绩排行榜

java

List<Student> students = new ArrayList<>(List.of(
        new Student("张三", 90),
        new Student("李四", 95),
        new Student("王五", 90)));

// 分数降序，同分按姓名升序
students.sort(Comparator.comparingInt(Student::score).reversed()
                        .thenComparing(Student::name));
// [李四(95), 张三(90), 王五(90)]

这里用 List + sort 而不是 TreeSet，因为 TreeSet 会把"分数相同"的两个学生当作重复丢掉。

6.3 反例：TreeSet 丢失数据

java

Set<Student> set = new TreeSet<>(Comparator.comparingInt(Student::score));
set.add(new Student("张三", 90));
set.add(new Student("王五", 90));
System.out.println(set.size());       // 1 —— 王五没了

问题：比较器只比较分数，张三和王五"相等"，后者被丢弃。

修复：

java

// 方案一：比较器加上次要字段，保证能区分
Comparator.comparingInt(Student::score).thenComparing(Student::name)

// 方案二：改用 List + sort（推荐，语义更清晰）

7. 完整可运行代码

文件：labs/collections/src/main/java/cn/kb/learn/collection/SetLesson.java

java

package cn.kb.learn.collection;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;

public class SetLesson {
    record Student(String name, int score) {
        @Override
        public String toString() {
            return name + "(" + score + ")";
        }
    }

    public static void main(String[] args) {
        // 1. 三种 Set 的顺序差异
        List<String> source = List.of("banana", "apple", "cherry", "apple");
        System.out.println("HashSet（不保证顺序）: " + new HashSet<>(source));
        System.out.println("LinkedHashSet（插入顺序）: " + new LinkedHashSet<>(source));
        System.out.println("TreeSet（自然排序）: " + new TreeSet<>(source));

        // 2. List 排序：Comparable 自然序
        List<String> words = new ArrayList<>(List.of("banana", "apple", "Cherry"));
        Collections.sort(words);
        System.out.println("自然序（大写字母排前面）: " + words);
        words.sort(String.CASE_INSENSITIVE_ORDER);
        System.out.println("忽略大小写排序: " + words);

        // 3. 自定义对象排序：Comparator
        List<Student> students = new ArrayList<>(List.of(
                new Student("张三", 90),
                new Student("李四", 95),
                new Student("王五", 90)));
        students.sort(Comparator.comparingInt(Student::score).thenComparing(Student::name));
        System.out.println("按分数升序、同分按姓名: " + students);

        students.sort(Comparator.comparingInt(Student::score).reversed().thenComparing(Student::name));
        System.out.println("按分数降序、同分按姓名: " + students);

        // 4. TreeSet 使用 Comparator，并据此判断重复
        Set<Student> byScore = new TreeSet<>(Comparator.comparingInt(Student::score).reversed());
        byScore.add(new Student("张三", 90));
        byScore.add(new Student("王五", 90));      // 与上一个分数相同
        byScore.add(new Student("李四", 95));
        System.out.println("TreeSet 按分数排序: " + byScore);
        System.out.println("compareTo 相同即视为重复，size = " + byScore.size());
    }
}

运行命令：

powershell

cd labs
./mvnw -pl collections compile
java -cp collections/target/classes cn.kb.learn.collection.SetLesson

预期输出：

text

HashSet（不保证顺序）: [banana, apple, cherry]
LinkedHashSet（插入顺序）: [banana, apple, cherry]
TreeSet（自然排序）: [apple, banana, cherry]
自然序（大写字母排前面）: [Cherry, apple, banana]
忽略大小写排序: [apple, banana, Cherry]
按分数升序、同分按姓名: [张三(90), 王五(90), 李四(95)]
按分数降序、同分按姓名: [李四(95), 张三(90), 王五(90)]
TreeSet 按分数排序: [李四(95), 张三(90)]
compareTo 相同即视为重复，size = 2

三处关键：

输出	含义
`HashSet` 与 `LinkedHashSet` 恰好相同	不要依赖这个巧合——`HashSet` 的顺序不保证
`[Cherry, apple, banana]`	自然序按 Unicode 码点，大写字母在小写之前
`TreeSet ... size = 2`	张三与王五分数相同，被判为重复

8. Debug 观察点

在 new TreeSet<>(source) 处断点，展开 TreeSet 观察内部是一个 TreeMap（key 是元素，value 是占位对象）——Set 的实现几乎都是"Map 的 key 集合"；
在 students.sort(...) 处 F7 进入，观察它最终调用 Arrays.sort 或 List.sort 的默认实现（ArrayList 用 Arrays.sort，LinkedList 用归并排序）；
在比较器 comparingInt(Student::score) 内部下断点（可以写成 lambda 后打断点），观察比较过程——理解 Comparator 是被反复回调的；
把 thenComparing(Student::name) 删掉，再观察 TreeSet 的行为变化（size 从 2 变 1）——这是本节最重要的一次实验。

9. 常见错误

错误 1：用 TreeSet 却丢失了数据

见 6.3 节。修复：比较器要能区分所有"你认为不同"的对象，或改用 List + sort。

错误 2：以为 `HashSet` 的顺序是固定的

java

Set<String> set = new HashSet<>(List.of("a", "b", "c"));
// 打印起来"看起来"是 a, b, c，但换个 JDK 版本或数据量就变了

修复：需要可预测顺序时用 LinkedHashSet 或 TreeSet。

错误 3：`reversed()` 的位置放错

java

// 意图：分数降序、姓名升序
Comparator.comparingInt(Student::score).thenComparing(Student::name).reversed()
// 实际：两条规则都被反转 → 分数升序、姓名降序

// 正确
Comparator.comparingInt(Student::score).reversed().thenComparing(Student::name)

错误 4：比较器里做减法导致溢出

java

(a, b) -> a.score() - b.score()          // 分数差很大时 int 溢出
Comparator.comparingInt(Student::score)  // 正确

错误 5：`compareTo` 与 `equals` 不一致

java

// compareTo 只比 score，equals 比 name + score

这种不一致在 TreeSet 与 HashSet 上会表现出不同的去重结果。建议：让 compareTo 与 equals 的语义保持一致，或明确只在需要排序时用 Comparator。

10. 动手实验

目标：写多字段排序，并体验 TreeSet 的去重规则。

步骤：

运行第 7 节代码，核对输出；
给 Student 加一个 clazz（班级）字段，排序规则改为"班级升序 → 分数降序 → 姓名升序"；
用 TreeSet 按"班级 + 分数 + 姓名"做比较器，验证不会丢数据；
用 List + sort 做同样的排序，对比两种写法的代码量与语义清晰度；
写一个方法 List<Student> topN(List<Student> students, int n)：返回分数最高的前 N 名（用 sort + subList 实现）。

验收方式：能解释第 3 步"为什么加上姓名后就不丢数据了"。

扩展任务：用 Comparator.nullsLast 处理姓名为 null 的学生，体会"排序时如何处理 null"这个实际问题的写法。

11. 练习题

基础题

判断：TreeSet 判断元素重复用的是 equals。（对 / 错）
填空：需要去重且保持插入顺序用 ______；需要去重且排序用 ______。
简答：Comparable 与 Comparator 的区别是什么？

代码阅读题

java

record Item(String name, int price) {}

List<Item> items = new ArrayList<>(List.of(
        new Item("笔", 3), new Item("本", 10), new Item("橡皮", 3)));
items.sort(Comparator.comparingInt(Item::price).reversed().thenComparing(Item::name));
System.out.println(items);

输出是什么？如果去掉 thenComparing，结果还确定吗？

编程题

有一个 Map<String, Integer>（姓名 → 分数），要求输出按分数降序、同分按姓名升序的列表，格式为 姓名: 分数。

综合任务

设计一个"商品排序"需求：
- Product（name、price、sales、rating）；
- 默认排序：销量降序 → 评分降序 → 价格升序；
- 支持"按价格从低到高"的备选排序；
- 用 Comparator 实现两种排序，并说明为什么把默认排序放在方法里而不是让 Product 实现 Comparable；
- 额外：处理"价格相同时按评分降序"的组合。

分级提示

提示 1（方向）：第 4 题的结果由"先价格降序、同价按名称升序"决定。

提示 2（关键点）：第 5 题把 map.entrySet() 转成 List 再排序，比较器用 Map.Entry.comparingByValue(Comparator.reverseOrder()).thenComparing(Map.Entry.comparingByKey())。

提示 3（接近答案）：第 6 题不实现 Comparable 的原因是"默认排序"在业务上可能变化，而且有多个排序需求——用 Comparator 更灵活、不侵入领域对象。

12. 参考答案

基础题

错。TreeSet 用 compareTo（或 Comparator）的返回值是否为 0 来判断重复，与 equals 无关。这正是"分数相同的学生被丢掉"的原因。
LinkedHashSet、TreeSet。
Comparable 由类自己实现，定义"自然序"，一个类只能有一个；Comparator 由外部传入，可以定义任意多种排序规则，不侵入类的定义。

代码阅读题（第 4 题）

text

[本(10), 橡皮(3), 笔(3)]

价格降序：10（本）在最前；
价格相同（3）的两项按名称升序：橡皮（拼音/Unicode 顺序）在笔之前。

去掉 thenComparing 后结果不再确定：sort 是稳定排序，对于"比较结果相同"的元素会保持原有相对顺序——所以在这个例子里恰好还是 [橡皮, 笔]（因为原列表顺序如此）。但这是巧合，一旦上游改变了列表顺序，输出就变了。结论：多字段排序务必写全条件。

编程题（第 5 题）

java

package cn.kb.learn.collection;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;

public class ScoreRanking {
    static List<String> rank(Map<String, Integer> scores) {
        List<Map.Entry<String, Integer>> entries = new ArrayList<>(scores.entrySet());
        entries.sort(Map.Entry.<String, Integer>comparingByValue(Comparator.reverseOrder())
                .thenComparing(Map.Entry.comparingByKey()));

        List<String> result = new ArrayList<>();
        for (Map.Entry<String, Integer> entry : entries) {
            result.add(entry.getKey() + ": " + entry.getValue());
        }
        return result;
    }

    public static void main(String[] args) {
        Map<String, Integer> scores = new LinkedHashMap<>();
        scores.put("张三", 90);
        scores.put("李四", 95);
        scores.put("王五", 90);
        System.out.println(rank(scores));
    }
}

预期输出：

text

[李四: 95, 王五: 90, 张三: 90]

综合任务（第 6 题）

java

package cn.kb.learn.collection;

import java.util.Comparator;
import java.util.List;

public class ProductSorter {
    record Product(String name, long priceInCents, int sales, double rating) {
    }

    /** 默认排序：销量降序 → 评分降序 → 价格升序 */
    static final Comparator<Product> DEFAULT_ORDER =
            Comparator.comparingInt(Product::sales).reversed()
                    .thenComparing(Comparator.comparingDouble(Product::rating).reversed())
                    .thenComparingLong(Product::priceInCents);

    /** 备选排序：价格升序 → 评分降序（价格相同时评分高的在前） */
    static final Comparator<Product> PRICE_ASC_ORDER =
            Comparator.comparingLong(Product::priceInCents)
                    .thenComparing(Comparator.comparingDouble(Product::rating).reversed());

    public static void main(String[] args) {
        List<Product> products = List.of(
                new Product("A", 300, 100, 4.5),
                new Product("B", 200, 100, 4.8),
                new Product("C", 200, 100, 4.5),
                new Product("D", 500, 200, 4.0));

        System.out.println("默认排序: " + products.stream().sorted(DEFAULT_ORDER).map(Product::name).toList());
        System.out.println("价格升序: " + products.stream().sorted(PRICE_ASC_ORDER).map(Product::name).toList());
    }
}

为什么不实现 Comparable：

业务排序规则会变——"默认排序"可能从"销量优先"改成"评分优先"，改 Comparator 是外部调整，改 Comparable 要动类本身；
有多个排序需求——一个类只能有一个 Comparable，但可以有无数个 Comparator；
不侵入领域对象——Product 的职责是描述商品，排序是展示层的关注点。

另一点：把比较器定义为 static final 常量，既复用又避免了每次排序重新构造。

预期输出：

text

默认排序: [D, B, A, C]
价格升序: [B, C, A, D]

13. 掌握标准

[ ] 能按需求在三种 Set 之间做选择；
[ ] 能用 Comparator 写单字段与多字段排序；
[ ] 知道 reversed() 的作用范围；
[ ] 知道自然序的大小写陷阱，会用 CASE_INSENSITIVE_ORDER；
[ ] 能解释 TreeSet 用 compareTo 判重的风险，并知道该改用 List + sort 的时机。

14. 扩展资源

Comparator 官方 API：comparing / thenComparing / reversed / nullsLast 全在这里
Object Ordering 官方教程：Comparable 与 Comparator 的官方说明
《Stream API》：流式排序 sorted(comparator) 与本节配合使用

15. 下一步学习

《迭代器与集合遍历陷阱》：解释 ConcurrentModificationException 的成因、为什么"删倒数第二个元素不报错"，以及遍历中删除的三种正确写法。

前置知识

S1-015 List、Set、Map

后续知识

暂无

进度只保存在本机浏览器，可随时清除

外部学习资源

面试题库索引

项目与练手索引

工具与软件索引

HashSet、TreeSet 与集合排序

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 三种 Set 实现

5.2 排序的两个接口

5.3 Comparator 的常用组合

5.4 自然序的两个陷阱

5.5 TreeSet 的去重规则（重要）

6. 递进示例

6.1 最小示例：三种 Set 的顺序差异

6.2 业务示例：成绩排行榜

6.3 反例：TreeSet 丢失数据

7. 完整可运行代码

8. Debug 观察点

9. 常见错误

错误 1：用 TreeSet 却丢失了数据

错误 2：以为 `HashSet` 的顺序是固定的

错误 3：`reversed()` 的位置放错

错误 4：比较器里做减法导致溢出

错误 5：`compareTo` 与 `equals` 不一致

10. 动手实验

11. 练习题

12. 参考答案

13. 掌握标准

14. 扩展资源

15. 下一步学习

前置知识

后续知识

HashSet、TreeSet 与集合排序 ​

1. 本节定位 ​

2. 学习目标 ​

3. 前置知识检查 ​

4. 为什么需要这个知识 ​

5. 核心概念 ​

5.1 三种 Set 实现 ​

5.2 排序的两个接口 ​

5.3 Comparator 的常用组合 ​

5.4 自然序的两个陷阱 ​

5.5 TreeSet 的去重规则（重要） ​

6. 递进示例 ​

6.1 最小示例：三种 Set 的顺序差异 ​

6.2 业务示例：成绩排行榜 ​

6.3 反例：TreeSet 丢失数据 ​

7. 完整可运行代码 ​

8. Debug 观察点 ​

9. 常见错误 ​

错误 1：用 TreeSet 却丢失了数据 ​

错误 2：以为 HashSet 的顺序是固定的 ​

错误 3：reversed() 的位置放错 ​

错误 4：比较器里做减法导致溢出 ​

错误 5：compareTo 与 equals 不一致 ​

10. 动手实验 ​

11. 练习题 ​

12. 参考答案 ​

13. 掌握标准 ​

14. 扩展资源 ​

15. 下一步学习 ​

前置知识

后续知识

HashSet、TreeSet 与集合排序

1. 本节定位

2. 学习目标

3. 前置知识检查

4. 为什么需要这个知识

5. 核心概念

5.1 三种 Set 实现

5.2 排序的两个接口

5.3 Comparator 的常用组合

5.4 自然序的两个陷阱

5.5 TreeSet 的去重规则（重要）

6. 递进示例

6.1 最小示例：三种 Set 的顺序差异

6.2 业务示例：成绩排行榜

6.3 反例：TreeSet 丢失数据

7. 完整可运行代码

8. Debug 观察点

9. 常见错误

错误 1：用 TreeSet 却丢失了数据

错误 2：以为 `HashSet` 的顺序是固定的

错误 3：`reversed()` 的位置放错

错误 4：比较器里做减法导致溢出

错误 5：`compareTo` 与 `equals` 不一致

10. 动手实验

11. 练习题

12. 参考答案

13. 掌握标准

14. 扩展资源

15. 下一步学习