哈希集合（HashSet）
基于哈希表实现的集合数据结构，提供 O(1) 平均时间复杂度的插入、删除和查找操作。
定义
哈希集合（HashSet） 是一种基于哈希表实现的集合数据结构，它存储不重复的元素。与哈希表（HashMap）存储键值对不同，哈希集合只存储元素本身。
核心特性
| 特性 | 说明 |
|---|---|
| 元素唯一性 | 集合中不包含重复元素 |
| 无序性 | 元素存储顺序不保证（除非使用 LinkedHashSet） |
| 允许 null | 大多数实现允许存储一个 null 元素 |
| 基于哈希表 | 底层使用哈希表实现，依赖 hashCode() 和 equals() |
基本原理
哈希集合的工作原理与哈希表类似：
- 调用元素的
hashCode()方法计算哈希值 - 根据哈希值确定元素在底层数组中的存储位置
- 如果该位置已有元素（哈希冲突），使用链表或红黑树解决冲突
- 插入前检查元素是否已存在（使用
equals()方法比较）
插入元素 e:
1. hash = e.hashCode()
2. index = hash % table.size
3. 如果 table[index] 为空 → 直接插入
4. 如果 table[index] 不为空 → 遍历链表/树，用 equals() 检查是否已存在
- 存在 → 不插入（保证唯一性）
- 不存在 → 添加到链表/树
常见操作及时间复杂度
| 操作 | 时间复杂度（平均） | 时间复杂度（最坏） | 说明 |
|---|---|---|---|
| 添加 add(e) | O(1) | O(n) | 哈希冲突严重时退化 |
| 删除 remove(e) | O(1) | O(n) | 同上 |
| 查找 contains(e) | O(1) | O(n) | 同上 |
| 大小 size() | O(1) | O(1) | 维护 size 计数器 |
与类似数据结构对比
| 维度 | 哈希集合 (HashSet) | 哈希表 (HashMap) | 树集合 (TreeSet) |
|---|---|---|---|
| 底层结构 | 哈希表 | 哈希表 | 红黑树 |
| 元素顺序 | 无序 | 无序（键值对） | 有序（自然顺序或比较器） |
| 时间复杂度 | O(1) | O(1) | O(log n) |
| 是否允许 null | 是（多数实现） | 是（多数实现） | 否 |
| 用途 | 去重、集合运算 | 键值映射 | 有序集合、范围查询 |
在 BFS 算法中的应用
在 BFS 算法中，哈希集合常用于实现 visited 集合，记录已访问过的节点，防止走回头路（成环）。
为什么用 HashSet 而不是 boolean 数组？
- 当节点不是简单的整数索引时（如字符串、对象），无法用数组下标表示
- 哈希集合可以存储任意类型的元素
- 例如：密码锁问题中，节点是 4 位字符串，用
HashSet<String>记录访问
代码示例（BFS 中的 visited 集合）：
Set<String> visited = new HashSet<>();
Queue<String> q = new LinkedList<>();
q.offer("0000");
visited.add("0000");
while (!q.isEmpty()) {
String cur = q.poll();
for (String neighbor : getNeighbors(cur)) {
if (!visited.contains(neighbor)) {
q.offer(neighbor);
visited.add(neighbor);
}
}
}
注意事项
- 重写 hashCode() 和 equals()：自定义对象作为元素时，必须正确重写这两个方法
- 哈希冲突：糟糕的 hashCode() 实现会导致大量冲突，退化为 O(n)
- 扩容开销：当元素数量超过负载因子容量时，会触发扩容（rehash），开销较大
- 非线程安全：多线程环境下需要使用
Collections.synchronizedSet()或ConcurrentHashMap.newKeySet()
常见实现
| 实现类 | 特点 |
|---|---|
| HashSet (Java) | 标准实现，基于 HashMap，无序 |
| LinkedHashSet (Java) | 维护插入顺序的双向链表，迭代顺序可预测 |
| TreeSet (Java) | 基于 TreeMap（红黑树），元素有序 |
| set (Python) | Python 内置集合类型，基于哈希表 |
应用场景
- 去重：从列表中去除重复元素
- 快速查找：判断元素是否存在于集合中
- 集合运算：求交集、并集、差集
- BFS/图遍历：记录已访问节点，防止走回头路
- 缓存：简单场景下的缓存实现