Set集合去重原理是啥

在 Java 中，Set 集合去重的原理本质上依赖于两个方法：hashCode() 和 equals()。不同实现类（如 HashSet、LinkedHashSet、TreeSet）在细节上略有差异，但核心思想一致。

一、最常见：HashSet 的去重原理

1️⃣ 核心结论

Set 判断两个元素是否重复，先比较 hashCode()，再比较 equals()。

2️⃣ 去重流程（重点）

当你调用：

set.add(obj);

HashSet 内部会做以下事情：

1. 计算对象的 hashCode

   int hash = obj.hashCode();
   

2. 根据 hash 找到对应的“桶（bucket）”
3. 如果该桶里没有元素 → 直接加入
4. 如果该桶里有元素：
   • 用 equals() 逐个比较
   • 只要有一个 equals 返回 true → 认为是重复元素，不加入
   • 全部 equals 都返回 false → 加入

✅ 只有 hashCode 相同 且 equals 为 true，才算重复

3️⃣ 为什么要用 hashCode？

• 提高性能
• 避免每次都调用 equals() 逐个比较
• 先快速定位，再精确判断

二、代码示例说明

示例 1：String 的去重（天然支持）

Set<String> set = new HashSet<>();
set.add("abc");
set.add("abc");

System.out.println(set.size()); // 1

原因：

• String 重写了 hashCode() 和 equals()
• 内容相同 → hash 相同 → equals true → 去重

示例 2：自定义对象（重点）

class Person {
    String name;
    int age;

    Person(String name, int age) {
        this.name = name;
        this.age = age;
    }
}

Set<Person> set = new HashSet<>();
set.add(new Person("张三", 18));
set.add(new Person("张三", 18));

System.out.println(set.size()); // 2 ❌ 没去重

原因：

• 没重写 hashCode() 和 equals()
• 默认使用 Object 的方法
• 比较的是 内存地址

✅ 正确写法（重写 hashCode + equals）

class Person {
    String name;
    int age;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Person)) return false;
        Person p = (Person) o;
        return age == p.age && Objects.equals(name, p.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }
}

此时：

set.size(); // 1 ✅

三、TreeSet 的去重原理（另一种）

TreeSet 不使用 hashCode 和 equals，而是使用：

✅ Comparable 或 Comparator

Set<Integer> set = new TreeSet<>();
set.add(3);
set.add(3);

判断重复规则：

• compareTo() 返回 0 → 认为是相同元素

⚠️ 注意：

• compareTo() == 0 必须和逻辑相等一致
• 否则会出现“逻辑相等但没去重”的坑

四、总结对比

五、一句话记忆版 ✅

HashSet 去重：先 hashCode 定位，再 equals 判断；
TreeSet 去重：compareTo 返回 0 就是重复。

如果你愿意，我也可以帮你画一张 HashSet 底层结构图 或结合 面试高频问法 给你总结。