Java集合框架Set底层原理：HashSet与TreeSet深度解析

聊到 Java 集合框架，Set 永远是面试里绕不开的一类。HashMap 和 ArrayList 大家天天都在用，但 Set 常常被当成“一个能去重的 List”草草带过。我在面试候选人的时候问过一道题：“HashSet 的 add 方法底层到底做了什么？”能把这条链路完整讲清楚的人真的不多，大部分人停留在“先算 hashCode 再 equals”这个层面。这句话没错，但离真正理解还差得很远。

这篇文章打算把 HashSet 和 TreeSet 的底层原理一次说透：包括它们各自依赖的数据结构、去重机制、排序规则、扩容参数对性能的影响，以及我这些年实际项目里踩过的坑。适合正在准备 Java 面试的开发者，也适合工作中要处理复杂集合、想搞明白“为什么这么写就出问题了”的读者。看完你能收获的不只是面试答案，更重要的是以后用 Set 的时候知道自己在做什么。

1. 先搞清楚 Set 到底在解决什么问题

1.1 集合的本质与日常用法

Set 从语义上讲是数学里的“集合”：元素互不相同、没有先后顺序（或者说不强调顺序）。Java 里 Set 是一个接口，最常用的实现是 HashSet、TreeSet 和 LinkedHashSet。日常业务里最常见的用法就是去重，比如统计一批订单号里的唯一商户、过滤重复的 IP、收集用户点击过的商品 ID。这些场景的共同点是：我们只关心“出现过没有”，不关心“出现了几次”，也不一定关心“先来后到”。

举个例子，一个简单的统计代码：

List<String> orderIds = Arrays.asList("A001", "A002", "A001", "A003", "A002"); Set<String> uniqueOrders = new HashSet<>(orderIds); System.out.println(uniqueOrders.size()); // 3

这里直接把 List 丢进 HashSet 的构造器，重复元素就被过滤掉了。这个操作背后发生了什么？HashSet 会挨个调用 add 方法，而 add 方法内部并不是像很多人想的那样“遍历已有元素逐个 equals 比较”，它是一种完全不同的机制，靠的是哈希表。这也是 HashSet 和 TreeSet 最本质的区别所在：一个用哈希换速度，一个用树换有序。

1.2 去重背后的三个关键约定

Java 里所有 Set 实现都遵守同一个契约：集合中不会存在两个元素 e1 和 e2 满足 e1.equals(e2)。这句话看着像废话，但它是理解后面所有源码的钥匙。去重的判据是 equals 而不是 ==，这一点决定了我们往 Set 里放自定义对象时，必须正确处理 equals 方法。

同时，HashSet 的去重还依赖另一个方法：hashCode。Set 接口的文档里明确写着：如果两个对象通过 equals 比较相等，那么它们的 hashCode 必须相同；反过来不成立，不同对象可以有相同哈希值。这个约定不是可选项，而是哈希表能正常工作的前提。

我经常跟团队里的新人说：往 Set 里放自定义对象之前，先问自己三个问题——equals 写了吗？hashCode 写了吗？这两个方法依赖的字段有没有可能改变？第三个问题是最容易被忽视的，后面专门有一节讲这个坑。

2. HashSet 原理：一个“披着羊皮的 HashMap”

2.1 底层结构：HashMap 如何撑起去重

HashSet 的源码非常短，因为它根本不自己做存储，所有逻辑都委托给了 HashMap。看 JDK 的源码，HashSet 里维护了一个 HashMap 字段：

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { private transient HashMap<E, Object> map; 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 里 add 元素，实际上是往 HashMap 里 put 这个元素作为 key，value 统一用一个共享的占位对象 PRESENT。为什么能这样设计？因为 HashMap 的 key 天然就是唯一的，重复 put 相同 key 会覆盖旧值并返回旧值；而 put 返回 null 表示之前没有这个 key，正好对应 Set 里“这次 add 产生了新元素”。这一手委托设计非常巧妙，代码量少，还不破坏语义。

读到这里你应该意识到了：理解 HashSet 的本质，就是理解 HashMap 的 put 流程。HashMap 内部是一个数组加链表（JDK 8 以后还有红黑树）的结构。put 的时候，先根据 key 的 hashCode 计算出桶下标，如果这个桶里没有元素，直接放进去；如果已经有元素了，就会在链表或树里用 equals 逐个比较，看 key 是否已经存在。

2.2 hash() 方法：扰动函数到底扰动了什么

HashMap 在计算桶下标之前，会先调用一个静态方法 hash()：

static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }

