HashSet 原理深度剖析：基于 HashMap 的去重神器，从源码到实战

• 教程
• 技术博客
• 文档

本文是 YCBlogs 仓库 Java 数据结构系列的核心篇章，聚焦 java/04.数据结构/22.HashSet原理深度分析.md 展开。HashSet 是 Java 集合框架中最常用的去重容器之一，其全部功能都建立在 HashMap 之上——理解 HashSet 就等于理解 HashMap 的 Key 语义。读完本文，你将掌握 HashSet 的特点、底层存储结构、add/remove/contains 的完整调用链、去重的真正判定规则，以及如何通过正确重写 hashCode() 与 equals() 让自定义对象也能可靠去重，最后还能独立完成"生成不重复随机数"这类经典实战案例。

01. HashSet 特点：一个"换皮"的 HashMap

1.1 三大核心特征

HashSet 实现了Set接口，与List系列最大的不同体现在三个方面：

• 不允许插入重复元素：这是 Set 存在的意义，去重能力由底层的 HashMap 保证；
• 允许包含 null 元素：且 null 只能存一个（因为重复判定会把第二个 null 挡在门外）；
• 不保证元素的迭代顺序：特别是不保证该顺序恒久不变——即使集合内容没变，随着 HashMap 扩容、哈希冲突变化，遍历顺序也可能改变。

从源码结构看，HashSet 的实现极其精简：去掉注释后代码不到两百行，因为它几乎没有自己的数据结构，底层直接复用了 HashMap。这一点从它的成员变量一眼就能看出：

// HashSet 底层用 HashMap 来存放数据 // Key 值由外部传入，Value 则由 HashSet 内部来维护 private transient HashMap<E,Object> map; // HashMap 中所有键值对都共享同一个值 // 即所有存入 HashMap 的键值对都是使用这个对象作为值 private static final Object PRESENT = new Object();

这是一个非常精妙的设计：HashSet 把用户传入的元素当作HashMap 的 Key，而 Value 统一使用一个静态占位对象PRESENT。这样一来，"元素是否重复"的判断就完全委托给了 HashMap 对 Key 的去重逻辑，HashSet 自身几乎零成本地获得了完整的哈希表能力。

1.2 快速验证：无序 + 去重 + 单 null

原文档给出的验证案例可以直接运行：

