HashSet 与哈希表 | JavaSE

HashSet 与哈希表

一、学习目标

完成本章学习后，你应该能够：

  • 能够解释 HashSet 的核心特点与适用场景。
  • 能够说明 HashSet 底层为什么实际上依赖 HashMap。
  • 能够解释哈希值（Hash Code）、哈希表（Hash Table）、桶（Bucket）与哈希碰撞（Hash Collision）的基本概念。
  • 能够描述 HashSet 添加、查询元素的大致工作流程。
  • 能够解释容量（Capacity）、负载因子（Load Factor）、扩容（Resize）之间的关系。
  • 能够理解 JDK 8+ 哈希桶从链表向红黑树转换的基本条件和目的。
  • 能够避免把 hashCode() 错误理解成“随机数”或“对象绝对唯一编号”。

二、核心知识

2.1 HashSet 是什么

HashSet<E> 是 Set<E> 最常用的实现类之一。

基本创建方式：

Set<String> set = new HashSet<>();

它继承了 Set 最重要的语义：

集合中不能保存重复元素。

例如：

Set<String> set = new HashSet<>();

System.out.println(set.add("Java"));
System.out.println(set.add("MySQL"));
System.out.println(set.add("Java"));

第三次添加 "Java" 时，集合不会再保存一份新的 "Java"。

2.2 HashSet 的基本特点

初学阶段可以记住：

HashSet
├── 不允许重复元素
├── 没有 List 式索引
├── 不保证遍历顺序
└── 基于哈希表实现

其中“不保证遍历顺序”尤其重要。

例如：

Set<String> set = new HashSet<>();

set.add("Java");
set.add("MySQL");
set.add("Redis");
set.add("Spring");

不能要求：

Java → MySQL → Redis → Spring

一定按照这个顺序遍历。

所以程序不能依赖 HashSet 当前“碰巧表现出来”的顺序。

2.3 HashSet 底层实际上使用 HashMap

这是理解 HashSet 的第一个关键点。

从实现关系上，可以先建立这样的模型：

HashSet
   │
   │ 内部维护
   ▼
HashMap
   │
   ▼
哈希表

也就是说：

HashSet 自己并没有重新实现一整套独立的哈希表，而是利用 HashMap 完成元素保存。

可以把：

set.add("Java");

粗略理解为内部执行了类似：

map.put("Java", PRESENT);

其中：

  • HashSet 的元素成为 HashMap 的 key；
  • value 使用一个内部共享的占位对象；
  • HashMap 的 key 本身就不能出现逻辑重复；
  • 因此 HashSet 获得了去重能力。

这里暂时只理解这种设计思想。

HashMap 本身会在后面的：

05-15 · HashMap 使用与底层原理

继续深入。

2.4 什么是哈希值

Java 中对象可以通过：

hashCode()

获取一个 int 类型的哈希码。

例如：

String name = "Java";

int hash = name.hashCode();

System.out.println(hash);

注意：

hashCode() 返回的是一个 int 哈希码，而不是“随机数”。

更不能认为：

hashCode = 对象全球唯一身份证号

这是错误的。

2.5 hashCode 不保证唯一

两个不同对象：

Object a = ...;
Object b = ...;

完全可能出现：

a.hashCode() == b.hashCode()

这种现象叫：

哈希碰撞（Hash Collision）

也就是说：

不同对象
    ↓
可能计算得到
    ↓
相同哈希值

因此：

hashCode()

不能单独完成对象相等性判断。

这是为什么 HashSet 的去重还必须结合：

equals()

的重要原因。

2.6 什么是哈希表

哈希表的核心目标是：

根据元素的哈希信息，快速缩小数据可能存在的位置范围。

可以先想象存在一个数组：

table

其中每个数组位置通常称为：

桶（Bucket / Bin）

例如：

index
  0      1      2      3      4      5
  ↓      ↓      ↓      ↓      ↓      ↓
┌────┬────┬────┬────┬────┬────┐
│    │    │    │    │    │    │
└────┴────┴────┴────┴────┴────┘

加入一个对象：

Student A

首先获得它的哈希信息，然后根据当前表长度定位一个桶：

