Java集合-HashSet

前言

HashSet 是 Java 集合框架中的一种无序、不重复的集合实现，属于 java.util 包。它实现了 Set 接口，底层基于 HashMap 实现。HashSet 的主要特点：

无序性：元素存储顺序与插入顺序无关。
唯一性：不允许重复元素（通过 equals() 和 hashCode() 判断）。
高效性：增删查操作的平均时间复杂度为 $O(1)$。
允许null：可以包含一个null元素。

源码分析

数据结构

HashSet 的实现依赖于 HashMap，具体来说，HashSet 的元素作为 HashMap 的键存储，而值则是一个固定的占位对象。

构造方法

HashSet 的五个构造方法如下，它们都围绕底层 HashMap 的初始化展开：

HashSet() - 默认构造方法
HashSet(int initialCapacity) - 指定初始容量
HashSet(int initialCapacity, float loadFactor) - 指定初始容量和加载因子
HashSet(Collection<? extends E> c) - 从另一个集合初始化
HashSet(int initialCapacity, float loadFactor, boolean dummy) - 内部使用的特殊构造方法（不公开）

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, Serializable {
    private transient HashMap<E, Object> map;
    // 所有键对应的值都是同一个PRESENT对象
    private static final Object PRESENT = new Object();

    // 默认构造方法
    public HashSet() {
        map = new HashMap<>();
    }

    // 指定初始容量的构造方法
    public HashSet(int initialCapacity) {
        map = new HashMap<>(initialCapacity);
    }

    // 指定初始容量和加载因子的构造方法
    public HashSet(int initialCapacity, float loadFactor) {
        map = new HashMap<>(initialCapacity, loadFactor);
    }

    // 从另一个集合初始化的构造方法
    public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size() / .75f) + 1, 16));
        addAll(c);
    }

    // 内部使用的特殊构造方法
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
}

除了第四个构造方法外，其他构造方法传入的 initialCapacity 都会被 HashMap 调整为 2 的幂。

第四个构造方法细节：

容量计算：Math.max((int) (c.size() / .75f) + 1, 16)。
- c.size() / 0.75f：根据集合大小和默认加载因子0.75估算所需容量。
- +1：确保容量足够。
- Math.max(..., 16)：保证容量至少为16。
addAll(c)：调用 AbstractCollection 的 addAll，逐个添加元素到 HashMap 中。

第五个构造方法是为 LinkedHashSet 设计的，体现了 Java 集合框架的复用性。

核心方法分析

在 HashSet 中，最为核心的是添加、删除这两个方法。

添加元素 - `add(E e)`

1
2
3

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

add 方法通过调用 HashMap.put 将元素作为键插入。
HashMap.put 返回的是插入前的旧值。如果返回 null，说明之前没有这个键，插入成功，返回 true；否则返回旧值（PRESENT），表示元素已存在，返回 false。

去重逻辑：依赖 HashMap 的键唯一性，内部会调用元素的 hashCode() 和 equals() 方法判断是否重复。

删除元素 - `remove(Object o)`

1
2
3

public boolean remove(Object o) {
    return map.remove(o) == PRESENT;
}

调用 HashMap.remove，如果成功移除（即返回 PRESENT），则返回 true。
删除操作依赖 HashMap 的哈希查找，时间复杂度 $O(1)$。

后记

HashSet 是非线程安全的，多线程环境下需要外部同步（如 Collections.synchronizedSet 或 ConcurrentHashMap）。

HashSet 本质上是 HashMap 的封装，元素存储在 HashMap 的键中，值统一为PRESENT。