HashSet

ℹ️定位说明

Set 系列第 1 篇详篇，日常默认实现。核心读法：HashSet 就是"只用 key 的 HashMap"——去重靠 hashCode()+equals() 双重判定，JDK 8 冲突多了还会树化。读懂本篇等于二次巩固 HashMap。

HashSet 是 Java 中最常用的 Set 实现类，基于 哈希表（本质是 HashMap 的键集合） 实现，具有 高效存储和查询 的特点。

一、核心原理与数据结构

1. 底层实现

基于 HashMap 实现：HashSet 的底层使用 HashMap 存储元素，每个元素作为 HashMap 的 键（Key），值（Value）统一为一个静态对象 PRESENT（相当于占位符）。

  private static final Object PRESENT = new Object();
  private transient HashMap<E, Object> map;

  public HashSet() {
      map = new HashMap<>();
  }

  public boolean add(E e) {
      return map.put(e, PRESENT) == null; // 键不存在时插入，返回 true
  }

哈希表特性：通过哈希函数（hashCode()）计算元素存储位置，利用链表或红黑树（JDK 8+ 后，链表长度 ≥ 8 时转为红黑树）解决哈希冲突。

2. 唯一性实现

依赖 equals() 和 hashCode()：
1. 插入元素时，先通过 hashCode() 计算哈希值，确定存储桶（Bucket）位置。
2. 若桶内无元素，直接插入；若有元素，通过 equals() 比较是否相等：
  - 相等：视为重复元素，不插入。
  - 不等：通过链地址法（链表或红黑树）存储在桶内。

二、关键特性

1. 无序性

元素顺序不可预测：HashSet 不保证元素插入顺序，遍历顺序可能与插入顺序不一致（由哈希表的存储逻辑决定）。
示例：

  HashSet<String> set = new HashSet<>();
  set.add("A");
  set.add("B");
  set.add("C");
  for (String s : set) {
      System.out.print(s + " "); // 输出可能为 "A B C" "B A C" 等任意顺序
  }

2. 性能表现

平均时间复杂度为 O (1)：
- 插入（add）、删除（remove）、查询（contains）操作在理想情况下（哈希分布均匀）效率极高。
- 极端情况下（哈希冲突严重，如所有元素哈希值相同），退化为链表操作，时间复杂度为 O (n)，但 JDK 8+ 通过红黑树优化了这种情况（链表长度≥ 8 时转为红黑树，时间复杂度降至 O (log n)）。

3. 线程安全性

非线程安全：多线程环境下并发修改（如同时 add/remove）可能导致数据不一致或 ConcurrentModificationException。
解决方案：

  Set<String> synchronizedSet = Collections.synchronizedSet(new HashSet<>()); // 手动同步
  // 或使用并发容器（如 ConcurrentHashMap 的键集合）

三、使用场景

1. 数据去重

典型场景：过滤集合中的重复元素（如用户注册时校验重复邮箱）。

  List<String> listWithDuplicates = Arrays.asList("A", "B", "A", "C");
  Set<String> uniqueSet = new HashSet<>(listWithDuplicates); // 去重后元素为 ["A", "B", "C"]

2. 快速查询存在性

优势：判断元素是否存在的效率远高于 List（List 的 contains 需遍历，时间复杂度 O (n)）。

  Set<String> emailSet = new HashSet<>(users.stream().map(User::getEmail).collect(Collectors.toSet()));
  boolean exists = emailSet.contains("test@example.com"); // 快速判断邮箱是否已注册

3. 高性能集合操作

交集、并集、差集：利用 Set 的特性高效实现集合运算。

  Set<Integer> setA = new HashSet<>(Arrays.asList(1, 2, 3));
  Set<Integer> setB = new HashSet<>(Arrays.asList(3, 4, 5));
  Set<Integer> intersection = new HashSet<>(setA); // 交集
  intersection.retainAll(setB); // 结果为 [3]

四、注意事项与最佳实践

1. 自定义对象存入 HashSet

必须重写 equals() 和 hashCode()：

若未重写，默认使用 Object 的方法（hashCode() 返回对象地址哈希值，equals() 比较引用地址），导致逻辑错误。

  class User {
      private String id;
      // 省略构造器、getter

      // 重写 hashCode() 和 equals()（根据业务唯一标识，如 id）
      @Override
      public int hashCode() {
          return Objects.hash(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);
      }
  }

2. null 值支持

允许存储一个 null：与 HashMap 一致，HashSet 允许插入一个 null 元素（其他 Set 实现类如 TreeSet 不支持 null）。

  HashSet<String> set = new HashSet<>();
  set.add(null); // 合法
  set.add(null); // 重复，不会插入

3. 遍历顺序与性能优化