Student A
   ↓
hash
   ↓
计算桶位置
   ↓
table[3]

这样查询时就不需要从头把整个集合逐个扫描一遍。

2.7 为什么哈希表查询通常很快

假设有 10000 个对象。

普通顺序扫描的思想可能是：

第1个
 ↓
第2个
 ↓
第3个
 ↓
...
 ↓
直到找到目标

哈希表则先：

目标对象
   ↓
hash
   ↓
快速确定候选桶
   ↓
只检查该桶中的少量元素

理想情况下，大量元素能够比较均匀地分散到不同桶中。

因此 HashSet 的：

add()
contains()
remove()

通常具有非常优秀的平均性能。

在哈希分布良好的情况下，基本操作平均可以接近：

O(1)

但这是平均复杂度，不是“无论什么情况绝对 O(1)”。

2.8 什么是哈希碰撞

假设：

对象 A → 桶 5
对象 B → 桶 5
对象 C → 桶 5

不同元素最终落到了同一个桶。

这就是：

哈希碰撞。

哈希碰撞本身不是异常。

真正的问题是：

如果大量元素全部堆到同一个桶里，哈希表就失去了快速定位的优势。

因此 HashMap / HashSet 必须设计机制处理冲突。

2.9 JDK 8+ 的桶结构

理解 HashSet 时，可以建立下面这个模型：

HashSet
   ↓
HashMap
   ↓
数组 table
   ↓
每个桶
├── 没有元素
├── 单个结点
├── 链表
└── 红黑树（达到特定条件后）

所以常见的教学总结：

JDK 8 之前：
数组 + 链表

JDK 8 及之后：
数组 + 链表 + 红黑树

方向上是正确的。

但还要注意：

并不是某个桶一出现几个元素就立即变成红黑树。

2.10 为什么需要红黑树

假设所有元素发生严重碰撞：

table[5]
   ↓
A → B → C → D → E → F → G → H → I → ...

如果链表越来越长，那么在这个桶内寻找元素就需要不断向后遍历。

最坏情况下查询性能会逐渐接近：

O(n)

JDK 8+ 在满足条件时可以把桶中的链表转换成：

红黑树（Red-Black Tree）

结构变成类似：

            D
          /   \
         B     F
        / \   / \
       A   C E   H

目的不是为了“看起来高级”，而是：

在严重哈希碰撞情况下改善桶内查询性能。

三、使用方法

3.1 创建 HashSet

最常见：

import java.util.HashSet;
import java.util.Set;

Set<String> set = new HashSet<>();

也可以直接：

HashSet<String> set = new HashSet<>();

普通业务中如果只需要 Set 的抽象能力，通常优先：

Set<String> set = new HashSet<>();

体现面向接口编程。

3.2 添加元素

Set<String> set = new HashSet<>();

set.add("Java");
set.add("MySQL");
set.add("Redis");

add() 返回：

boolean

因此可以直接判断是否真正加入了新元素：

boolean success = set.add("Java");

if (success) {
    System.out.println("添加成功");
} else {
    System.out.println("元素已经存在");
}

3.3 利用 add() 判断重复

例如用户名注册：

Set<String> usernames = new HashSet<>();

if (usernames.add("lingxi")) {
    System.out.println("注册成功");
} else {
    System.out.println("用户名已存在");
}

这里不需要先写：

if (!usernames.contains("lingxi")) {
    usernames.add("lingxi");
}

因为：

add()

自身已经可以通过返回值告诉我们是否新增成功。

3.4 contains()

判断某个元素是否存在：

Set<String> technologies = new HashSet<>();

technologies.add("Java");
technologies.add("Spring");
technologies.add("MySQL");

System.out.println(technologies.contains("Java"));

这是 HashSet 非常典型的使用场景：

这个元素是否存在？

3.5 remove()

删除指定元素：

boolean removed = technologies.remove("MySQL");

如果确实删除了元素：

true

否则：

false

3.6 HashSet 可以保存 null

标准 HashSet 允许保存一个：

null

例如：

Set<String> set = new HashSet<>();

