5.2 查重比对：Set

5.2 查重比对：Set

本节摘要：Set 的契约只有一条——不可重复。HashSet 用哈希定位、快但不保序；LinkedHashSet 额外记录插入顺序；TreeSet 用红黑树排序、可范围查询但要求元素可比。判重依据是 hashCode 定桶加 equals 核对（Object 契约的强制执行现场），排序依据是比较规则。本节用去重实验验证三种 Set 的行为差异，并给出选型表。

加不进去，就是 Set 的全部本领

业务里有一类高频需求：一批数据里挑出唯一的。登记号去重、关键词去重、访问账号去重——用 List 加 contains 判重的写法在数据量上来后会慢到不可用（contains 是逐个扫）。Set 把"判重"做成入队的第一道关卡：

import java.util.HashSet;
import java.util.Set;

public class SetDemo {
    public static void main(String[] args) {
        Set<String> ids = new HashSet<>();
        System.out.println(ids.add("A001"));   // 输出：true  首次加入成功
        System.out.println(ids.add("A002"));   // 输出：true
        System.out.println(ids.add("A001"));   // 输出：false 重复 直接被拒
        System.out.println("集合大小：" + ids.size());   // 输出：集合大小：2
        System.out.println(ids.contains("A001"));        // 输出：true 哈希定位 极快
        ids.remove("A002");
        System.out.println(ids);                          // 输出：[A001]
    }
}
​

add 的返回值就是判重结果：true 表示新客入队、false 表示已有同款、拒绝入内。对 String 这类已正确实现契约的类型，Set 直接可用；对自定义类型，判重完全依据第 2.3 节的 Object 契约——先 hashCode 定桶、再 equals 核对，只重写一个的后果（重复入库、查无此人）在 2.3 节已经完整复现，这里不重复贴代码，只把结论钉死：自定义类入 Set，equals 与 hashCode 必须成对重写。

三种 Set：快、有序、排队

HashSet 只管快不管顺序——两次遍历输出的顺序可能不同，也肯定不是插入顺序。需要"记住入队顺序"或"按大小排好队"时换另外两种：

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

public class SetKindDemo {
    public static void main(String[] args) {
        Set<String> hash = new HashSet<>();
        Set<String> linked = new LinkedHashSet<>();
        Set<String> tree = new TreeSet<>();
        for (String s : new String[]{"登记", "变更", "注销", "登记"})
            { hash.add(s); linked.add(s); tree.add(s); }
        System.out.println("HashSet    输出：" + hash);     // 顺序不可预期 与哈希分布有关
        System.out.println("LinkedHashSet：" + linked);     // 输出：[登记, 变更, 注销] 保持插入顺序
        System.out.println("TreeSet     输出：" + tree);    // 输出按字典序 [变更, 注销, 登记]

        TreeSet<Integer> nums = new TreeSet<>();
        for (int x : new int[]{50, 20, 90, 40}) nums.add(x);
        System.out.println("第一个与最后一个：" + nums.first() + " " + nums.last());  // 输出：20 90
        System.out.println("小于50的元素：" + nums.headSet(50));   // 输出：[20, 40]
        System.out.println("大于等于40的元素：" + nums.tailSet(40)); // 输出：[40, 50, 90]
    }
}
​

三种实现的底层各不相同，性能与代价也各有出处：

HashSet 的增删查平均接近常数级；TreeSet 的增删查是对数级——慢一点，换来"永远排好队"和范围查询能力（headSet、tailSet、first、last 这些方法只有有序集合才有）。LinkedHashSet 是 HashSet 的带账本版本：哈希定位照旧，双向链表额外把插入顺序串起来，遍历时按账本走。

TreeSet 的入场券：必须可比

TreeSet 要给元素排序，元素就得能比大小。字符串与包装类天生可比（实现过 Comparable 接口，第 3 章发证科发的那张证）；自定义类型要么实现 Comparable、要么建 TreeSet 时递一个比较器：

import java.util.Comparator;
import java.util.Set;
import java.util.TreeSet;

