HashSet 源码解析

简介

HashSet 是 Set 接口的哈希实现，特点是元素不可重复、无序、允许一个 null。它的实现非常「轻」——底层直接包装了一个 HashMap，把集合元素作为 HashMap 的 key，value 统一指向一个占位对象。

• 不是线程安全的；并发可用 Collections.synchronizedSet 或 CopyOnWriteArraySet。
• 去重依赖元素的 hashCode() 与 equals()。
• 查找 / 插入 / 删除的复杂度与 HashMap 一致，平均 O(1)。

因为底层是 HashMap，HashSet 的性能主要受初始容量与负载因子影响，原理与 HashMap 完全相同。

底层数据结构分析

HashSet 自身不存储数据，所有元素放进一个私有的 HashMap 中；value 全部用同一个静态常量对象 PRESENT 占位，仅利用 key 的不可重复性来实现 Set 语义。

// 所有元素都作为 key 存进这个 map
private transient HashMap<E,Object> map;

// 统一的占位 value：所有 key 映射到同一个对象即可，不为 null 即可
private static final Object PRESENT = new Object();

核心成员变量

private transient HashMap<E,Object> map;          // 承载元素的 HashMap
private static final Object PRESENT = new Object(); // 占位 value

源码分析

构造

public HashSet() {
    map = new HashMap<>(); // 默认 HashMap
}
public HashSet(int initialCapacity, float loadFactor) {
    map = new HashMap<>(initialCapacity, loadFactor);
}

增删查（全部委托给 map）

public boolean add(E e) {
    // 放入 map；若 key 原本不存在（返回 null）才算"新增成功"
    return map.put(e, PRESENT) == null;
}

public boolean remove(Object o) {
    return map.remove(o) == PRESENT; // 移除成功返回占位对象
}

public boolean contains(Object o) {
    return map.containsKey(o);       // 直接查 map 的 key
}

可以看到：add 的返回值、remove 的语义完全建立在「HashMap 的 key 不可重复」之上。

与 TreeSet / LinkedHashSet 的对比

维度	HashSet	LinkedHashSet	TreeSet
底层	HashMap	LinkedHashMap	TreeMap
顺序	无序	插入顺序	key 有序
允许 null	允许	允许	否（自然排序下）
复杂度	平均 O(1)	平均 O(1)	O(log n)

经典 Demo

import java.util.HashSet;

public class HashSetDemo {
    public static void main(String[] args) {
        HashSet<String> set = new HashSet<>();
        set.add("a"); set.add("b"); set.add("a"); // 重复元素被忽略
        System.out.println(set);    // [a, b]（顺序不确定）
        System.out.println(set.contains("a")); // true
    }
}