HashSet

本章定位：理解 HashSet 基于 HashMap 的实现原理，掌握 hashCode/equals 契约在去重中的核心作用。HashSet 是"不允许重复、不保证顺序"的 Set 标准实现，飞翔科技的打卡去重、权限集合等场景均基于它构建。

概述

HashSet 的底层完全委托给 HashMap——集合的元素作为 Map 的 key，所有 key 共享同一个虚拟 value（一个名为 PRESENT 的静态常量 Object）。这种设计体现了"复用而非重写"的工程哲学。

特性	描述
底层实现	`HashMap<E, Object>`
元素唯一性	依赖 `hashCode()` + `equals()`
元素顺序	无序（不保证与插入顺序一致）
允许 null	是（仅一个，HashMap 允许一个 null key）
线程安全	否
默认容量	16（继承自 HashMap）
负载因子	0.75（继承自 HashMap）
add/remove/contains	平均 O(1)

方法速查表

方法	实现原理	时间复杂度
`add(E e)`	`map.put(e, PRESENT) == null`	平均 O(1)
`remove(Object o)`	`map.remove(o) == PRESENT`	平均 O(1)
`contains(Object o)`	`map.containsKey(o)`	平均 O(1)
`size()`	`map.size()`	O(1)
`clear()`	`map.clear()`	O(n)
`isEmpty()`	`map.isEmpty()`	O(1)
`iterator()`	返回 `map.keySet().iterator()`	—

核心原理

HashSet 源码结构

public class HashSet<E> extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {

    private transient HashMap<E, Object> map;

    // 所有元素共享的虚拟值
    private static final Object PRESENT = new Object();

    // 构造方法——创建 HashMap
    public HashSet() {
        map = new HashMap<>();
    }

    // add 方法——本质是 map.put
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
        // HashMap.put 返回旧值；新 key 返回 null → 添加成功
    }

    // contains 方法——本质是 map.containsKey
    public boolean contains(Object o) {
        return map.containsKey(o);
    }

    // remove 方法——本质是 map.remove
    public boolean remove(Object o) {
        return map.remove(o) == PRESENT;
    }
}

为什么 HashSet 不保证顺序

HashSet 的"无序"源于 HashMap 的哈希表结构：元素根据 hashCode 取模后分布在数组的不同槽位中，遍历顺序取决于哈希值分布、数组容量和冲突链的长度，与插入顺序无关。

hashCode 与 equals 契约

这是 HashSet 正确工作的理论基础，也是面试中的高频考点。

重写 equals 必须重写 hashCode

// ❌ 错误：重写了 equals 但未重写 hashCode
class Employee {
    private String id;
    private String name;

    public Employee(String id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Employee)) return false;
        Employee emp = (Employee) o;
        return Objects.equals(id, emp.id);  // 仅用 id 判断相等
    }
    // 未重写 hashCode() —— 继承 Object 的使用内存地址的 native hashCode
}

// 测试
Set<Employee> set = new HashSet<>();
Employee e1 = new Employee("001", "大翔");
Employee e2 = new Employee("001", "大翔");
set.add(e1);
System.out.println(set.contains(e2));  // false! 应该返回 true
System.out.println(e1.equals(e2));     // true
System.out.println(e1.hashCode() == e2.hashCode());  // false! 不满足契约

问题分析：

e1.equals(e2) 返回 true（id 相同），但 hashCode() 不同
HashSet 先用 hashCode 定位桶，两个不同 hashCode 落到了不同的桶
即使在同一桶，也会先比较 hashCode（HashMap 优化），hashCode 不同直接认为不相等

// ✅ 正确：同时重写 equals 和 hashCode
class Employee {
    private String id;
    private String name;

    public Employee(String id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof Employee)) return false;
        Employee emp = (Employee) o;
        return Objects.equals(id, emp.id);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id);  // 与 equals 使用相同字段
    }
}

// 测试
Set<Employee> set = new HashSet<>();
Employee e1 = new Employee("001", "大翔");
Employee e2 = new Employee("001", "大翔");
set.add(e1);
System.out.println(set.contains(e2));  // true ✓
System.out.println(e1.equals(e2));     // true ✓
System.out.println(e1.hashCode() == e2.hashCode());  // true ✓

hashCode/equals 契约规则

规则	说明
自反性	`x.equals(x)` 必须返回 true
对称性	`x.equals(y)` == `y.equals(x)`
传递性	若 `x.equals(y)` 且 `y.equals(z)`，则 `x.equals(z)`
一致性	多次调用 `equals` 结果应一致（前提：比较信息未变）
非空性	`x.equals(null)` 必须返回 false
hashCode 一致性	若 `x.equals(y)`，则 `x.hashCode() == y.hashCode()`（必要非充分）
逆命题不成立	`x.hashCode() == y.hashCode()` 不能推出 `x.equals(y)`（哈希冲突）

完整示例

