HashSet 底层实现：一切皆为 Map 的 Value
HashSet 是个「空壳」
说出来你可能不信：HashSet 内部根本没有任何数据结构。
它只是把操作转发给了 HashMap。这不是比喻，是字面意义上的转发：
public class HashSet<E> extends AbstractSet<E> implements Set<E> {
// HashSet 的全部家当
private transient HashMap<E, Object> map;
// 所有 value 都用这个固定对象充当
private static final Object PRESENT = new Object();
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
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);
}
}这就是 HashSet 的全部秘密。理解了这一层，HashSet 的所有行为都变得透明。
为什么 HashMap 可以当 HashSet 的底座
核心逻辑在 add 方法：
public boolean add(E e) {
// HashMap.put 的返回值：
// - key 已存在 → 返回旧 value
// - key 不存在 → 返回 null
return map.put(e, PRESENT) == null;
}由于 HashMap 的 key 天然唯一，HashSet 的去重就自动实现了。HashMap 不接受重复 key = HashSet 不接受重复元素。
数据结构图解
┌──────────────────────────────────────────────────────────────────┐
│ HashSet vs HashMap │
├──────────────────────────────────────────────────────────────────┤
│ │
│ HashSet HashMap │
│ ┌──────────────────────┐ ┌──────────────────┐ │
│ │ map: HashMap │───────────────▶ │ table: Node[] │ │
│ │ │ │ │ │
│ │ add("A") ──────────→│ put("A", PRESENT)│ │ │
│ │ add("B") ──────────→│ put("B", PRESENT)│ │ │
│ └──────────────────────┘ └──────────────────┘ │
│ │
│ HashSet 的元素 = HashMap 的 key │
│ HashSet 的 PRESENT = HashMap 的固定 value（无意义，只占位） │
│ │
└──────────────────────────────────────────────────────────────────┘PRESENT 对象的作用：HashMap 需要 key-value 对，HashSet 只需要 key。PRESENT 就是那个「凑数的 value」，告诉 HashMap「这个位置我占了，但值不重要」。
扩容机制
HashSet 本身没有扩容逻辑，全部委托给 HashMap：
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}所以 HashSet 的扩容参数和 HashMap 完全一致：
| 参数 | 默认值 | 说明 |
|---|---|---|
| initialCapacity | 16 | 初始桶数量 |
| loadFactor | 0.75 | 负载因子 |
// 预估 1000 个元素，预估初始容量
HashSet<String> set = new HashSet<>(1334); // 1000/0.75 + 1迭代器：其实是 Map 的 KeySet 迭代器
public Iterator<E> iterator() {
return map.keySet().iterator();
}HashSet 的迭代器就是 HashMap 的 keySet 迭代器，迭代顺序由 HashMap 的桶分布决定——无序。
如果 HashSet 里的元素是 Integer 或 String，遍历顺序往往看起来是升序，但这只是 hashCode 分布的巧合，不是保证。
LinkedHashSet：插入顺序的秘密
LinkedHashSet 不是 HashSet 的简单包装，它使用了特殊的 HashMap：
public class LinkedHashSet<E> extends HashSet<E> {
public LinkedHashSet() {
// 关键：accessOrder = false → 维护插入顺序
// 如果 accessOrder = true → 维护访问顺序（LRU 缓存）
super(16, .75f, true);
}
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);
}
}第三个参数 true 是什么意思？去看 LinkedHashMap 的构造函数：
// HashSet 底层其实调用的是这个
HashMap(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}LinkedHashMap 在每个桶节点之间维护了一条双向链表：
插入顺序链表（LinkedHashMap 维护）：
head → "C" → "A" → "B" → tail
HashMap 桶结构：
bucket[2] → "C"
bucket[3] → "A" → "B"迭代时按链表顺序遍历，而不是按桶顺序。所以 LinkedHashSet = HashMap 的去重 + 双向链表的有序。
线程安全性
HashSet 非线程安全，原因和 HashMap 一样：
// ❌ 并发添加，数据可能丢失
HashSet<Integer> set = new HashSet<>();
// 线程1: set.add(1)
// 线程2: set.add(1)
// 结果可能只有 1 个元素
// ✅ 方案 1：synchronized 包装
Set<Integer> safe = Collections.synchronizedSet(new HashSet<>());
// ✅ 方案 2：CopyOnWriteArraySet（读多写少场景）
Set<Integer> cow = new CopyOnWriteArraySet<>();性能特点
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| add | O(1) 均摊 | 哈希 + 可能的链表遍历 |
| remove | O(1) 均摊 | 同上 |
| contains | O(1) 均摊 | 同上 |
| 遍历 | O(n + m) | n=元素数，m=桶数 |
HashSet 的性能完全取决于哈希函数的质量。哈希分布均匀 → O(1)；哈希严重冲突 → 退化到 O(n)。
总结
| 要点 | 说明 |
|---|---|
| 本质 | HashMap 的 key 集合 |
| PRESENT | 无意义的占位 value |
| 去重 | 依赖 HashMap key 唯一性 |
| 迭代器 | HashMap.keySet().iterator()，无序 |
| LinkedHashSet | LinkedHashMap 作底座，维护双向链表 |
| 线程安全 | 非安全，需要包装 |
一句话理解：HashSet 是 HashMap 的「门面模式」——只暴露 key，省掉 value。