HashSet 去重原理：hashCode 和 equals 的双重门卫
去重的本质：两把钥匙
HashSet 去重靠的不是一把钥匙，而是两把：hashCode + equals。
为什么需要两把？因为只用一把不够：
- 只用 equals：每次添加都要遍历整个集合，时间复杂度 O(n)
- 只用 hashCode：hashCode 相等不代表 equals 相等，会误判
- hashCode + equals：先用 hashCode 定位桶，再用 equals 精确比较，O(1)
两阶段判断流程
HashSet.add("hello") 时发生了什么？
┌─────────────────────────────────────────────────────────────┐
│ 第一阶段：hashCode 定位桶 │
├─────────────────────────────────────────────────────────────┤
│ │
│ "hello".hashCode() = 31 │
│ ↓ │
│ index = hash(31) & (16 - 1) = 5 ← 只在 bucket[5] 找 │
│ │
└─────────────────────────────────────────────────────────────┘
┌─────────────────────────────────────────────────────────────┐
│ 第二阶段：equals 精确比较 │
├─────────────────────────────────────────────────────────────┤
│ │
│ bucket[5] 中可能已有元素：[ ] → ["world"] → ... │
│ ↓ │
│ "hello".equals("world") → false，继续找 │
│ "hello".equals("hello") → true，找到相同元素 │
│ ↓ │
│ 相同 → 返回 false，不添加 │
│ 不同 → 插入链表末尾 │
│ │
└─────────────────────────────────────────────────────────────┘代码验证
java
import java.util.*;
public class DeduplicationDemo {
public static void main(String[] args) {
// 基本类型：Integer、String 有现成的 hashCode 和 equals
Set<Integer> numbers = new HashSet<>();
numbers.add(1);
numbers.add(2);
numbers.add(1); // hashCode 相同，equals 也相同，忽略
System.out.println(numbers); // [1, 2]
// 自定义对象：必须同时重写两个方法
Set<Student> students = new HashSet<>();
students.add(new Student("张三", 20));
students.add(new Student("张三", 20)); // 如果 hashCode 和 equals 正确，应该忽略
System.out.println(students.size()); // 1
}
static class Student {
String name;
int age;
Student(String name, int age) {
this.name = name;
this.age = age;
}
// 第一把钥匙：hashCode
@Override
public int hashCode() {
return Objects.hash(name, age);
}
// 第二把钥匙：equals
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student that = (Student) o;
return age == that.age && Objects.equals(name, that.name);
}
@Override
public String toString() {
return name + "(" + age + ")";
}
}
}hashCode 和 equals 的契约
相等的对象必须产生相等的 hashCode。不相等的对象最好产生不同的 hashCode（但不是必须的）。
✅ 正确契约：
equals 返回 true → hashCode 必须相等
hashCode 相等 → equals 不一定返回 true（哈希冲突）
hashCode 不相等 → equals 必须返回 false最容易犯的错误
只重写 equals，不重写 hashCode：
java
// ❌ 错误示范：只重写 equals
class Point {
int x, y;
@Override
public boolean equals(Object o) {
// equals 逻辑正确...
return this.x == ((Point) o).x && this.y == ((Point) o).y;
}
// hashCode 没重写！用的是 Object 的原始 hashCode（内存地址）
}
Set<Point> set = new HashSet<>();
set.add(new Point(1, 2));
set.add(new Point(1, 2)); // equals 返回 true，但 hashCode 不同！
// 结果：HashSet 认为这是两个不同的元素，两个都存进去了哈希冲突与去重效率
哈希冲突（不同的 hashCode 值落在同一个桶）会影响去重效率：
| 哈希质量 | 描述 | 去重效率 |
|---|---|---|
| 完美哈希 | 每个元素 hashCode 互不相同 | O(1)，每次只比一次 |
| 均匀哈希 | 桶内元素少（1-2 个） | O(1)，每次比 1-2 次 |
| 严重冲突 | 大量元素落在同一桶 | O(n)，退化成链表遍历 |
java
// 故意制造严重哈希冲突
class BadHash implements Comparable<BadHash> {
int value;
BadHash(int value) { this.value = value; }
// ❌ 所有实例都返回相同的 hashCode
@Override
public int hashCode() { return 0; }
@Override
public boolean equals(Object o) {
return this.value == ((BadHash) o).value;
}
}
// 10 万元素全部落在同一个桶，退化成链表
Set<BadHash> set = new HashSet<>();
for (int i = 0; i < 100000; i++) {
set.add(new BadHash(i)); // O(n) 每步，10 万元素 = 50 亿次比较！
}String 的特殊优化
String 类对 hashCode 有特殊缓存：
java
// String.hashCode 源码（简化）
public int hashCode() {
int h = hash; // 懒加载计算一次后缓存
if (h == 0 && value.length > 0) {
h = Arrays.hashCode(value);
hash = h;
}
return h;
}这意味着同一个 String 对象多次计算 hashCode 只有第一次有开销。
实际场景：用户去重
java
public class UserDeduplication {
public static void main(String[] args) {
Set<User> users = new HashSet<>();
users.add(new User("u001", "张三"));
users.add(new User("u001", "张三")); // 相同 id，去重
users.add(new User("u002", "李四"));
System.out.println("去重后用户数: " + users.size()); // 2
}
static class User {
String id;
String name;
User(String id, String name) {
this.id = id;
this.name = name;
}
// ✅ 以 id 作为去重依据
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
User user = (User) o;
return Objects.equals(id, user.id);
}
@Override
public int hashCode() {
return Objects.hash(id);
}
// ✅ hashCode 只基于 id，不基于 name
// 两个相同 id 不同 name 的对象视为同一个用户
@Override
public String toString() {
return "User{" + "id='" + id + '\'' + ", name='" + name + '\'' + '}';
}
}
}总结
| 要点 | 说明 |
|---|---|
| 去重两阶段 | hashCode 定位桶 → equals 精确比较 |
| 契约 | equals 为 true 时，hashCode 必须相等 |
| 常见错误 | 只重写 equals，不重写 hashCode |
| 哈希冲突影响 | 严重冲突导致 O(1) 退化为 O(n) |
| 推荐实践 | 用 Objects.hash(field1, field2) 生成 hashCode |
一句话：hashCode 决定去重效率，equals 决定去重规则。两者缺一不可。