HashSet适用于键非连续小整数的访问状态记录，核心是正确重写hashCode()和equals()，配合BFS/DFS用add()返回值高效判重，初始化宜预设容量。
HashSet 在算法题中记录访问状态，核心在于利用其 O(1) 平均时间复杂度的查找与插入能力，以及“自动去重”的语义特性。它比布尔数组更灵活（支持任意对象作状态键），比 List 更高效（避免线性扫描）。关键不是“能不能用”，而是“怎么用才不踩坑、不拖慢性能”。
适用场景：什么情况下优先选 HashSet
当访问状态的“键”不是连续小整数时，HashSet 是首选：
- 二维坐标点（如
new Point(x, y)或字符串"x,y"） - 字符串路径（如迷宫中的状态
"row,col,steps"） - 自定义对象状态（如 BFS 中的棋盘布局、括号序列等）
- 数值范围极大或稀疏（比如
long值、大质数索引），无法开布尔数组
正确构造 key：避免失效的核心
HashSet 判断“已访问”依赖 hashCode() 和 equals()。若 key 对象未正确重写这两个方法，会导致逻辑错误——看似相同的状态被当成不同元素反复处理。
- 用
int[]当 key？❌ 不行。数组默认hashCode()是内存地址，equals()是引用比较 - 改用
List或Arrays.asList(x, y)？✅ 可行，List 已重写相关方法 - 更推荐：用字符串拼接
x + "," + y或记录为record Point(int x, int y) { }（Java 14+，自动实现equals/hashCode）
高频操作模式：结合算法结构使用
在 BFS/DFS/回溯类题目中，HashSet 通常配合队列或递归栈使用：
- BFS 入队前先
if (!visited.add(nextState)) continue;—— 一行代码完成“检查+标记+跳过” - DFS 回溯中，在进入递归前
visited.add(state)，退出后visited.remove(state)（注意：仅当需要撤销访问状态时才 remove） - 避免在循环内反复调用
contains()再add()，直接用add()的返回值判断：if (visited.add(state)) { /* 新状态，继续处理 */ }
性能与边界提醒
虽然平均是 O(1)，但最坏情况（大量哈希冲突）会退化到 O(n)。实际刷题中极少触发，但仍需注意：
- 初始化时可预估规模，设置初始容量避免频繁扩容：
new HashSet(n * 2) - 不要在 HashSet 中存大量短生命周期对象（如每次循环 new 一个 String），考虑复用或用更轻量 key
- 多线程环境不适用（算法题一般单线程），无需考虑同步
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