这个操作叫“扰动函数”。hashCode 返回的是一个 32 位 int，而 HashMap 的桶下标是用 (n - 1) & hash 算出来的，n 是数组长度。当数组长度比较小的时候（比如默认 16），参与运算的只有 hash 的低 4 位，高位信息完全被丢弃。这样做的后果是：只要 hashCode 的低位相同、高位不同，就一定会碰撞。

扰动函数的思路是把高 16 位通过异或混入低 16 位，让高位的信息也参与下标计算。这样即使两个对象的 hashCode 在高位有明显差异、低位相同，经过扰动后落到同一桶的概率也会大大降低。这属于工程上的“低成本高收益”优化：就一行位运算，却能显著改善哈希分布。

实际开发中，这个细节和你直接相关的是：自定义对象的 hashCode 不要设计得太“稀疏”。比如一个对象的唯一 ID 是 Long 类型，如果直接返回 id.hashCode()，而 id 恰好都是 2 的幂次倍数，低位全是 0，那么大量元素会堆在同一个桶里，HashSet 的时间复杂度从 O(1) 直接退化成 O(n)。JDK 的 Objects.hash() 虽然方便，但不是万能的，关键要看业务字段的真实分布。

2.3 容量、负载因子与扩容机制

HashSet 默认构造器创建的是一个初始容量 16、负载因子 0.75 的 HashMap。负载因子的含义是：当元素个数超过容量乘以负载因子时，触发扩容。默认值算下来，就是元素数量超过 12 个（16 * 0.75 = 12）时，数组扩容到原来的两倍，也就是 32。

这里有个参数选择问题值得展开。负载因子越大（比如 1.0），空间利用率越高，但碰撞概率也越高，链表变长的风险加大；负载因子越小（比如 0.5），碰撞少、查询快，但浪费的空间多，扩容也更频繁。0.75 是 JDK 团队在时间和空间之间做的一个折中，绝大多数场景直接用它就好。真正值得手动指定的是初始容量：如果你事先知道要存的数据量很大，比如 100 万条，直接用默认容量会导致频繁扩容，每次扩容都要重新计算所有元素的桶下标，非常消耗性能。

正确的姿势是预先估算容量：

// 期望存储 100 万条数据，负载因子 0.75 // 需要初始容量 = 1000000 / 0.75 + 1 ≈ 1333334 Set<String> set = new HashSet<>(1333334);

为什么不直接传 1000000？因为 HashMap 的扩容阈值是容量乘负载因子，如果你只传 1000000，那么存入 75 万条左右就开始扩容了，等于你的“预分配”白做了。加 1 是防止 1000000 正好落在扩容阈值上（虽然概率低，但边界条件不能赌）。另外，HashMap 构造器对于传入的容量还会做一次补位运算，把它调整为大于等于该值的 2 的幂次，所以传 1333334 实际得到的底层数组长度是 2097152（2^21）。这也是(n - 1) & hash这个位运算能高效工作的前提：n 是 2 的幂，n - 1 的二进制全是低位 1，与运算等价于取模。

2.4 hashCode 和 equals：那个绕不开的契约

面试里最经典的问题之一：为什么重写 equals 必须重写 hashCode？用 HashSet 的视角回答最直观。当你往 HashSet 里放对象时，它用 hashCode 定位桶，再用 equals 精确比较。如果两个对象 equals 相等但 hashCode 不同，它们会被分到不同的桶里，Set 就会认为它们是两个不同的元素，去重失败。反过来，如果 hashCode 相同但 equals 不相等（哈希碰撞），它们会落在同一个桶里，通过链表或树共存，这没问题，只是查询性能会下降。

