HashSet

介绍

HashSet 是一个无重复元素的集合，底层基于 HashMap 实现（元素存为 key，value 是一个固定的 dummy 对象）。

一句话直觉：Set = 只关心”在不在”，不关心”是什么”。去重、查存在、做交集 — 全 O(1)。

核心能力：O(1) 时间判断元素是否存在。常用于去重和存在性判断。

Set vs List — 什么时候用哪个？

	HashSet	ArrayList
查找	O(1)	O(n)
插入	O(1)	O(1) 末尾 / O(n) 中间
重复元素	自动去重	允许重复
顺序	无序	保持插入顺序
内存	较大（哈希表开销）	较小

判断原则：需要频繁查找、去重 → Set。需要按索引访问、保持顺序 → List。如果两者都需要 → LinkedHashSet。

模式识别

当你看到这些信号，优先想 Set：

• “是否有重复元素？“（O(1) 查重）
• “两个集合的交集/并集/差集”
• “已访问过吗？“（DFS/BFS 的 visited 标记）
• “需要快速判断某元素是否在禁止列表中”

Java 常用方法

boolean add(E e)               // add element, returns false if already present
boolean remove(Object o)       // remove element
boolean contains(Object o)     // O(1) membership check
int size()
boolean isEmpty()
void clear()

// Bulk operations
boolean addAll(Collection c)
boolean retainAll(Collection c) // intersection
boolean removeAll(Collection c) // difference

常见模式

去重

// Remove duplicates from array while preserving order
Set<Integer> seen = new HashSet<>();
List<Integer> result = new ArrayList<>();
for (int num : nums) {
    if (seen.add(num)) {
        result.add(num);
    }
}

存在性检查

// Check if a value exists in collection
if (set.contains(target)) {
    // found
}

两个数组的交集

public int[] intersection(int[] nums1, int[] nums2) {
    Set<Integer> set1 = new HashSet<>();
    for (int n : nums1) set1.add(n);

    Set<Integer> result = new HashSet<>();
    for (int n : nums2) {
        if (set1.contains(n)) result.add(n);
    }
    return result.stream().mapToInt(Integer::intValue).toArray();
}

关键技巧

• O(1) 查重 — 判断”是否见过”就是 Set 的第一用途，O(n²) → O(n) 的关键
• add() 返回值是去重利器 — 返回 false 说明元素已存在，一行代码完成”查 + 插”
• Set 操作就是集合论 — 交集 retainAll，并集 addAll，差集 removeAll，脑中画 Venn 图
• LinkedHashSet = Set + 插入顺序 — 需要去重但还要保持遍历顺序时使用
• HashSet vs HashMap — 只关心键就用 Set，语义更清晰，代码更短

参考资料

• HashSet — Java Docs