示例一：飞翔科技考勤打卡去重

import java.util.*;

// 场景：飞翔科技每日考勤系统，一人一天打卡多次只计一次
class AttendanceRecord {
    private String employeeId;
    private String date;     // 日期：yyyy-MM-dd
    private String time;     // 打卡时间：HH:mm:ss

    public AttendanceRecord(String employeeId, String date, String time) {
        this.employeeId = employeeId;
        this.date = date;
        this.time = time;
    }

    // 同一员工同一天视为同一条记录（忽略具体时间）
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof AttendanceRecord)) return false;
        AttendanceRecord that = (AttendanceRecord) o;
        return Objects.equals(employeeId, that.employeeId) 
            && Objects.equals(date, that.date);
    }

    @Override
    public int hashCode() {
        return Objects.hash(employeeId, date);
    }

    @Override
    public String toString() {
        return employeeId + " | " + date + " | " + time;
    }
}

public class AttendanceDedup {
    public static void main(String[] args) {
        Set<AttendanceRecord> todayAttendance = new HashSet<>();

        // 小崔上午打了 3 次卡（迟到边缘试探...）
        todayAttendance.add(new AttendanceRecord("EMP001", "2024-03-15", "08:55:01"));
        todayAttendance.add(new AttendanceRecord("EMP001", "2024-03-15", "08:58:22"));
        todayAttendance.add(new AttendanceRecord("EMP001", "2024-03-15", "08:59:47"));

        // 白歌上午准点到
        todayAttendance.add(new AttendanceRecord("EMP002", "2024-03-15", "09:00:05"));

        // 大翔一大早就来了
        todayAttendance.add(new AttendanceRecord("EMP003", "2024-03-15", "07:30:00"));

        // 孔蓝下午才打卡（惭愧）
        todayAttendance.add(new AttendanceRecord("EMP004", "2024-03-15", "13:01:00"));

        System.out.println("今日打卡原始记录数: 7 条");
        System.out.println("今日实际出勤人数: " + todayAttendance.size() + " 人\n");

        System.out.println("--- 今日出勤明细 ---");
        todayAttendance.forEach(record -> 
            System.out.println("  " + record)
        );

        // 查找某员工是否已打卡
        AttendanceRecord query = new AttendanceRecord("EMP001", "2024-03-15", "");
        System.out.println("\n小崔今天打卡了吗？ " + todayAttendance.contains(query));
    }
}

运行输出：
今日打卡原始记录数: 7 条
今日实际出勤人数: 4 人

--- 今日出勤明细 ---
  EMP001 | 2024-03-15 | 08:59:47
  EMP002 | 2024-03-15 | 09:00:05
  EMP003 | 2024-03-15 | 07:30:00
  EMP004 | 2024-03-15 | 13:01:00

小崔今天打卡了吗？ true

示例二：Set 运算（交集、并集、差集）

import java.util.*;

// 场景：飞翔科技技术部和产品部的权限交集分析
public class SetOperations {
    public static void main(String[] args) {
        Set<String> techDept = new HashSet<>(Arrays.asList(
            "代码仓库读写", "服务器SSH", "数据库读写", "日志查看", "K8s部署"
        ));
        Set<String> productDept = new HashSet<>(Arrays.asList(
            "需求文档编辑", "原型工具", "数据库只读", "日志查看", "BI报表"
        ));

        System.out.println("技术部权限: " + techDept);
        System.out.println("产品部权限: " + productDept);

        // 并集（两个部门的所有权限）
        Set<String> union = new HashSet<>(techDept);
        union.addAll(productDept);
        System.out.println("\n并集（所有权限）: " + union);

        // 交集（两个部门共有的权限）
        Set<String> intersection = new HashSet<>(techDept);
        intersection.retainAll(productDept);
        System.out.println("交集（共有权限）: " + intersection);

        // 差集（技术部有但产品部没有的权限）
        Set<String> difference = new HashSet<>(techDept);
        difference.removeAll(productDept);
        System.out.println("差集（技术部独有）: " + difference);

        // 判断子集
        Set<String> basicPerms = new HashSet<>(Arrays.asList("日志查看"));
        System.out.println("\n基础权限是技术部的子集？ " + techDept.containsAll(basicPerms));
    }
}

运行输出：
技术部权限: [服务器SSH, 数据库读写, 代码仓库读写, K8s部署, 日志查看]
产品部权限: [BI报表, 需求文档编辑, 数据库只读, 原型工具, 日志查看]

并集（所有权限）: [原型工具, 服务器SSH, 数据库只读, 数据库读写, 代码仓库读写, BI报表, K8s部署, 需求文档编辑, 日志查看]
交集（共有权限）: [日志查看]
差集（技术部独有）: [服务器SSH, 数据库读写, 代码仓库读写, K8s部署]

基础权限是技术部的子集？ true

易错场景

反例一：可变对象作为 HashSet 元素后修改字段

