HashSet 是 Java 集合框架中的一个重要实现类，用于存储不重复的元素。HashSet 是基于 HashMap 实现的，其内部通过 HashMap 来存储元素，借助 HashMap 的键的特性来确保元素的唯一性。

1. HashSet 的基本特性

• 基于 HashMap 实现：HashSet 的底层是基于 HashMap，每一个存入 HashSet 的元素实际上作为 HashMap 的键，而值则是一个固定的常量 PRESENT，其类型为 Object。
• 元素唯一性：通过 HashMap 键的唯一性特性来确保 HashSet 中元素不重复。
• 非线程安全：HashSet 是非线程安全的，如果需要在多线程环境下使用，可以使用 Collections.synchronizedSet() 方法来获取线程安全的版本。
• 允许 null 值：HashSet 允许存储一个 null 值。

2. 构造函数

HashSet 提供了多个构造函数，用于满足不同的初始化需求：

• 默认构造函数：

  public HashSet() {
      map = new HashMap<>();
  }
  

  • 创建一个默认初始容量为 16，负载因子为 0.75 的 HashMap，用于存储元素。

• 指定初始容量的构造函数：

  public HashSet(int initialCapacity) {
      map = new HashMap<>(initialCapacity);
  }
  

  • 可以指定初始容量，创建相应容量的 HashMap，以减少后续扩容的开销。

• 指定初始容量和负载因子的构造函数：

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

  • 可以同时指定初始容量和负载因子，创建 HashMap。

3. 数据结构

HashSet 通过 HashMap 来实现元素的存储和唯一性保证，以下是关键数据结构的实现：

• 存储元素：

  private transient HashMap<E,Object> map;
  private static final Object PRESENT = new Object();
  

  • map：一个 HashMap 实例，用于存储 HashSet 中的元素。
  • PRESENT：一个占位符对象，用作 HashMap 的值，所有元素的值都是这个常量。

4. 添加元素 (add() 方法)

add() 方法用于在 HashSet 中添加元素，其核心逻辑如下：

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

• map.put(e, PRESENT)：将元素作为键，PRESENT 作为值插入到 HashMap 中。
  • 如果插入成功（即元素不重复），则返回 true；否则返回 false。
  • 由于 HashMap 的键是唯一的，因此能够保证 HashSet 中的元素不重复。

5. 删除元素 (remove() 方法)

remove() 方法用于从 HashSet 中删除指定元素，核心逻辑如下：

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

• map.remove(o)：通过 HashMap 的 remove() 方法移除指定的键（即元素）。
  • 如果移除成功，返回 true；否则返回 false。

6. 判断元素是否存在 (contains() 方法)

contains() 方法用于判断 HashSet 中是否包含指定的元素：

public boolean contains(Object o) {
    return map.containsKey(o);
}

• map.containsKey(o)：直接调用 HashMap 的 containsKey() 方法来判断元素是否存在。
  • 由于 HashMap 的键是唯一的，因此可以高效地判断元素是否在集合中。

7. HashSet 的迭代

HashSet 的迭代通过调用 HashMap 的 keySet() 方法实现，keySet() 方法返回 HashMap 中所有键的集合，从而可以遍历 HashSet 中的元素。

public Iterator<E> iterator() {
    return map.keySet().iterator();
}

• map.keySet().iterator()：返回一个用于遍历 HashSet 元素的迭代器。

8. HashSet 的扩容机制

HashSet 的扩容依赖于 HashMap 的扩容机制。当元素数量超过阈值时，HashMap 会进行扩容，扩容后的容量是原容量的两倍，并重新分布原有的键值对。

• 扩容条件：当 HashSet 中的元素数量超过 HashMap 的阈值（容量 * 负载因子）时，触发扩容。
• 扩容过程：HashMap 会创建一个新的、更大的数组，然后将原有的元素重新哈希分布到新的数组中，以减少哈希冲突。

9. 总结

HashSet 基于 HashMap 实现，利用 HashMap 的键来确保元素的唯一性，从而实现了不重复元素的集合。HashSet 的所有操作（如添加、删除、判断存在等）都依赖于 HashMap 的方法，这使得 HashSet 具有和 HashMap 类似的时间复杂度，即常数时间的增删查操作。通过源码分析，可以看到 HashSet 的简单而高效的实现方式，同时也继承了 HashMap 的扩容机制，以保证良好的性能表现。