避免依赖遍历顺序：若需要有序遍历，改用 LinkedHashSet（按插入顺序）或 TreeSet（按排序顺序）。
初始化容量优化：若已知元素数量，指定初始容量可减少扩容次数，提升性能：

  HashSet<String> set = new HashSet<>(16); // 初始容量为 16（默认负载因子 0.75，即元素达 12 时扩容）

默认负载因子为 0.75，当元素数量超过容量 × 0.75 时自动扩容（新容量为原来的两倍）。合理设置初始容量可以避免扩容带来的 rehash 成本。

五、与其他 Set 实现类对比

维度	HashSet	LinkedHashSet	TreeSet
数据结构	哈希表（HashMap 键集合）	哈希表 + 双向链表	红黑树（TreeMap 键集合）
元素顺序	无序（不可预测）	按插入顺序有序	按自然顺序或定制顺序排序
null 值支持	允许 1 个 null	允许 1 个 null	不允许 null
插入性能	平均 O (1)（最优）	略低于 HashSet（维护链表）	O (log n)（需平衡树结构）
适用场景	快速去重、无需顺序的场景	需要保留插入顺序的去重场景	排序需求明确的唯一性数据（如数值排序）

总结

HashSet 是 Java 中处理 唯一性存储、快速查询、去重场景 的首选工具，其核心优势在于 哈希表的高效性 和 实现简单性。使用时需注意自定义对象的 equals() 和 hashCode() 重写，以及多线程环境下的同步问题。对于有序场景，可切换至 LinkedHashSet 或 TreeSet，以满足特定需求。

拓展

迭代顺序的不确定性

HashSet 的遍历顺序不保证与插入顺序一致，也不遵循任何特定规律。该顺序可能因 JVM 版本、哈希函数分布或扩容操作而改变。若需保留插入顺序，应使用 LinkedHashSet；若需排序，则选择 TreeSet。
哈希冲突与性能平衡
- 负载因子权衡：默认负载因子 0.75 在空间与时间效率间取得平衡。降低负载因子（如 0.5）减少冲突概率但增加内存开销，调高则反之。
- 初始容量优化：若预知元素数量为 N，建议初始容量设为 (N / 0.75) + 1 以避免频繁扩容。
自定义对象的不可变性

若存储自定义可变对象，修改其影响 hashCode() 或 equals() 的字段后，可能导致元素“丢失”（因哈希桶定位错误）。建议将 HashSet 中的对象设计为不可变，或在修改后先移除再重新插入。
序列化机制

HashSet 通过自定义 writeObject() 和 readObject() 方法实现序列化，仅传输元素而非内部结构（如桶数组、红黑树节点），以保证兼容性。
遍历性能

遍历时间复杂度为 O(n + m)，其中 n 是元素数量，m 是桶数量。初始容量过大但元素稀疏时，遍历效率可能下降。

常见问题深度解析

为何重写 equals() 必须同时重写 hashCode()？
- 契约一致性：Java 规定两个对象 equals() 为 true 时，其 hashCode() 必须相同。若违反此规则，HashSet可能将逻辑相等的对象存入不同桶，破坏唯一性。
- 示例场景：

     class Person {
         String name;
         // 仅重写 equals()，未重写 hashCode()
         @Override public boolean equals(Object o) { /* 比较 name */ }
     }
     Set<Person> set = new HashSet<>();
     set.add(new Person("Alice"));  // 哈希值假设为 100
     set.contains(new Person("Alice")); // 新对象哈希值 200，直接返回 false

JDK 8 链表转红黑树的阈值为何是 8？
- 统计学依据：哈希冲突遵循泊松分布，链表长度达到 8 的概率极低（约 1e-6）。此阈值是对极端情况的保护，避免恶意哈希攻击导致性能骤降。
为何扩容时容量翻倍？
- 位运算优化：翻倍后新容量为 2 的幂，计算桶位置时可通过 hash & (capacity - 1) 替代取模运算，提升效率。
- 分散冲突：翻倍扩容使元素重新散列到新桶，可能减少链表长度或树化概率。
线程安全的替代方案
- Collections.synchronizedSet()：通过同步代码块包装方法调用，适合低并发场景。
- 并发容器：ConcurrentHashMap.newKeySet() 或 CopyOnWriteArraySet。前者适用于高并发读写，后者适合读多写少。

实战建议

去重场景：优先使用 HashSet（时间复杂度 O(1)），而非 List 的 contains()（O(n)）。
内存敏感场景：调整初始容量和负载因子，避免无谓扩容。
对象设计：作为 HashSet 元素的类应覆写 hashCode() 和 equals()，推荐使用 IDE 自动生成或 Lombok 的 @EqualsAndHashCode。

通过理解这些细节，能更高效地利用 HashSet 特性，避免常见陷阱，提升代码质量与性能。

⬅️ 00-Set总览 🏠 00-Java ➡️ LinkedHashSet

01-HashSet