Set 的核心承诺只有四个字：元素唯一。HashSet 靠哈希算法高效判重，TreeSet 靠排序顺便判重，LinkedHashSet 则额外记住插入顺序。本篇把三种 Set 的原理讲透，重点是 hashCode/equals 这对孪生方法和 Comparable/Comparator 两种排序方案。

本篇目标

  • 理解 Set 去重的语义和 HashSet 的判重流程
  • 说清为什么自定义对象必须成对重写 hashCode() 和 equals()
  • 区分 HashSet、LinkedHashSet、TreeSet 的适用场景
  • 掌握 Comparable 自然排序与 Comparator 比较器排序

Set 的核心语义：不重复

List 允许重复、有索引；Set 不允许重复、没有索引（也就没了按下标操作的方法）。先看 HashSet 的基本使用：

HashSet<String> hs = new HashSet<>();
boolean b1 = hs.add("a");
boolean b2 = hs.add("a");   // 重复，存不进去

System.out.println(b1);     // true
System.out.println(b2);     // false，add 用返回值告诉你有没有存成功
for (String s : hs) {
    System.out.println(s);
}

两个注意点：存重复元素不报错，只是 add 返回 false；遍历顺序和插入顺序没有对应关系——HashSet 不承诺任何顺序。由于没有索引，Set 的遍历只有迭代器和增强 for 两种，用不了带下标的普通 for。

HashSet：hashCode 与 equals 如何配合

如果每次 add 都把新元素和已有元素逐个 equals 一遍，集合一大效率就垮了。HashSet 用哈希算法把这件事变快：add 时先调对象的 hashCode() 算出哈希值，定位到对应的桶——桶里没有哈希值相同的对象就直接存入；有的话再逐个 equals() 确认，真相等才不存。哈希值把”和所有人比”缩小成”只和同桶的人比”，equals 的调用次数大大降低。

两个不同对象的 hashCode 碰巧相同，叫哈希碰撞，它们会落进同一个桶，靠 equals 逐个甄别。所以 hashCode 设计得越好、分布越均匀，碰撞越少，equals 就越少被调用，性能越好。

一句话预告：HashSet 底层其实是一个只存键不存值的 HashMap，这套”先哈希定位、再 equals 确认”的机制正是 HashMap 的灵魂，后续的 HashMap 源码分析会完整拆解它。

自定义对象必须重写两个方法

HashSet<Person> hs = new HashSet<>();
hs.add(new Person("张三", 23));
hs.add(new Person("张三", 23));
System.out.println(hs.size());   // 不重写的话输出 2，出问题了

不重写时，Object 的默认实现看的是内存地址：两个 new 出来的”张三”地址不同、哈希值不同，HashSet 根本发现不了重复。重写规则：hashCode() 要求属性相同的对象返回值必须相同，属性不同尽量不同（减少 equals 次数）；equals() 要求属性相同返回 true。两个方法必须保持一致的判等标准，只重写一个等于没重写，开发中直接用 IDE 自动生成。

LinkedHashSet：保住插入顺序

HashSet 快但无序，若要求”怎么存就怎么取”就换 LinkedHashSet：它在哈希表之外多维护一条双向链表记录插入次序，去重能力和速度基本不受影响。

LinkedHashSet<String> lhs = new LinkedHashSet<>();
lhs.add("c");
lhs.add("a");
lhs.add("b");
System.out.println(lhs);   // [c, a, b]，按插入顺序输出

典型场景：去掉日志里的重复行但保持原有顺序。上一篇给 ArrayList 去重的练习，用 LinkedHashSet 两步就能搞定：addAll 进去再取出来，重复没了、顺序还在，比手写 contains 筛子优雅得多。

TreeSet：排序即去重

TreeSet 底层是红黑树（自平衡二叉搜索树），元素一进来就按规则排好位置，有序是它的卖点，去重是排序的副产品——比较结果为 0 就视为重复不存。红黑树保证增删查稳定在 O(log n)，比哈希结构的 O(1) 略慢，换来的是天然有序。排序有两种指定方式。

方式一：自然排序 Comparable

让元素类实现 Comparable 接口，重写 compareTo：

public class Person implements Comparable<Person> {
    private String name;
    private int age;
    // 构造、getter 省略

    @Override
    public int compareTo(Person other) {
        int num = this.age - other.age;                            // 主条件：按年龄升序
        return num == 0 ? this.name.compareTo(other.name) : num;   // 次要条件
    }
}

compareTo 返回负数表示”我小排前面”，正数排后面，返回 0 表示相等、不存。写主条件时务必补次要条件，否则年龄相同的两个人会被误判为重复而丢掉一个。String、Integer 这些 JDK 类早已实现 Comparable，所以 TreeSet 存字符串、数字直接就有序。

方式二：比较器排序 Comparator

元素类不方便改，或一套类想要多种排法，就把比较逻辑外置成 Comparator，通过构造方法传给 TreeSet：

TreeSet<Person> ts = new TreeSet<>(new Comparator<Person>() {
    @Override
    public int compare(Person p1, Person p2) {
        int num = p1.getName().length() - p2.getName().length();
        return num == 0 ? p1.getName().compareTo(p2.getName()) : num;
    }
});

两者区别：不传比较器时默认走元素自身的 Comparable，没实现就抛 ClassCastException；传了 Comparator 就优先用比较器。Comparable 是”类天生会排”，Comparator 是”外部按需指定”，后者更灵活，实战用得更多。

还有个反向技巧：如果业务要求”排序但保留重复”，可以在 compare 的最后把 0 改掉——return num == 0 ? 1 : num;，TreeSet 就会把相等元素当成”比它大”而照常存入。

经典练习一：生成 10 个不重复的随机数

HashSet<Integer> hs = new HashSet<>();
Random r = new Random();

while (hs.size() < 10) {          // 用 size 控制个数
    hs.add(r.nextInt(20) + 1);    // 1~20，重复了自动被丢弃
}

for (Integer num : hs) {
    System.out.println(num);
}

去重交给 Set，循环条件只看 size——体会”让数据结构替你干活”的思路。再想一步：要求结果有序输出，把 HashSet 换成 TreeSet 即可，一行改动。

经典练习二：去掉字符串中的重复字符

键盘录入一行字符串（如 aaaabbbcccddd），去掉重复字符后打印：

Scanner sc = new Scanner(System.in);
String line = sc.nextLine();
HashSet<Character> hs = new HashSet<>();
for (char c : line.toCharArray()) {
    hs.add(c);
}
System.out.println(hs);

Character 是包装类，JDK 早已为它重写好 hashCode 和 equals，拿来就能用。想保持字符出现的先后顺序，把 HashSet 换成 LinkedHashSet 即可。

小结

  • Set 不承诺索引，只承诺不重复：HashSet 无序、LinkedHashSet 按插入序、TreeSet 按排序规则。
  • HashSet 判重靠”先 hashCode 定位、再 equals 确认”，自定义对象必须成对重写这两个方法。
  • TreeSet 的排序规则决定去重标准：compareTo/compare 返回 0 即视为重复，写主条件别忘次要条件。
  • Comparable 内置于类，Comparator 外置可配多种排序，二者同时存在时比较器优先。