在 JDK 源码里，这种“先比较哈希定位，再 equals 确认”的逻辑体现在 HashMap 的 putVal 方法里：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K, V>[] tab; int n = (tab = table).length; int i = (n - 1) & hash; if (tab[i] == null) { tab[i] = newNode(hash, key, value, null); } else { Node<K, V> e; K k; if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) { e = p; } // ... 链表遍历或树遍历 } }

注意这行判断：p.hash == hash && (k == key || key.equals(k))。它先比较哈希值，哈希值不一样就直接跳过 equals，这是性能优化；哈希一致了再用 == 或 equals 确认。所以 hashCode 决定了性能，equals 决定了正确性，两者缺一不可。

3. TreeSet 原理：有序集合背后的红黑树

3.1 底层结构：TreeMap 与红黑树

如果说 HashSet 的靠山是 HashMap，那 TreeSet 的靠山就是 TreeMap。TreeSet 的源码同样很短，内部持有一个 NavigableMap，默认构造器创建的就是 TreeMap：

public class TreeSet<E> extends AbstractSet<E> implements NavigableSet<E>, Cloneable, java.io.Serializable { private transient NavigableMap<E, Object> m; private static final Object PRESENT = new Object(); public TreeSet() { this(new TreeMap<>()); } public boolean add(E e) { return m.put(e, PRESENT) == null; } }

TreeMap 不再用数组加链表，而是一棵红黑树，每个节点包含 key、value、左右子节点和颜色标记。红黑树是一种自平衡的二叉搜索树，它保证从根节点到任意叶子节点的路径中，黑色节点的数量相同，且不存在两个连续的红色节点。这些约束让树的高度保持在 O(log n) 量级，所有查找、插入、删除操作的时间复杂度都是 O(log n)。

为什么 TreeSet 要用红黑树而不是普通二叉搜索树？因为普通二叉搜索树在最坏情况下会退化成链表。比如你按顺序插入 1, 2, 3, 4, 5，每个新节点都挂在右子树，树的高度变成 n，查找复杂度退化成 O(n)。红黑树通过在插入和删除后执行旋转和变色操作，维持树的平衡，避免了这种灾难。

3.2 排序规则：自然排序与 Comparator

TreeSet 的元素顺序由两种方式决定。第一种是自然排序，元素本身实现 Comparable 接口，TreeSet 用 compareTo 方法比较大小；第二种是传入一个 Comparator，TreeSet 完全按你定义的规则排序，元素自身的 Comparable 实现被忽略。

这里有个关键区别：TreeSet 判断元素重复靠的不是 equals，而是 compareTo 或 compare 的返回值。如果两个元素比较结果为 0，TreeSet 就认为它们是同一个元素，后插入的会覆盖先插入的。这一点和 HashSet 完全不同，也经常引发隐蔽的 bug。

看一个活生生的例子：

Set<String> set = new TreeSet<>(String.CASE_INSENSITIVE_ORDER); set.add("Java"); set.add("JAVA"); System.out.println(set.size()); // 1

size 是 1，因为 String.CASE_INSENSITIVE_ORDER 这个比较器认为 "Java" 和 "JAVA" 相等。但这两个字符串的 equals 返回 false。所以你的业务里如果同时依赖 Set 的去重和排序能力，一定要想清楚：TreeSet 的去重规则由比较器决定，不是你写的 equals 方法。如果比较器写得太粗（比如只按 ID 比较），两个字段不同但 ID 相同的对象就会被视为同一个。

使用 Comparator 时还有一点要注意：比较结果必须满足传递性，否则 TreeSet 的树结构会被破坏，出现“明明插入了却 contains 不到”的诡异现象。比如 A > B、B > C、C > A 这种循环比较，红黑树的插入逻辑会无所适从，数据错乱几乎是必然的。

3.3 红黑树的平衡机制（通俗版）

红黑树的插入流程大致是：先按二叉搜索树规则找到插入位置，把新节点标成红色，然后自底向上修复可能违反的约束。修复手段就两种：变色和旋转。如果父节点是黑色，直接插入完成；如果父节点是红色，就触发修复逻辑，可能是把父节点的兄弟节点变黑并向上递归，可能是对祖父节点做左旋或右旋。

