聊到 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。这些场景的共同点是我们只关心“出现过没有”不关心“出现了几次”也不一定关心“先来后到”。举个例子一个简单的统计代码ListString orderIds Arrays.asList(A001, A002, A001, A003, A002); SetString 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 HashSetE extends AbstractSetE implements SetE, Cloneable, java.io.Serializable { private transient HashMapE, 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 这个元素作为 keyvalue 统一用一个共享的占位对象 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 SetString set new HashSet(1333334);为什么不直接传 1000000因为 HashMap 的扩容阈值是容量乘负载因子如果你只传 1000000那么存入 75 万条左右就开始扩容了等于你的“预分配”白做了。加 1 是防止 1000000 正好落在扩容阈值上虽然概率低但边界条件不能赌。另外HashMap 构造器对于传入的容量还会做一次补位运算把它调整为大于等于该值的 2 的幂次所以传 1333334 实际得到的底层数组长度是 20971522^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) { NodeK, V[] tab; int n (tab table).length; int i (n - 1) hash; if (tab[i] null) { tab[i] newNode(hash, key, value, null); } else { NodeK, 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默认构造器创建的就是 TreeMappublic class TreeSetE extends AbstractSetE implements NavigableSetE, Cloneable, java.io.Serializable { private transient NavigableMapE, 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 排序规则自然排序与 ComparatorTreeSet 的元素顺序由两种方式决定。第一种是自然排序元素本身实现 Comparable 接口TreeSet 用 compareTo 方法比较大小第二种是传入一个 ComparatorTreeSet 完全按你定义的规则排序元素自身的 Comparable 实现被忽略。这里有个关键区别TreeSet 判断元素重复靠的不是 equals而是 compareTo 或 compare 的返回值。如果两个元素比较结果为 0TreeSet 就认为它们是同一个元素后插入的会覆盖先插入的。这一点和 HashSet 完全不同也经常引发隐蔽的 bug。看一个活生生的例子SetString set new TreeSet(String.CASE_INSENSITIVE_ORDER); set.add(Java); set.add(JAVA); System.out.println(set.size()); // 1size 是 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 完全一样只是额外维护了顺序信息。把三者放在一起对比一下维度HashSetTreeSetLinkedHashSet底层结构HashMapTreeMap红黑树LinkedHashMap元素顺序无保证按比较器排序按插入顺序核心操作复杂度O(1)O(log n)O(1)是否允许 null允许自然排序时不允许允许去重判据equalscompareTo / compareequals适用场景高频去重、快速查找有序遍历、范围查询去重且需要保序这张表里最容易翻车的是 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 MBLinkedHashSet 大约 6.5 MBTreeSet 大约 9 MB。树结构每个节点要存左右子节点引用和颜色标记这些额外字段加起来相当可观。换句话说在数据量大、对内存敏感的服务里TreeSet 要慎用尤其是当排序需求可以通过“插入后统一排序一次”来替代时。有一种常见的错误用法是数据频繁写入读取时偶尔需要有序结果于是全程用 TreeSet 维护有序。如果写入量远大于读取量这个设计很亏因为每次写入都付出 O(log n) 的树维护成本。更好的方案是用 HashSet 收集数据需要排序的时候再转成 List 排序一次ListString list new ArrayList(hashSet); Collections.sort(list); // 或者 list.sort(Comparator.naturalOrder());这样做在“读写比例悬殊”的场景下能省下大量维护成本。写多读少用哈希加懒排序写少读多用 TreeSet 持续有序这是一条很实用的经验。5. 实战中那些坑我替你们踩过了5.1 可变对象放进 Set 之后意识不到的问题这是我在代码评审里见过最多的问题没有之一。把对象放进 HashSet 之后又修改了对象的 hashCode 相关字段导致集合彻底乱掉。我举个例子User user new User(1L, 张三); SetUser set new HashSet(); set.add(user); user.setName(李四); // 假设 name 参与了 hashCode 计算 System.out.println(set.contains(user)); // 大概率是 falsecontains 返回 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很多人写过这样的代码SetString 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 的 removeIfset.removeIf(s - s.equals(b));或者IteratorString 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 不允许重复却能存 nullHashMap 允许一个 null 的 key这是它的设计选择。hash() 方法里对 null 返回 0所以 null 永远定位到 0 号桶。HashSet 复用 HashMap自然也就允许一个 null 元素。面试时如果被问到这一点你可以顺带解释允许一个 null 不破坏 Set 的去重语义因为 null 只有一个第二次 add(null) 会覆盖第一次的值返回旧值Set 不会变长。我见过一些候选人在这里犯糊涂他们背了“HashMap 允许 nullHashtable 不允许”却不知道 HashSet 和 HashMap 的关系更不知道 TreeSet 对 null 的态度。一条清晰的记忆线索是底层是哈希表的允许一个 null底层是树的不默认允许除非比较器特殊处理。6.2 TreeSet 传 Comparator 和自然排序的细微差别另一个容易答偏的考点TreeSet 构造时传了 Comparator元素的 Comparable 实现还有没有用答案是没用。TreeSet 内部所有比较都通过 comparator 完成你传进去的 Comparator 会完全覆盖元素的自然排序逻辑。看 TreeMap 的源码put 方法里比较逻辑会优先用 comparatorfinal 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. 实操手写一个稳如老狗的自定义对象 Set7.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 实际效果验证写完之后做一个简单的验证确保各种边界情况都符合预期SetUser 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把元素作为 keyPRESENT 作为 valueput 内部先对 key 做扰动 hash用数组长度减一与哈希值做位运算得到桶下标如果桶为空直接放入否则通过 equals 在链表或红黑树中查找如果 key 已存在就覆盖 value 并返回旧值add 据此判断结果是 true 还是 false。这套链路里每一个环节都对应一个实际的性能决策和潜在坑点。我个人在实际开发里最大的体会是Set 的问题很少出在“不会用”而是出在“没想清楚底层是哈希还是树”。哈希结构快但无序树结构有序但贵加上 equals 和 hashCode 的契约约束几乎所有的生产事故都能从这三个维度找到根因。把这一层想通了面试问什么变体你都能接住。
聊到 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。这些场景的共同点是我们只关心“出现过没有”不关心“出现了几次”也不一定关心“先来后到”。举个例子一个简单的统计代码ListString orderIds Arrays.asList(A001, A002, A001, A003, A002); SetString 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 HashSetE extends AbstractSetE implements SetE, Cloneable, java.io.Serializable { private transient HashMapE, 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 这个元素作为 keyvalue 统一用一个共享的占位对象 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 SetString set new HashSet(1333334);为什么不直接传 1000000因为 HashMap 的扩容阈值是容量乘负载因子如果你只传 1000000那么存入 75 万条左右就开始扩容了等于你的“预分配”白做了。加 1 是防止 1000000 正好落在扩容阈值上虽然概率低但边界条件不能赌。另外HashMap 构造器对于传入的容量还会做一次补位运算把它调整为大于等于该值的 2 的幂次所以传 1333334 实际得到的底层数组长度是 20971522^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) { NodeK, V[] tab; int n (tab table).length; int i (n - 1) hash; if (tab[i] null) { tab[i] newNode(hash, key, value, null); } else { NodeK, 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默认构造器创建的就是 TreeMappublic class TreeSetE extends AbstractSetE implements NavigableSetE, Cloneable, java.io.Serializable { private transient NavigableMapE, 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 排序规则自然排序与 ComparatorTreeSet 的元素顺序由两种方式决定。第一种是自然排序元素本身实现 Comparable 接口TreeSet 用 compareTo 方法比较大小第二种是传入一个 ComparatorTreeSet 完全按你定义的规则排序元素自身的 Comparable 实现被忽略。这里有个关键区别TreeSet 判断元素重复靠的不是 equals而是 compareTo 或 compare 的返回值。如果两个元素比较结果为 0TreeSet 就认为它们是同一个元素后插入的会覆盖先插入的。这一点和 HashSet 完全不同也经常引发隐蔽的 bug。看一个活生生的例子SetString set new TreeSet(String.CASE_INSENSITIVE_ORDER); set.add(Java); set.add(JAVA); System.out.println(set.size()); // 1size 是 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 完全一样只是额外维护了顺序信息。把三者放在一起对比一下维度HashSetTreeSetLinkedHashSet底层结构HashMapTreeMap红黑树LinkedHashMap元素顺序无保证按比较器排序按插入顺序核心操作复杂度O(1)O(log n)O(1)是否允许 null允许自然排序时不允许允许去重判据equalscompareTo / compareequals适用场景高频去重、快速查找有序遍历、范围查询去重且需要保序这张表里最容易翻车的是 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 MBLinkedHashSet 大约 6.5 MBTreeSet 大约 9 MB。树结构每个节点要存左右子节点引用和颜色标记这些额外字段加起来相当可观。换句话说在数据量大、对内存敏感的服务里TreeSet 要慎用尤其是当排序需求可以通过“插入后统一排序一次”来替代时。有一种常见的错误用法是数据频繁写入读取时偶尔需要有序结果于是全程用 TreeSet 维护有序。如果写入量远大于读取量这个设计很亏因为每次写入都付出 O(log n) 的树维护成本。更好的方案是用 HashSet 收集数据需要排序的时候再转成 List 排序一次ListString list new ArrayList(hashSet); Collections.sort(list); // 或者 list.sort(Comparator.naturalOrder());这样做在“读写比例悬殊”的场景下能省下大量维护成本。写多读少用哈希加懒排序写少读多用 TreeSet 持续有序这是一条很实用的经验。5. 实战中那些坑我替你们踩过了5.1 可变对象放进 Set 之后意识不到的问题这是我在代码评审里见过最多的问题没有之一。把对象放进 HashSet 之后又修改了对象的 hashCode 相关字段导致集合彻底乱掉。我举个例子User user new User(1L, 张三); SetUser set new HashSet(); set.add(user); user.setName(李四); // 假设 name 参与了 hashCode 计算 System.out.println(set.contains(user)); // 大概率是 falsecontains 返回 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很多人写过这样的代码SetString 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 的 removeIfset.removeIf(s - s.equals(b));或者IteratorString 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 不允许重复却能存 nullHashMap 允许一个 null 的 key这是它的设计选择。hash() 方法里对 null 返回 0所以 null 永远定位到 0 号桶。HashSet 复用 HashMap自然也就允许一个 null 元素。面试时如果被问到这一点你可以顺带解释允许一个 null 不破坏 Set 的去重语义因为 null 只有一个第二次 add(null) 会覆盖第一次的值返回旧值Set 不会变长。我见过一些候选人在这里犯糊涂他们背了“HashMap 允许 nullHashtable 不允许”却不知道 HashSet 和 HashMap 的关系更不知道 TreeSet 对 null 的态度。一条清晰的记忆线索是底层是哈希表的允许一个 null底层是树的不默认允许除非比较器特殊处理。6.2 TreeSet 传 Comparator 和自然排序的细微差别另一个容易答偏的考点TreeSet 构造时传了 Comparator元素的 Comparable 实现还有没有用答案是没用。TreeSet 内部所有比较都通过 comparator 完成你传进去的 Comparator 会完全覆盖元素的自然排序逻辑。看 TreeMap 的源码put 方法里比较逻辑会优先用 comparatorfinal 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. 实操手写一个稳如老狗的自定义对象 Set7.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 实际效果验证写完之后做一个简单的验证确保各种边界情况都符合预期SetUser 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把元素作为 keyPRESENT 作为 valueput 内部先对 key 做扰动 hash用数组长度减一与哈希值做位运算得到桶下标如果桶为空直接放入否则通过 equals 在链表或红黑树中查找如果 key 已存在就覆盖 value 并返回旧值add 据此判断结果是 true 还是 false。这套链路里每一个环节都对应一个实际的性能决策和潜在坑点。我个人在实际开发里最大的体会是Set 的问题很少出在“不会用”而是出在“没想清楚底层是哈希还是树”。哈希结构快但无序树结构有序但贵加上 equals 和 hashCode 的契约约束几乎所有的生产事故都能从这三个维度找到根因。把这一层想通了面试问什么变体你都能接住。