set.add(null);
set.add(null);
set.add("Java");

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

因为 Set 不允许重复，所以即使多次：

add(null);

也只会保存一个 null。

但实际业务代码中是否应该使用 null，应根据系统设计决定。

3.7 HashSet.newHashSet()

JDK 19 开始，Java 提供了：

HashSet.newHashSet(int numElements)

例如已知预计保存约 10000 个元素：

HashSet<String> set = HashSet.newHashSet(10_000);

这里传入的是：

预计元素数量

而不是要求开发者自己根据负载因子计算内部容量。

在 JDK 21 项目中，如果已知预计数据规模，这是一个非常清晰的创建方式。

四、原理与进阶

4.1 默认容量与负载因子

HashSet 背后的 HashMap 默认配置包含：

默认初始容量：16
默认负载因子：0.75

负载因子（Load Factor）可以理解为：

哈希表允许“拥挤到什么程度”再考虑扩容。

假设当前容量：

16

默认负载因子：

0.75

对应扩容阈值通常为：

16 × 0.75 = 12

当元素数量超过相应阈值时，就需要扩大哈希表容量。

4.2 一个重要细节：底层数组是延迟分配的

不要机械理解为：

new HashSet<>();

执行完成的一瞬间，JVM 就一定已经创建好了一个长度 16 的结点数组。

在 OpenJDK 的实现中：

哈希表数组采用延迟初始化策略。

也就是先创建集合对象，真正发生首次插入等需要表空间的操作时，再进行底层数组分配。

因此：

默认初始容量 = 16

描述的是默认容量策略。

而不是说：

执行 new HashSet() 后一定立即分配 16 个桶

这是两个不同层次的概念。

4.3 为什么容量通常使用 2 的幂

OpenJDK HashMap 的桶数量采用 2 的幂。

例如：

16
32
64
128
...

经过哈希扰动后，可以利用：

(n - 1) & hash

高效计算桶索引。

这里：

n = 当前数组长度

由于：

n

是 2 的幂：

n - 1

在二进制中会形成连续的低位 1。

因此可以通过位运算快速完成桶位置计算。

这个公式属于实现原理：

会理解即可，不需要把它当业务 API 背诵。

4.4 HashMap 还会对 hashCode 做一次扰动

底层并不是机械地直接拿：

key.hashCode()

作为最终桶定位值。

OpenJDK HashMap 会对哈希码进行进一步扰动处理，其核心思想类似：

h ^ (h >>> 16)

目的之一是：

让原始哈希码的高位信息也参与低位桶索引计算，提高哈希分布质量。

因此完整思想更接近：

对象
 ↓
hashCode()
 ↓
哈希扰动
 ↓
计算桶索引
 ↓
定位桶

这也是为什么不要把：

hashCode()

简单理解成“数组下标”。

4.5 HashSet 添加元素的大致流程

以：

set.add(element);

为例，可以建立下面的概念模型：

准备添加 element
        ↓
获取 hashCode
        ↓
进行哈希处理
        ↓
计算对应桶位置
        ↓
桶是否为空？
   ┌────┴────┐
   │         │
  是         否
   │         │
直接保存   检查桶中已有元素
             ↓
      hash 与 equals 等判断
             ↓
      ┌──────┴──────┐
      │             │
    已重复         不重复
      │             │
    不添加         添加新结点

注意：

这是一张用于理解 HashSet 的概念流程图。

真正的 OpenJDK 源码还包含：

  • 哈希扰动；
  • 链表处理；
  • 红黑树处理；
  • 扩容；
  • 阈值判断；
  • 多种优化分支。

学习阶段应先掌握主线，而不是一开始陷入源码每一行。

4.6 树化条件不能只记“链表超过 8”

常见简化说法是：

链表长度超过 8 就转换成红黑树。

这个说法不够完整。

OpenJDK 中存在两个重要阈值概念：

TREEIFY_THRESHOLD = 8
MIN_TREEIFY_CAPACITY = 64

也就是说：

当某个桶中的结点数量达到树化阈值时，还要考虑当前哈希表容量。

如果当前 table 容量：

< 64

实现通常优先考虑：

扩容