public class DataType { public static void main(String[] args){ Set<String> set = new HashSet<>(); set.add("1"); set.add("2"); set.add(null); set.add("1"); // 重复元素，add 返回 false，不会真正插入 for(String s : set){ System.out.println(s); } } }

运行结果：

null 1 2

注意三点："1"只出现一次（去重生效）；null被允许插入且只有一个；输出顺序是null、1、2而非插入顺序——因为元素在哈希表中的存储位置由hashCode()计算得出，与插入先后无关。同时这也验证了HashSet 是根据 hashCode 决定存储位置的，因此存入的元素类型必须正确实现 hashCode() 方法。

02. HashSet 源码全解析：不到两百行的"包装类"

下面完整给出 HashSet 的核心源码，并逐段说明其设计意图。这段代码也是原文档（java/04.数据结构/22.HashSet原理深度分析.md）的骨架，我们将在此基础上深入每一行背后的原理。

2.1 类声明与字段

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable{ //序列化ID static final long serialVersionUID = -5024744406713321676L; //HashSet 底层用 HashMap 来存放数据 //Key值由外部传入，Value则由 HashSet 内部来维护 private transient HashMap<E,Object> map; //HashMap 中所有键值对都共享同一个值 //即所有存入 HashMap 的键值对都是使用这个对象作为值 private static final Object PRESENT = new Object(); }

• extends AbstractSet<E>：复用 AbstractSet 提供的equals()、hashCode()、removeAll()等基于迭代器的通用实现；
• implements Cloneable, java.io.Serializable：支持克隆与序列化；
• PRESENT是静态常量，被所有键值对共享——HashMap 的 Value 字段实际不承载任何业务数据，纯粹是占位。

2.2 五个构造函数

//无参构造函数，HashMap 使用默认的初始化大小(16)和装载因子(0.75) public HashSet() { map = new HashMap<>(); } //使用默认的装载因子，并以此来计算 HashMap 的初始化大小 //+1 是为了弥补精度损失 public HashSet(Collection<? extends E> c) { map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16)); addAll(c); } //为 HashMap 自定义初始化大小和装载因子 public HashSet(int initialCapacity, float loadFactor) { map = new HashMap<>(initialCapacity, loadFactor); } //为 HashMap 自定义初始化大小 public HashSet(int initialCapacity) { map = new HashMap<>(initialCapacity); } //此构造函数为包访问权限，只用于对 LinkedHashSet 的支持 HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); }

构造细节值得展开：

• 传入集合的构造中，c.size()/.75f + 1是预估容量公式：已知装载因子为 0.75（即容量用到 75% 就会扩容），要装下size()个元素，预估容量约为size() / 0.75，+1用于弥补浮点除法带来的精度损失，Math.max(..., 16)保证不小于 HashMap 默认初始容量 16。如果不这样预估，addAll 过程中就可能触发多次扩容，白白浪费性能。
• 最后一个带dummy参数的构造是包访问权限（没有 public 修饰），它不创建 HashMap 而是创建 LinkedHashMap。这个"隐藏"构造的唯一调用方就是 LinkedHashSet——这正是 java/04.数据结构/23.LinkedHashSet.md 中super(16, .75f, true)所指向的构造。dummy参数本身没有任何业务含义，纯粹是为了与HashSet(int, float)构成重载区分。

2.3 迭代、size、isEmpty、contains

//将对 HashSet 的迭代转换为对 HashMap 的 Key 值的迭代 public Iterator<E> iterator() { return map.keySet().iterator(); } //获取集合中的元素数量 public int size() { return map.size(); } //判断集合是否为空 public boolean isEmpty() { return map.isEmpty(); } //判断集合是否包含指定元素 public boolean contains(Object o) { return map.containsKey(o); }

所有方法都是一行委托：iterator()返回的是map.keySet()的迭代器，因为 HashSet 的元素就是 HashMap 的 Key 集合；contains(o)等价于判断 HashMap 中是否存在以o为 Key 的键值对，走的是containsKey的哈希查找路径，时间复杂度 O(1)（无冲突时）。

2.4 add 与 remove：去重的关键

//如果 HashSet 中不包含元素 e，则添加该元素，并返回 true //如果 HashSet 中包含元素 e，则不会影响 HashSet ，并返回 false public boolean add(E e) { return map.put(e, PRESENT)==null; } //移除集合中的元素 o //如果集合不包含元素 o，则返回 false public boolean remove(Object o) { return map.remove(o)==PRESENT; } //清空集合中的元素 public void clear() { map.clear(); }

这两个方法是对"委托设计"最极致的体现：

• add(e)返回map.put(e, PRESENT) == null。根据 HashMap 的语义，put 返回的是旧 Value：如果之前不存在该 Key，put 返回 null（即==null为 true，插入成功）；如果之前已存在该 Key，put 会返回旧 Value——在这里永远是PRESENT（即==null为 false，插入失败）。所以 add 的返回值恰好表达了"是否发生了真正的插入"。
• remove(o)返回map.remove(o) == PRESENT。如果 Key 存在，remove 返回被移除键值对的旧 Value（即PRESENT），返回 true；如果 Key 不存在，返回 null，返回 false。

这两个方法把"元素是否已存在"的判断完全下沉给了 HashMap 的 Key 查找逻辑，HashSet 只负责比较返回值。

2.5 clone 与序列化

@SuppressWarnings("unchecked") public Object clone() { try { HashSet<E> newSet = (HashSet<E>) super.clone(); newSet.map = (HashMap<E, Object>) map.clone(); return newSet; } catch (CloneNotSupportedException e) { throw new InternalError(e); } } private void writeObject(java.io.ObjectOutputStream s) throws java.io.IOException { // Write out any hidden serialization magic s.defaultWriteObject(); // Write out HashMap capacity and load factor s.writeInt(map.capacity()); s.writeFloat(map.loadFactor()); // Write out size s.writeInt(map.size()); // Write out all elements in the proper order. for (E e : map.keySet()) s.writeObject(e); } private void readObject(java.io.ObjectInputStream s) throws java.io.IOException, ClassNotFoundException { // Read in any hidden serialization magic s.defaultReadObject(); // Read capacity and verify non-negative. int capacity = s.readInt(); if (capacity < 0) { throw new InvalidObjectException("Illegal capacity: " + capacity); } // Read load factor and verify positive and non NaN. float loadFactor = s.readFloat(); if (loadFactor <= 0 || Float.isNaN(loadFactor)) { throw new InvalidObjectException("Illegal load factor: " + loadFactor); } // Read size and verify non-negative. int size = s.readInt(); if (size < 0) { throw new InvalidObjectException("Illegal size: " + size); } // Set the capacity according to the size and load factor ensuring that // the HashMap is at least 25% full but clamping to maximum capacity. capacity = (int) Math.min(size * Math.min(1 / loadFactor, 4.0f), HashMap.MAXIMUM_CAPACITY); // Create backing HashMap map = (((HashSet<?>)this) instanceof LinkedHashSet ? new LinkedHashMap<E,Object>(capacity, loadFactor) : new HashMap<E,Object>(capacity, loadFactor)); // Read in all elements in the proper order. for (int i=0; i<size; i++) { @SuppressWarnings("unchecked") E e = (E) s.readObject(); map.put(e, PRESENT); } }

• clone()：先super.clone()浅拷贝出新的 HashSet 实例，再把内部的 map 也 clone 一份，保证克隆对象与原件互不影响；
• 序列化采用自定义writeObject/readObject：不直接序列化 HashMap（其内部 table 结构依赖 hashCode 定位，不同 JVM 上 hashCode 实现可能不同，直接序列化结构不可靠），而是只序列化容量、装载因子和元素本身，反序列化时再重新 put 进新建的 HashMap——这也解释了为什么 map 字段被声明为transient；
• readObject中通过instanceof LinkedHashSet判断反序列化目标类型，以决定重建 HashMap 还是 LinkedHashMap，从而保留 LinkedHashSet 的顺序语义。

2.6 spliterator

//为了并行遍历数据源中的元素而设计的迭代器 public Spliterator<E> spliterator() { return new HashMap.KeySpliterator<E,Object>(map, 0, -1, 0, 0); }

Spliterator是 Stream API 并行流的底层支撑，直接复用HashMap.KeySpliterator，再次印证 HashSet 的一切都来自 HashMap。

03. HashSet 如何去重：add() 背后的完整调用链

这是 HashSet 原理中最核心的问题。答案可以浓缩为一句话：向 HashSet 添加元素，本质是向底层 HashMap 添加一个"元素为 Key、PRESENT 为 Value"的键值对。

展开来看，去重判定发生在 HashMap 的put→putVal链路中。参考 java/04.数据结构/07.HashMap源码深度分析.md 中给出的putVal关键逻辑：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // tab 为空则创建（首次 put 时初始化） if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 计算 index（桶位置），该位置为空则直接放入 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; // 关键判定①：hash 相等且 (引用相等 或 equals 相等) → 视为同一个 Key if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 该链已树化为红黑树，走红黑树查找 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 该链为普通链表，逐个节点用 equals 比较 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); // 链表长度达到阈值(8)则树化 if (binCount >= TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash); break; } if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // 找到了已存在的 Key：用新 Value 覆盖旧 Value，但 Key 不变 if (e != null) { V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; return oldValue; // put 返回旧 Value（即 PRESENT） } } ... return null; // 新插入，返回 null }

对照 HashSet.add() 的返回值map.put(e, PRESENT)==null，去重的完整逻辑就清晰了：

1. 先通过hash(key)对元素 hashCode 做二次扰动（详见下文第 4 节），再用(n - 1) & hash定位桶；
2. 在桶内查找是否存在 Key 与待插入元素"相等"的节点，判定条件是双重的：hashCode()返回值相等，且通过equals()比较返回 true；
3. 若存在相等 Key，则新键值对的 value 会覆盖原有数据，但 key 不会改变——意味着重复元素不会真正进入 HashMap，add 返回 false；
4. 若不存在相等 Key，正常插入新节点，add 返回 true。

因此原文档的总结是准确的：如果 HashMap 中包含 key 值与待插入元素相等的键值对，则待添加键值对的 value 会覆盖原有数据，但 key 不会有所改变，元素不会被存入 HashMap，从而实现了 HashSet 元素不重复的特征。

值得强调：e.value = value覆盖的是 Value，而 HashSet 的 Value 永远是同一个PRESENT，所以覆盖操作实际上什么都不改变，纯粹是一个"占位"动作。

04. 底层 HashMap 的哈希寻址与扩容原理

理解了委托关系后，再深入一步：HashSet 的去重性能和存储布局，完全取决于 HashMap 的实现细节。

4.1 哈希函数：为什么不能直接用 hashCode

从 java/04.数据结构/07.HashMap源码深度分析.md 可以确认，HashMap 对 key 的 hashCode 做了一次扰动：

public V put(K key, V value) { return putVal(hash(key), key, value, false, true); // 对 key 的 hashCode() 做 hash }

扰动的原因在于：hashCode() 返回的是 32 位 int，范围约 40 亿，而 HashMap 的容量通常只有 16 到 2^30，直接取 hashCode 作为数组下标必然越界。实际寻址公式是i = (n - 1) & hash——用容量减一做掩码，等价于取模。此时如果两个元素的 hashCode 差异主要集中在高位，低位完全相同，就会碰撞到同一个桶。扰动函数把高位信息异或到低位，就是为了摊平这类"高位不同、低位相同"的碰撞风险。这也解释了为什么好的 hashCode 实现（如 String、Integer 内置实现）能显著减少冲突、提升 HashSet 的存取效率。

4.2 put 的完整流程

综合 java/04.数据结构/07.HashMap源码深度分析.md 的总结，一次 put（即一次 HashSet.add）的流程是：

1. 对 key 的hashCode()做 hash 扰动，再计算桶索引；
2. 如果没有碰撞，直接放入对应桶；
3. 如果碰撞了，以链表形式挂在桶后面；
4. 如果碰撞导致链表过长（达到TREEIFY_THRESHOLD，值为 8），链表转换为红黑树，把最坏查找时间从 O(n) 降为 O(log n)；
5. 如果节点已经存在（hash 相等且 equals 相等），用新 value 替换旧 value，保证 key 唯一性；
6. 如果桶数组使用量超过loadFactor * currentCapacity，触发 resize 扩容。

4.3 扩容 resize

HashMap 默认初始容量 16、默认装载因子 0.75。当元素个数超过threshold = capacity * loadFactor（默认即 16 × 0.75 = 12）时，resize()会把容量翻倍（newCap = oldCap << 1），并重算每个元素在新数组中的位置。扩容意味着哈希寻址掩码(n - 1)变化，元素的桶位置可能随之改变——这正是"不保证迭代顺序恒久不变"的底层原因之一。扩容过程中旧数组元素需要重新放置，这是 resize 的主要开销来源，所以预估容量（如构造 HashSet 时传入c.size()/.75f + 1）能有效减少扩容次数。

需要补充的另一个事实：HashMap 不是线程安全的，多线程并发 put 可能引发死循环或数据错乱。因此 HashSet 同样不是线程安全的，并发场景下应改用Collections.synchronizedSet()或ConcurrentHashMap.newKeySet()。

05. 实战案例：生成 10 个 1~20 的不重复随机数

这是原文档给出的经典练习，它把 HashSet 的"去重"特性应用到了随机数去重场景，逻辑非常直观：

/** * 产生10个1-20之间的随机数,要求不能重复 * 分析: * 1: 创建一个HashSet集合对象 , 作用: 存储产生的随机数 * 2: 生成随机数 , 把随机数添加到集合中 * 3: 使用循环,当集合的长度大于等于10退出循环 , 小于10就一直循环 */ // 创建一个HashSet集合对象 , 作用: 存储产生的随机数 HashSet<Integer> hs = new HashSet<Integer>() ; while(hs.size() < 10) { // 使用Random类 Random random = new Random() ; int num = random.nextInt(20) + 1 ; // 把num添加到集合中 hs.add(num) ; } // 遍历 for(Integer i : hs) { System.out.println(i); }

运行逻辑拆解：

• 循环条件hs.size() < 10利用了add的去重特性——当nextInt(20) + 1产生的数已经存在时，add 返回 false，集合 size 不变，循环继续生成下一个数；
• 由于取值范围是 1~20（共 20 个数），要取 10 个不重复的数，理论上循环一定会终止；
• 输出顺序无序，这是 HashSet 的固有特性；如果希望输出有序，可以改用 LinkedHashSet（按插入顺序）或 TreeSet（按自然顺序）。

作为延伸，把该案例与 java/04.数据结构/24.TreeSet源码深入分析.md 中的案例对比，可以直观看到三个 Set 家族的差异：HashSet 无序去重、LinkedHashSet 有序（插入序）去重、TreeSet 按比较器排序去重。

06. 让自定义对象正确去重：hashCode 与 equals 的约定

HashSet 的去重判定依赖hashCode()与equals()两个方法，如果自定义对象没有正确重写它们，去重就会失效（对象默认使用 Object 的引用相等语义，两个内容相同的对象会被当作不同元素）。结合 question/java/03.Java数据结构问题.md 中整理的约定，必须遵守以下规则：

• equals 相等，hashCode 一定要相等——这是 HashMap 哈希查找的前提，违反它会导致"明明相等却存进了两个位置"；
• 重写了 hashCode 也要重写 equals，反之亦然；
• hashCode 需要保持一致性——对象状态改变前后（参与哈希计算的字段不变时）返回的哈希值要一致；
• equals 需要满足自反性、对称性、传递性、一致性，且对于任何非 null 的 x，x.equals(null)必须返回 false。

一个规范的 Key 类重写示例（来自仓库问题汇总）：

public class Key { private final String name; private final int width; private final int heifht; @Override public boolean equals(Object o) { if (this == o) { return true; } if (o == null || getClass() != o.getClass()) { return false; } Key key = (Key) o; if (width != key.width) { return false; } if (heifht != key.heifht) { return false; } return name != null ? name.equals(key.name) : key.name == null; } @Override public int hashCode() { int result = name != null ? name.hashCode() : 0; result = 31 * result + width; result = 31 * result + heifht; return result; } }

要点说明：

• hashCode()使用 31 作为乘数（31 是奇素数，且31 * i可被 JVM 优化为移位减法的位运算，碰撞概率较低）；
• equals()对参与相等性判定的每一个字段都要比较（基本类型用==，引用类型用equals并处理 null）；
• 参与 hashCode 计算的字段应与 equals 比较的字段保持一致，否则会破坏"equals 相等则 hashCode 相等"的约定。

实践建议：采用合适的 equals/hashCode 会减少哈希碰撞、提高存取效率；不可变对象（如 String、Integer 包装类）能缓存 hashCode 且状态稳定，是作为 HashSet 元素的理想选择。如果要用可变对象作为元素，务必保证在存入后不再修改其参与哈希计算的字段，否则元素将"丢失"（无法再被 contains/remove 正确找到）。

07. 同门对比：HashSet 与 LinkedHashSet、TreeSet

在 question/java/03.Java数据结构问题.md 中，三者的区别被归纳为：

• HashSet：基于哈希表实现，支持快速查找（无冲突时 O(1)），但不支持有序性操作，失去元素插入顺序信息，Iterator 遍历结果不确定；
• LinkedHashSet：具有 HashSet 的查找效率，且内部使用双向链表维护元素的插入顺序（底层是 LinkedHashMap，见 java/04.数据结构/23.LinkedHashSet.md）；
• TreeSet：基于红黑树实现（底层 TreeMap），支持有序性操作（如按范围查找），但查找效率为 O(log n)，不如 HashSet。

从源码层面看，三者是同一套"委托"设计思想的三个变体：

值得注意的细节：LinkedHashSet 的四个构造函数全部通过super(initialCapacity, loadFactor, true)调用 HashSet 那个包访问权限的"隐藏"构造，从而让底层 map 初始化为 LinkedHashMap；TreeSet 则通过map.put(e, PRESENT)但底层是 TreeMap，元素按红黑树的比较器排序，因此 TreeSet 存储的元素要么实现 Comparable，要么在构造时传入 Comparator，且元素不能为 null。

08. 常见面试问题小结

把本文内容浓缩成面试可直接作答的要点：

Q1：HashSet 有哪些特点？答：实现了 Set 接口，不允许重复元素、允许且只能存储一个 null、不保证迭代顺序且该顺序可能因扩容改变；代码极简（不到两百行），底层完全委托 HashMap 实现。

Q2：HashSet 如何存储 null？答：add(null) 会把 null 作为 Key 放入 HashMap。HashMap 允许 null Key（其哈希值为 0，存入 table[0] 对应的桶）；再次 add(null) 时，(n-1) & 0定位到同一桶，null == null 引用相等即判定重复，add 返回 false，所以 null 只能存一个。

Q3：HashSet 是如何去重的？答：add(e) 等价于map.put(e, PRESENT)。HashMap 在 putVal 中先用 hash(key) 定位桶，再在桶内通过"hashCode 相等 且 (引用相等或 equals 相等)"判定 Key 是否已存在；若存在，仅覆盖 Value（HashSet 中 Value 恒为 PRESENT，Key 不变），元素不会真正插入，add 返回 false。

Q4：手写"生成 10 个 1~20 的不重复随机数"？答：见第 5 节代码，核心是利用hs.size() < 10作循环条件，重复随机数会被 add 自动拦截。

Q5：HashSet 与 TreeSet 的区别？如何保证唯一值？答：HashSet 基于 HashMap、无序、O(1) 查找，靠 hashCode+equals 去重；TreeSet 基于 TreeMap 红黑树、有序、O(log n) 查找，靠 compareTo/Comparator 返回 0 去重；HashSet 允许 null，TreeSet 不允许。

结语

HashSet 是"组合优于继承"设计思想的教科书级案例：它没有发明任何新数据结构，仅靠把元素包装成 HashMap 的 Key、用静态占位对象统一 Value，就完整获得了哈希表的存取、去重、扩容能力，全部源码不过两百行。理解 HashSet 的关键在于吃透两条链路：一是add/remove/contains 到 HashMap 的一行委托，二是HashMap putVal 中"hash 相等 + equals 相等"的双重去重判定。在此基础上，正确重写 hashCode 与 equals、合理预估初始容量、区分与 LinkedHashSet/TreeSet 的适用场景，就能在实战中可靠地用 HashSet 完成各类去重任务。

延伸阅读（YCBlogs 仓库内相关篇章）：

• java/04.数据结构/07.HashMap源码深度分析.md：HashSet 底层的完整实现（put/get/remove/resize/hash 扰动）
• java/04.数据结构/23.LinkedHashSet.md：有序去重的 LinkedHashSet 源码解析
• java/04.数据结构/24.TreeSet源码深入分析.md：基于红黑树的 TreeSet 原理
• question/java/03.Java数据结构问题.md：Set 家族对比与 hashCode/equals 面试题汇总
• java/04.数据结构/08.HashMap问题思考.md：HashMap 常见问题深入思考

• 教程
• 技术博客
• 文档