class Applicant implements Comparable<Applicant> {   // 方式一：类自己实现可比
    String name;
    int score;
    Applicant(String name, int score) { this.name = name; this.score = score; }

    @Override
    public int compareTo(Applicant o) {
        return Integer.compare(o.score, this.score);   // 按分数从高到低
    }
    @Override public String toString() { return name + ":" + score; }
}

public class TreeSortDemo {
    public static void main(String[] args) {
        Set<Applicant> byScore = new TreeSet<>();
        byScore.add(new Applicant("赵一", 82));
        byScore.add(new Applicant("钱二", 95));
        byScore.add(new Applicant("孙三", 88));
        System.out.println(byScore);   // 输出：[钱二:95, 孙三:88, 赵一:82] 按分排好

        // 方式二：建集合时递比较器 按名字排
        Set<Applicant> byName = new TreeSet<>(Comparator.comparing(a -> a.name));
        byName.add(new Applicant("赵一", 82));
        byName.add(new Applicant("钱二", 95));
        System.out.println(byName);   // 输出：[钱二:95, 赵一:82] 按名字字典序
    }
}
​

compareTo 的返回值约定：负数表示排前面、零表示相等、正数表示排后面；比较基本类型用 Integer.compare 这类工具方法，别用相减——两个大数相减可能溢出翻转符号。还有一个隐蔽的坑：compareTo 返回零时 TreeSet 视为同一个元素，只保留一个。若按分数排序但两名申请者恰好同分，第二位就进不去了——排序键必须能唯一标识，或者明确接受"同分即同人"的语义。这与 HashSet 的判重依据不同（那边看 equals 与 hashCode），同分不同名的对象在 HashSet 里能共存、在按分排序的 TreeSet 里会消失一个，选型时要意识到两套判据的差异。

完整案例：背景：活动系统要统计参与账号数，日志里同一天同一账号可能多条，还要按当天注册的先后顺序展示前若干名。操作：第一步用 LinkedHashSet 去重并保留出现顺序；第二步从去重结果构建 TreeSet 排名：

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

public class DedupCase {
    public static void main(String[] args) {
        String[] logs = {"u3", "u1", "u3", "u2", "u1", "u4"};
        Set<String> seen = new LinkedHashSet<>();
        for (String u : logs) seen.add(u);              // 去重 保首次出现顺序
        System.out.println("去重后的参与顺序：" + seen);  // 输出：[u3, u1, u2, u4]
        System.out.println("参与账号数：" + seen.size()); // 输出：参与账号数：4
        Set<String> sorted = new TreeSet<>(seen);        // 排好队的副本
        System.out.println("账号排序展示：" + sorted);    // 输出：[u1, u2, u3, u4]
    }
}
​

结果：去重、计数、保序展示一次完成。解读：两个 Set 各干最擅长的事——LinkedHashSet 管"按出现顺序的唯一性"，TreeSet 管"排好队的展示"；复制成本远低于自己写判重循环。变式：若只按内容去重且量极大、连账本都不需要，退回 HashSet 更省内存；若要去重的对象是可变的（入队后会改字段），重读第 2.3 节末尾那条铁律——改字段等于搬家没销户，定位必然漂移。

本节要点回顾

• Set 的契约只有不可重复：add 返回值即判重结果；自定义类入 Set 必须 equals 与 hashCode 成对重写，两步判重正是 Object 契约的强制执行现场
• 三种实现各管一头：HashSet 最快无序、LinkedHashSet 保插入序、TreeSet 按规则排序并支持范围查询
• TreeSet 的入场券是可比：元素实现 Comparable 或建集合时递比较器；比较用 compare 工具方法，相减会溢出
• compareTo 返回零等于同一个元素：排序键必须唯一，否则同键者只剩一个——与 HashSet 的判据不同，选型要分清
• 去重保序两步走：LinkedHashSet 去重保序、再转 TreeSet 排序展示，两个 Set 各司其职

Set 判重的两步（hashCode 定桶、equals 核对）在 Map 里原封不动地用在键上。下一节进索引柜：HashMap 一次 put 背后的定位、碰撞、扩容，以及可变键的事故。