而不是立即树化。

当 table 已经足够大，并且桶内冲突仍然严重时，才更适合转成红黑树。

因此更准确的记忆是：

桶内冲突严重
+
达到树化阈值
+
table 容量至少达到 64
↓
才可能树化

4.7 为什么容量小时优先扩容

如果 table 很小：

16

某个桶出现大量冲突，原因可能只是：

桶数量太少。

此时把 table 扩大：

16 → 32 → 64

重新分布元素后，原来挤在一起的数据可能自然散开。

因此直接上红黑树未必是最优选择。

这正体现了 HashMap 实现中的设计思想：

先改善整体哈希分布，再处理真正严重的局部碰撞。

4.8 HashSet 为什么平均性能好

当哈希函数分布良好时：

大量元素
 ↓
均匀分散
 ↓
多个桶

理想情况类似：

bucket 0 → A
bucket 1 → D
bucket 2 → B
bucket 3 → F
bucket 4 → C
bucket 5 → E

而不是：

bucket 0 → A → B → C → D → E → F → ...

因此：

好的哈希分布质量是 HashSet 高性能的重要前提。

五、实践应用

5.1 用户名去重

Set<String> usernames = new HashSet<>();

注册：

if (!usernames.add(username)) {
    System.out.println("用户名已存在");
}

非常符合业务语义。

5.2 唯一 ID 集合

例如：

Set<Long> articleIds = new HashSet<>();

用于保存：

已经浏览的文章 ID
已经选择的订单 ID
已经处理的消息 ID

这些场景主要关心：

是否存在

而不是：

排在第几个

5.3 黑名单

Set<String> blockedIps = new HashSet<>();

判断：

if (blockedIps.contains(clientIp)) {
    // 拒绝访问
}

这种“大量成员判断”就是典型哈希集合场景。

5.4 随机生成不重复号码

例如随机生成：

1 ~ 33

范围内的 6 个不重复数字。

可以不断产生随机值并：

numbers.add(number);

因为 HashSet 自动去重，所以：

while (numbers.size() < 6)

即可控制最终数量。

这也是非常典型的 HashSet 入门案例。

六、常见问题

6.1 hashCode 是随机数吗？

不是。

hashCode()：

public int hashCode()

返回的是一个遵守 Java 对象哈希契约的整数。

同一个对象在参与相等性判断的信息没有变化的情况下，在同一次程序执行过程中重复调用 hashCode()，必须保持一致。

6.2 hashCode 是否全球唯一？

不是。

不同对象完全可能：

a.hashCode() == b.hashCode()

这就是哈希碰撞。

因此：

hashCode 相同

不能直接推出：

对象一定相等

6.3 两个对象 equals 相等，hashCode 可以不同吗？

按照 Java 的正式契约：

如果两个对象通过 equals() 判断相等，它们必须拥有相同的哈希码。

也就是：

equals() == true
         ↓
hashCode 必须相同

反过来则不成立：

hashCode 相同

不代表：

equals() 一定为 true

这个问题将在下一章完整展开。

6.4 HashSet 是否线程安全？

不是。

普通：

HashSet

不是线程安全集合。

并发集合属于后续多线程体系。

6.5 HashSet 为什么不保证遍历顺序？

因为 HashSet 的核心设计目标是：

去重
+
高效哈希操作

元素内部位置受到：

  • hash；
  • table 容量；
  • 扩容；
  • 冲突；
  • 桶结构；

等因素影响。

所以业务代码不能依赖 HashSet 的遍历顺序。

6.6 HashSet 是否一定比 ArrayList 快？

不能这么比较。

ArrayList 与 HashSet 解决的问题根本不同。

例如：

按索引访问

ArrayList 更符合需求。

而：

大量判断元素是否存在
+
不允许重复

HashSet 更符合需求。

数据结构选型首先应该看：

业务语义。

其次才比较具体操作复杂度。

6.7 为什么 HashSet 中自定义对象有时去重失败？

因为自定义类如果没有按照业务含义正确设计：

equals()
hashCode()

那么 HashSet 可能无法按照你所谓的：

“内容相同”

进行去重。