这个过程听着复杂，但在 TreeMap 源码里只是 put 方法末尾的一个循环，同时检查颜色和位置关系，选择对应的修复分支。作为使用方，你不必背下所有旋转细节，但要知道它的代价：插入和删除的平均成本比 HashSet 高，因为除了定位，还要维护平衡。这也是 TreeSet 和 HashSet 性能差异的根源。

红黑树有一个实际影响值得记住：它不保证绝对的“矮”，只保证高度不超过 2 * log2(n + 1)。也就是说，同样存 100 万个元素，TreeSet 的查找最多需要约 40 次比较（2 * log2(1000001) ≈ 40），而 HashSet 在哈希均匀的理想情况下只需要 1 到 2 次。这个差距在数据量小的时候无所谓，上了百万量级会变得非常明显。

3.4 性能数据与适用场景

我做过一个简单的基准测试：向 HashSet 和 TreeSet 各插入 100 万个随机整数，然后随机查询其中 10 万个。HashSet 的插入和查询都在几十毫秒量级，TreeSet 则在几百毫秒量级，差距接近一个数量级。在数据量小（几百条）的时候两者差别几乎感知不到，但随着规模上升，哈希结构的优势会被放大。

TreeSet 的不可替代性在于它提供了一组 HashSet 做不到的操作：获取最小值和最大值（first / last）、获取小于某个值的最大元素（floor / lower）、获取大于某个值的最小元素（ceiling / higher）、按范围截取子集（subSet / headSet / tailSet）。如果你有类似“找到距离目标值最近的前一个和后一个元素”的需求，TreeSet 是天然的选择。

所以我的选型原则很简单：只去重，用 HashSet；去重加排序，用 TreeSet；去重但想保留插入顺序，用 LinkedHashSet。别为了一个排序功能牺牲掉 O(1) 的哈希性能，也别为了用 TreeSet 的高端 API 而硬塞进去。

4. HashSet、TreeSet、LinkedHashSet 三兄弟怎么选

4.1 三者核心差异对比

很多初学者搞不清 HashSet 和 LinkedHashSet 的区别。LinkedHashSet 继承自 HashSet，底层是用 LinkedHashMap 实现的，它在 HashMap 的基础上给每个桶里的第一个节点加了一条双向链表，专门记录插入顺序。所以 LinkedHashSet 的去重逻辑和 HashSet 完全一样，只是额外维护了顺序信息。

把三者放在一起对比一下：

这张表里最容易翻车的是 TreeSet 的 null 处理。自然排序模式下，TreeSet 插入 null 会直接抛 NullPointerException，因为 null 无法调用 compareTo 方法。但如果你传入的 Comparator 自己写了 null 处理逻辑，比如把 null 排在最前面，那么 TreeSet 是可以接受 null 的。这个行为很多人不知道，面试里问到“TreeSet 能存 null 吗”时，正确的回答是“默认不能，除非 Comparator 显式支持”。

4.2 选型决策参考

我建议用一张决策图来思考，但这里不用图画，用文字描述逻辑链：

第一步，问自己：需要排序吗？如果不需要，看第二步；如果需要，直接选 TreeSet，但先确认元素是否能定义出稳定且满足传递性的比较规则。

第二步，问自己：需要保持插入顺序吗？如果需要，选 LinkedHashSet；如果不需要，选 HashSet。

这个决策过程的依据核心是性能：HashSet 的优势是 O(1) 的插入和查询，适合绝大多数场景；LinkedHashSet 在 HashSet 基础上只多了一个双向链表的维护开销，代价很小；TreeSet 的 O(log n) 成本在大数据量下不可忽视，只有在真正需要有序性时才值得付出。

还有一个细节是初始化时的容量差异。TreeSet 不支持像 HashSet 那样指定初始容量，因为它底层是树结构，容量概念不适用。如果你明确知道数据量，HashSet 可以提前分配容量避免扩容，而 TreeSet 的插入成本主要是树的旋转和比较，没法通过预分配优化。

4.3 内存开销实测对比

关于内存，我实测过一次。插入 10 万个自定义小对象（两个 int 字段），HashSet 大约占用 6 MB，LinkedHashSet 大约 6.5 MB，TreeSet 大约 9 MB。树结构每个节点要存左右子节点引用和颜色标记，这些额外字段加起来相当可观。换句话说，在数据量大、对内存敏感的服务里，TreeSet 要慎用，尤其是当排序需求可以通过“插入后统一排序一次”来替代时。

