---
url: https://www.chenlj.top/md/java-base/collections/HashSet.md
---
# 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 语义。

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

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

## 核心成员变量

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

## 源码分析

### 构造

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

### 增删查（全部委托给 map）

```java
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

```java
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
    }
}
```