这正是下一章的核心问题。

七、练习与验收

7.1 知识问答

  1. HashSet 属于什么集合体系？
  2. HashSet 最核心的特点是什么？
  3. HashSet 底层为什么与 HashMap 有关系？
  4. hashCode() 返回什么类型？
  5. hashCode 是不是随机数？
  6. hashCode 是否保证唯一？
  7. 什么是哈希碰撞？
  8. 什么是哈希表？
  9. 什么是桶？
  10. 哈希表为什么能够提升元素查找效率？
  11. JDK 8+ 一个冲突桶可能使用哪些结构？
  12. 为什么会引入红黑树？
  13. 默认负载因子是多少？
  14. 默认容量策略是多少？
  15. 为什么说底层 table 使用延迟初始化？
  16. 为什么不能只记“链表长度超过 8 就树化”？
  17. TREEIFY_THRESHOLD 与 MIN_TREEIFY_CAPACITY 分别解决什么问题？
  18. 为什么哈希分布质量会影响 HashSet 性能？

7.2 代码阅读

不运行：

Set<String> set = new HashSet<>();

boolean a = set.add("Java");
boolean b = set.add("MySQL");
boolean c = set.add("Java");

System.out.println(a);
System.out.println(b);
System.out.println(c);
System.out.println(set.size());

回答：

  1. 三个 boolean 分别表示什么？
  2. 最终 size 是多少？
  3. 第三个 "Java" 为什么没有形成新的元素？
  4. 能否根据添加顺序准确预测最终遍历顺序？
  5. 如果将 HashSet 换成 ArrayList，结果有什么不同？

7.3 手写代码

任务一：用户名去重

使用：

HashSet<String>

实现：

  • 输入用户名；
  • 添加用户；
  • 重复用户名拒绝注册；
  • 输入 exit 结束；
  • 最后显示唯一用户名数量。

任务二：随机号码

随机生成：

1 ~ 33

中的 6 个不重复号码。

要求：

  • 使用 HashSet；
  • 不手动写嵌套循环检查重复；
  • 最终保证恰好有 6 个不同数字。

任务三：技术栈去重

给定一组：

Java
Spring
MySQL
Java
Redis
Spring
Docker

要求：

  1. 使用 HashSet 去重；
  2. 输出元素数量；
  3. 查询是否存在 Redis；
  4. 删除 Docker；
  5. 遍历全部元素。

7.4 Debug

分析下面代码：

Set<String> set = new HashSet<>();

set.add("Java");
set.add("MySQL");
set.add("Redis");

System.out.println(set.get(0));

要求：

  1. 指出错误。
  2. 为什么 HashSet 不提供这种索引访问模型？
  3. 如果业务要求“第一个元素”，HashSet 是否是合适的数据结构？
  4. 应该根据什么重新进行数据结构选型？

7.5 综合训练

设计一个网站访问去重统计程序。

每次用户访问时得到：

userId

要求统计：

  • 总共出现过多少不同用户；
  • 某个用户是否访问过；
  • 新用户第一次访问时输出欢迎信息；
  • 老用户再次访问时输出“欢迎回来”。

要求：

  1. 先选择合适的数据结构；
  2. 写出选择理由；
  3. 完成程序；
  4. 说明 add() 返回值在该业务中的价值；
  5. 分析如果使用 ArrayList 会出现什么额外成本。

7.6 本章验收

关闭资料和 AI 自动补全：

  • [ ] 能画出 HashSet → HashMap → 哈希表之间的关系。
  • [ ] 能解释 hashCode，而不会说成“随机数”。
  • [ ] 能解释哈希碰撞。
  • [ ] 能解释桶。
  • [ ] 能描述 HashSet 添加元素的主流程。
  • [ ] 能解释为什么 hashCode 相同还不能直接认定重复。
  • [ ] 能解释默认容量、负载因子和扩容的关系。
  • [ ] 能解释 JDK 8+ 为什么引入红黑树。
  • [ ] 能说出树化不仅取决于桶中结点数量，还取决于 table 容量。
  • [ ] 能独立使用 HashSet 完成至少一个真实去重场景。