有一种常见的错误用法是：数据频繁写入，读取时偶尔需要有序结果，于是全程用 TreeSet 维护有序。如果写入量远大于读取量，这个设计很亏，因为每次写入都付出 O(log n) 的树维护成本。更好的方案是用 HashSet 收集数据，需要排序的时候再转成 List 排序一次：

List<String> list = new ArrayList<>(hashSet); Collections.sort(list); // 或者 list.sort(Comparator.naturalOrder());

这样做在“读写比例悬殊”的场景下能省下大量维护成本。写多读少用哈希加懒排序，写少读多用 TreeSet 持续有序，这是一条很实用的经验。

5. 实战中那些坑，我替你们踩过了

5.1 可变对象放进 Set 之后意识不到的问题

这是我在代码评审里见过最多的问题，没有之一。把对象放进 HashSet 之后，又修改了对象的 hashCode 相关字段，导致集合彻底乱掉。

我举个例子：

User user = new User(1L, "张三"); Set<User> set = new HashSet<>(); set.add(user); user.setName("李四"); // 假设 name 参与了 hashCode 计算 System.out.println(set.contains(user)); // 大概率是 false！

contains 返回 false 的原因在于：user 的 name 变了，hashCode 也随之变化，计算出的桶下标和插入时不一样了。HashSet 到原来的桶里去找，发现那个桶是空的；而 user 实际所在的桶，HashSet 在 contains 时根本不会去访问。更可怕的是，remove 也删不掉这个“迷路”的元素，set.size() 依然把它算在里面，但它已经永远无法被访问到了。这就是“内存泄漏”的又一种形态。

正确的做法是：放进 Set 的对象应该是不可变的，或者至少保证 hashCode 依赖的字段在放入后不被修改。如果业务上必须修改，那就先 remove 再改再 add。这个道理同样适用于 HashMap 的 key，这两个容器在这方面的行为完全一致。

我在项目里定过一条规则：凡是作为 Set 元素或 Map key 的类，要么做成不可变类，要么在字段设计时明确标注哪些字段参与 hashCode，并在文档里写明“写入后禁止修改”。

5.2 equals 不对称：contains 明明应该有却返回 false

对称性是 equals 方法的基本要求：a.equals(b) 和 b.equals(a) 必须一致。但很多人用继承的时候没注意这一点。比如子类继承了父类的 equals，但子类又加了新的字段，如果 equals 用了 instanceOf 或者 getClass 判断不当，就会出现不对称。

一个经典场景是：父类 BaseEntity 用 ID 判断相等，子类 User 扩展了 name 字段，重写了 equals 要同时比较 name。那么 BaseEntity.equals(user) 可能返回 true（因为 ID 相同），而 user.equals(baseEntity) 返回 false（因为 baseEntity 没有 name 字段）。这会让 Set 的去重行为变得不可预测。

常见的规避手段有两种：一是在 equals 里用getClass() != o.getClass()严格判断类型，拒绝跨类型比较；二是约定所有实体类不用继承关系复合 equals，而是用组合或统一走接口。我偏向第二种，因为第一种虽然解决了对称性，但也破坏了里氏替换原则，有时候会让代码僵化。团队里明确约定“equals 只在同一类内部比较”，实际发生的 bug 最少。

5.3 遍历时删除元素的 ConcurrentModificationException

很多人写过这样的代码：