这是 HashSet 使用中的经典大坑，孔蓝在做代码审查时经常发现：

// ❌ 错误：将可变对象放入 HashSet 后修改其 hashCode 相关字段
class MutableEmployee {
    String id;
    String name;
    
    MutableEmployee(String id, String name) {
        this.id = id; this.name = name;
    }
    
    @Override public boolean equals(Object o) {
        if (!(o instanceof MutableEmployee)) return false;
        return Objects.equals(id, ((MutableEmployee) o).id);
    }
    @Override public int hashCode() { return Objects.hash(id); }
    @Override public String toString() { return id + ":" + name; }
}

Set<MutableEmployee> set = new HashSet<>();
MutableEmployee emp = new MutableEmployee("001", "小崔");
set.add(emp);
System.out.println("添加后: " + set.contains(emp));  // true

emp.id = "002";  // 修改了决定 hashCode 的字段！
System.out.println("修改后: " + set.contains(emp));  // false! 元素丢失！
// HashSet 按新的 hashCode 查找，但 emp 仍在旧的桶中
// 甚至 remove(emp) 也无法删除它，造成"内存泄漏"

原理图解：

HashSet 存储:
桶[hash("001")] → [emp: id="001"]
                    ↓ emp.id 被改为 "002"
桶[hash("002")] → (空)

contains(emp): 计算 hash("002") → 查找桶[hash("002")] → 空 → 返回 false
但 emp 实际存在于桶[hash("001")] 中！

纠正方案：

// ✅ 方案一：使用不可变字段作为 hashCode/equals 依据
class ImmutableEmployee {
    private final String id;   // final 确保不可修改
    private final String name;
    
    public ImmutableEmployee(String id, String name) {
        this.id = id; this.name = name;
    }
    // equals / hashCode 基于 final 字段，绝对安全
}

// ✅ 方案二：从 Set 中移除 → 修改 → 重新添加
set.remove(emp);
emp.id = "002";
set.add(emp);

反例二：HashSet 中 null 的陷阱

// HashSet 允许一个 null 元素
Set<String> set = new HashSet<>();
set.add(null);       // true
set.add(null);       // false（重复）
set.add("A");

// 遍历到 null 时调用方法会 NPE
for (String s : set) {
    System.out.println(s.length());  // NPE! s 可能是 null
}

建议：如果业务上不允许 null 元素，使用 Objects.requireNonNull() 或 Optional 做防御性检查。

面试考点

Q1：HashSet 如何保证元素不重复？

HashSet 底层委托给 HashMap，元素作为 key 存入，所有 key 共享同一个 PRESENT 虚拟值。HashMap 通过 hashCode() 定位桶，通过 equals() 判断是否重复。如果 hashCode 相等且 equals 返回 true，则 put 返回旧值（不等于 null），HashSet 的 add 判断 put() == null 从而拒绝重复添加。

Q2：为什么重写 equals 必须重写 hashCode？

这是 Java 对象契约的要求，也是 HashSet/HashMap 正确工作的前提。如果只重写 equals 不重写 hashCode，两个 equals 返回 true 的对象可能拥有不同的 hashCode，导致 HashMap 将它们放入不同的桶中，从而破坏"相等对象必须存在于相同桶"的不变式。具体表现为：set.add(obj1) 后 set.contains(obj2) 返回 false（尽管 obj1.equals(obj2) 为 true）。

Q3：HashSet 和 TreeSet 的区别？

维度 HashSet TreeSet
底层 HashMap TreeMap（红黑树）
顺序无序自然顺序或 Comparator 排序
时间复杂度 O(1) 平均 O(log n)
null 允许 1 个不允许（需要比较）
依赖 hashCode + equals compareTo / compare
适用场景快速去重有序集合

维度	HashSet	TreeSet
底层	HashMap	TreeMap（红黑树）
顺序	无序	自然顺序或 Comparator 排序
时间复杂度	O(1) 平均	O(log n)
null	允许 1 个	不允许（需要比较）
依赖	hashCode + equals	compareTo / compare
适用场景	快速去重	有序集合

Q4：HashSet 的 add 方法时间复杂度真的是 O(1) 吗？

平均 O(1)，但不总是。hashCode 分布良好时，HashMap 的 put 操作确实是 O(1)；但如果 hashCode 分布不均导致严重冲突（所有元素都落在一个桶内），HashMap 退化为链表（JDK 7）或红黑树 O(log n)（JDK 8 树化后）。最坏情况 O(n)（JDK 7）或 O(log n)（JDK 8）。

Q5：如何从 HashSet 中按插入顺序取出元素？

HashSet 本身不支持顺序。如果需要按插入顺序，使用 LinkedHashSet（HashSet 的子类，内部维护双向链表记录插入顺序）；如果需要按排序顺序，使用 TreeSet。LinkedHashSet 的 add/remove/contains 仍是 O(1)，只是额外维护了链表。