--- title: "01-HashSet" created: 2025-12-02 tags: - Java --- # HashSet > [!note] 定位说明 > Set 系列第 1 篇详篇，日常默认实现。核心读法：**HashSet 就是"只用 key 的 HashMap"**——去重靠 hashCode()+equals() 双重判定，JDK 8 冲突多了还会树化。读懂本篇等于二次巩固 HashMap。 `HashSet` 是 Java 中最常用的 `Set` 实现类，基于 **哈希表（本质是** `HashMap` **的键集合）** 实现，具有 **高效存储和查询** 的特点。 ### **一、核心原理与数据结构** #### **1. 底层实现** - **基于** `HashMap` **实现**：`HashSet` 的底层使用 `HashMap` 存储元素，每个元素作为 `HashMap` 的 **键（Key）**，值（Value）统一为一个静态对象 `PRESENT`（相当于占位符）。 ```java private static final Object PRESENT = new Object(); private transient HashMap 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` 不保证元素插入顺序，遍历顺序可能与插入顺序不一致（由哈希表的存储逻辑决定）。 - **示例**： ```java HashSet 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`。 - **解决方案**： ```java Set synchronizedSet = Collections.synchronizedSet(new HashSet<>()); // 手动同步 // 或使用并发容器（如 ConcurrentHashMap 的键集合） ``` ### **三、使用场景** #### **1. 数据去重** - **典型场景**：过滤集合中的重复元素（如用户注册时校验重复邮箱）。 ```java List listWithDuplicates = Arrays.asList("A", "B", "A", "C"); Set uniqueSet = new HashSet<>(listWithDuplicates); // 去重后元素为 ["A", "B", "C"] ``` #### **2. 快速查询存在性** - **优势**：判断元素是否存在的效率远高于 `List`（`List` 的 `contains` 需遍历，时间复杂度 O (n)）。 ```java Set emailSet = new HashSet<>(users.stream().map(User::getEmail).collect(Collectors.toSet())); boolean exists = emailSet.contains("test@example.com"); // 快速判断邮箱是否已注册 ``` #### **3. 高性能集合操作** - **交集、并集、差集**：利用 `Set` 的特性高效实现集合运算。 ```java Set setA = new HashSet<>(Arrays.asList(1, 2, 3)); Set setB = new HashSet<>(Arrays.asList(3, 4, 5)); Set intersection = new HashSet<>(setA); // 交集 intersection.retainAll(setB); // 结果为 [3] ``` ### **四、注意事项与最佳实践** #### **1. 自定义对象存入 HashSet** - **必须重写** `equals()` **和** `hashCode()`： 若未重写，默认使用 `Object` 的方法（`hashCode()` 返回对象地址哈希值，`equals()` 比较引用地址），导致逻辑错误。 ```java 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`）。 ```java HashSet set = new HashSet<>(); set.add(null); // 合法 set.add(null); // 重复，不会插入 ``` #### **3. 遍历顺序与性能优化** - **避免依赖遍历顺序**：若需要有序遍历，改用 `LinkedHashSet`（按插入顺序）或 `TreeSet`（按排序顺序）。 - **初始化容量优化**：若已知元素数量，指定初始容量可减少扩容次数，提升性能： ```java HashSet 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`，以满足特定需求。 ### 拓展 1. **迭代顺序的不确定性** HashSet 的遍历顺序不保证与插入顺序一致，也不遵循任何特定规律。该顺序可能因 JVM 版本、哈希函数分布或扩容操作而改变。若需保留插入顺序，应使用 **LinkedHashSet**；若需排序，则选择 **TreeSet**。 2. **哈希冲突与性能平衡** - **负载因子权衡**：默认负载因子 0.75 在空间与时间效率间取得平衡。降低负载因子（如 0.5）减少冲突概率但增加内存开销，调高则反之。 - **初始容量优化**：若预知元素数量为 N，建议初始容量设为 **(N / 0.75) + 1** 以避免频繁扩容。 3. **自定义对象的不可变性** 若存储自定义可变对象，修改其影响 **hashCode()** 或 **equals()** 的字段后，可能导致元素“丢失”（因哈希桶定位错误）。建议将 HashSet 中的对象设计为不可变，或在修改后先移除再重新插入。 4. **序列化机制** HashSet 通过自定义 **writeObject()** 和 **readObject()** 方法实现序列化，仅传输元素而非内部结构（如桶数组、红黑树节点），以保证兼容性。 5. **遍历性能** 遍历时间复杂度为 O(n + m)，其中 n 是元素数量，m 是桶数量。初始容量过大但元素稀疏时，遍历效率可能下降。 **常见问题深度解析** 1. **为何重写 equals() 必须同时重写 hashCode()？** - **契约一致性**：Java 规定两个对象 **equals()** 为 true 时，其 **hashCode()** 必须相同。若违反此规则，HashSet可能将逻辑相等的对象存入不同桶，破坏唯一性。 - **示例场景**： ```java class Person { String name; // 仅重写 equals()，未重写 hashCode() @Override public boolean equals(Object o) { /* 比较 name */ } } Set set = new HashSet<>(); set.add(new Person("Alice")); // 哈希值假设为 100 set.contains(new Person("Alice")); // 新对象哈希值 200，直接返回 false ``` 2. **JDK 8 链表转红黑树的阈值为何是 8？** - **统计学依据**：哈希冲突遵循泊松分布，链表长度达到 8 的概率极低（约 1e-6）。此阈值是对极端情况的保护，避免恶意哈希攻击导致性能骤降。 3. **为何扩容时容量翻倍？** - **位运算优化**：翻倍后新容量为 2 的幂，计算桶位置时可通过 **hash & (capacity - 1)** 替代取模运算，提升效率。 - **分散冲突**：翻倍扩容使元素重新散列到新桶，可能减少链表长度或树化概率。 4. **线程安全的替代方案** - **Collections.synchronizedSet()**：通过同步代码块包装方法调用，适合低并发场景。 - **并发容器**：**ConcurrentHashMap.newKeySet()** 或 **CopyOnWriteArraySet**。前者适用于高并发读写，后者适合读多写少。 ### **实战建议** - **去重场景**：优先使用 **HashSet**（时间复杂度 O(1)），而非 **List** 的 **contains()**（O(n)）。 - **内存敏感场景**：调整初始容量和负载因子，避免无谓扩容。 - **对象设计**：作为 HashSet 元素的类应覆写 **hashCode()** 和 **equals()**，推荐使用 IDE 自动生成或 Lombok 的 **@EqualsAndHashCode**。 通过理解这些细节，能更高效地利用 HashSet 特性，避免常见陷阱，提升代码质量与性能。 --- ⬅️ [[00-Set总览|00-Set总览]] 🏠 [[00-Java|00-Java]] ➡️ [[02-LinkedHashSet|LinkedHashSet]]