Set<String> set = new HashSet<>(); set.add("a"); set.add("b"); set.add("c"); for (String s : set) { if (s.equals("b")) { set.remove(s); // 会抛 ConcurrentModificationException } }

原因很简单：迭代器持有 modCount 快照，每次 next 时都会检查集合的 modCount 是否被外部修改过。直接调用 set.remove 会修改 modCount，导致迭代器校验失败。正确的做法是用迭代器自己的 remove 方法，或者用 JDK 8 的 removeIf：

set.removeIf(s -> s.equals("b"));

或者：

Iterator<String> it = set.iterator(); while (it.hasNext()) { String s = it.next(); if (s.equals("b")) { it.remove(); } }

removeIf 的底层就是用迭代器实现的，所以能安全删除。如果你在循环里同时做“判断后删除”和“判断后插入”，那要格外小心，插入操作同样会触发 ConcurrentModificationException，除非你用的是 ConcurrentSkipListSet 这类并发容器。

5.4 Set 与 null 和空集合的边界

HashSet 允许存入一个 null，因为 HashMap 的 hash() 方法对 null 有特殊处理，返回 0，所以 null 会落到 0 号桶。但 TreeSet 默认对 null 不友好，前面已经说过会抛 NPE。LinkedHashSet 和 HashSet 一样允许一个 null。

另一个边界是空集合。Collections.emptySet() 返回的集合是不可变的，调用 add 会抛 UnsupportedOperationException。很多人从工具方法里拿到一个 emptySet，以为可以像普通 Set 一样往里加元素，结果线上直接炸。判断一个 Set 是否可变的简单方法：看它来自哪里。如果来自 Arrays.asList 的相关转换或 Collections 工具类，通常不可变；来自 new 出来的实现类，通常可变。

6. 从源码层面理解两个高频面试考点

6.1 为什么 HashSet 不允许重复却能存 null

HashMap 允许一个 null 的 key，这是它的设计选择。hash() 方法里对 null 返回 0，所以 null 永远定位到 0 号桶。HashSet 复用 HashMap，自然也就允许一个 null 元素。面试时如果被问到这一点，你可以顺带解释：允许一个 null 不破坏 Set 的去重语义，因为 null 只有一个，第二次 add(null) 会覆盖第一次的值，返回旧值，Set 不会变长。

我见过一些候选人在这里犯糊涂：他们背了“HashMap 允许 null，Hashtable 不允许”，却不知道 HashSet 和 HashMap 的关系，更不知道 TreeSet 对 null 的态度。一条清晰的记忆线索是：底层是哈希表的允许一个 null，底层是树的不默认允许，除非比较器特殊处理。

6.2 TreeSet 传 Comparator 和自然排序的细微差别

另一个容易答偏的考点：TreeSet 构造时传了 Comparator，元素的 Comparable 实现还有没有用？答案是没用。TreeSet 内部所有比较都通过 comparator 完成，你传进去的 Comparator 会完全覆盖元素的自然排序逻辑。看 TreeMap 的源码，put 方法里比较逻辑会优先用 comparator：

final int compare(Object k1, Object k2) { return comparator == null ? ((Comparable<? super K>) k1).compareTo((K) k2) : comparator.compare((K) k1, (K) k2); }

所以面试官问你“TreeSet 的去重和排序依据是什么”，标准回答是：如果没有传 Comparator，用元素的 Comparable 自然排序；如果传了 Comparator，用 Comparator 的结果。但无论哪种，都基于 compareTo / compare 的返回值，而不是 equals 方法。

有一个更深的问题值得说出来：既然 TreeSet 用 compare 判重，那这棵树里的两个元素会不会出现“compare 相等但 equals 不相等”？在上面的 String.CASE_INSENSITIVE_ORDER 例子里就会。这时候 TreeSet 的行为是“留一个”，而 HashSet 可能会留两个。这个差异在分布式系统的一致性计算、日志合并等场景里可能造成数据不一致，值得引起重视。

7. 实操：手写一个稳如老狗的自定义对象 Set

7.1 正确实现 hashCode 与 equals

理论说了这么多，落实到代码才是关键。假设我们要用 Set 管理一批用户对象，业务唯一键是 userId。object 定义如下：

public class User { private final Long userId; private String name; private int age; public User(Long userId, String name, int age) { this.userId = userId; this.name = name; this.age = age; } // getters... @Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof User user)) { return false; } return Objects.equals(userId, user.userId); } @Override public int hashCode() { return Objects.hash(userId); } }

这里的关键设计：equals 和 hashCode 都只依赖 userId，并且 userId 是 final 的，从根本上避免了 5.1 节描述的“放入后修改导致元素丢失”的问题。业务上如果允许两个不同 userId 的用户有相同的 name 和 age，这个实现完全正确；如果唯一键是 userId + 关联的租户 ID，那就要一起加进去：

@Override public boolean equals(Object o) { if (this == o) { return true; } if (!(o instanceof User user)) { return false; } return Objects.equals(userId, user.userId) && Objects.equals(tenantId, user.tenantId); } @Override public int hashCode() { return Objects.hash(userId, tenantId); }

7.2 实际效果验证

写完之后，做一个简单的验证，确保各种边界情况都符合预期：

Set<User> users = new HashSet<>(); User a = new User(1L, "张三", 25); User b = new User(1L, "李四", 30); // 不同实例，同 userId users.add(a); System.out.println(users.add(b)); // false，因为 userId 相同 System.out.println(users.size()); // 1 System.out.println(users.contains(b)); // true，按 userId 命中

我建议你在自己的项目里把这个小测试跑起来，确认 equals 的实现符合业务预期。尤其是“contains 用另一个只有 userId 的对象去查”这种场景，很多人会疑惑为什么能查到——因为 HashSet 靠 hashCode 定位、靠 equals 确认，equals 里只比较了 userId，所以一个残缺对象也能命中。这在业务上有时是特性，有时是隐患，取决于你的 equals 设计。

7.3 几个工程级建议

第一，能用项目里的公共工具类就别手写。很多团队引入了 Lombok，可以用 @EqualsAndHashCode 注解自动生成，但要注意指定字段。比如只按 userId 比较，就写：

@EqualsAndHashCode(of = "userId") public class User { ... }

第二，如果类可能被继承，在 equals 里加一个类型严格判断：

if (getClass() != o.getClass()) { return false; }

这会牺牲一点灵活性，但能避免 5.2 节说的不对称问题。

第三，如果对象要被序列化或者跨服务传输，equals 依赖的字段不能是易变字段。服务 A 和服务 B 对“相同用户”的定义必须一致，否则两个服务各自维护的 Set 会出现数据分叉。这种问题在微服务环境里非常难排查，因为日志里看起来都是合法的。

8. 关于性能调优，最后想分享的三条经验

第一条：不要盲目设置初始容量。我看到有人习惯性写new HashSet<>(10000)，但如果实际数据只有几百条，这个容量会让底层数组白白占内存。可以先评估数据规模，再决定要不要预分配。没有明确量级的时候，默认构造器是最稳的选择。

第二条：能用基本类型包装类替代自定义对象时，尽量用。Integer、Long、String 这些类型的 hashCode 实现都是官方优化过的，分布均匀，不急着自己造轮子。自定义对象的哈希质量取决于你的字段设计，写不好就是给自己埋雷。

第三条：在并发场景下，别用 Collections.synchronizedSet 包装 HashSet 后以为万事大吉。这个包装类同步的是方法级别的操作，但遍历和修改的复合操作依然有并发问题。Java 提供的 ConcurrentSkipListSet 是有序并发 Set，底层是跳表，读多写少的场景表现不错；如果只去重不需要排序，可以自己用 ConcurrentHashMap.newKeySet() 得到并发安全的 Set，它底层就是 ConcurrentHashMap，性能比 synchronized 包装好很多。

我一般是这样用的：单线程或用 ConcurrentHashMap.newKeySet()，需要有序并发操作才考虑 ConcurrentSkipListSet。很少用 synchronizedSet，因为它粒度太粗，竞争激烈时吞吐量掉得厉害。

回到文章开头那个问题——“HashSet 的 add 方法底层到底做了什么”。现在你可以完整地回答了：add 会调用 HashMap 的 put，把元素作为 key，PRESENT 作为 value；put 内部先对 key 做扰动 hash，用数组长度减一与哈希值做位运算得到桶下标；如果桶为空直接放入，否则通过 equals 在链表或红黑树中查找；如果 key 已存在就覆盖 value 并返回旧值，add 据此判断结果是 true 还是 false。这套链路里每一个环节都对应一个实际的性能决策和潜在坑点。

我个人在实际开发里最大的体会是：Set 的问题很少出在“不会用”，而是出在“没想清楚底层是哈希还是树”。哈希结构快但无序，树结构有序但贵，加上 equals 和 hashCode 的契约约束，几乎所有的生产事故都能从这三个维度找到根因。把这一层想通了，面试问什么变体你都能接住。