如果让我从Java集合框架里选一个“最容易被低估”的接口，我会投Set一票。List有索引、有顺序，Map有key-value，大家用起来都挺顺手；唯独Set，表面看只是“装不重复元素的容器”，可一旦深入到底层，HashSet、LinkedHashSet、TreeSet三兄弟的行为逻辑完全不同——有人吞掉重复元素，有人自动排序，有人默默记住插入顺序。选错实现类，轻则浪费内存，重则线上出Bug。这篇文章我就把这几个实现从原理到实战完整过一遍，适合正在学集合框架的初学者，也适合写了不少年代码但没认真抠过底层的老手。
1. 为什么单独聊Set：List之外的另一半江山
1.1 从一道面试题说起：Set到底解决了什么问题
先想一个问题：给你一批用户ID，要求过滤掉重复的，最后还要快速判断某个ID是否出现过。用List怎么写？每次判断都要遍历一遍，数据量一大立刻变慢，100万个元素里判断一个元素是否存在平均要扫描50万个位置，这个成本在写业务代码时往往被忽略。
Set的存在就是为了解决这类问题。它的语义直接借用了数学里的“集合”：元素互异、无序（某些实现有序）、强调“成员资格判断”。而Java集合框架面试里必问的那道题——HashSet、LinkedHashSet、TreeSet的区别——本质上就是在问：你知不知道不同底层的Set在“去重的同时付出了什么代价、得到了什么能力”。
List和Set的核心差异可以浓缩成三句话：
- List关心“位置”，Set关心“是否存在”
- List允许重复，Set天然去重
- List通过索引访问是O(1)，Set判断存在最差是O(log n)、平均是O(1)
所以Set的适用场景永远是那几类：去重、黑白名单判断、标签集合、数学意义的并交差操作。以后写代码前先问自己一句“我需要的是顺序容器还是成员判断容器”，能少走很多弯路。
1.2 Set家族成员一览：接口到实现类的层次关系
Set本身是个接口，下面挂着一条清晰的继承链。先搞清楚这棵“家谱”，后面讲原理才不会迷路：
Set：顶层接口，声明了add、remove、contains、size等基础方法AbstractSet：骨架实现，帮子类搞定了equals、hashCode等通用逻辑HashSet：哈希表实现，查找最快，但没有任何顺序保证LinkedHashSet：HashSet的子类，额外用双向链表维护插入顺序SortedSet/NavigableSet：对Set扩展了排序和范围查询语义TreeSet：基于红黑树，元素自动排序，支持大量范围操作
此外还有两个容易被忽略的干将：EnumSet处理枚举类型的位运算集合，极致轻量；CopyOnWriteArraySet走的是“写复制”路线，适合读多写少的高并发场景。这六个加在一起，才是“Set全家族”。
下面这张表可以先存着，后面所有篇幅都在给这张表填细节：
| 集合实现 | 底层结构 | 是否有序 | 搜索复杂度 | 线程安全 |
|---|---|---|---|---|
| HashSet | HashMap的key | 无序 | O(1) 平均 | 否 |
| LinkedHashSet | HashMap + 双向链表 | 插入顺序 | O(1) 平均 | 否 |
| TreeSet | TreeMap（红黑树） | 自然/自定义排序 | O(log n) | 否 |
| EnumSet | 位向量 | 枚举声明顺序 | O(1) | 否 |
| CopyOnWriteArraySet | CopyOnWriteArrayList | 插入顺序 | O(n) | 是 |
2. HashSet的哈希表底牌：快，但快得有代价
2.1 面纱后面的HashMap：HashSet是如何借用哈希表结构的
很多人不知道，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 boolean add(E e) { return map.put(e, PRESENT) == null; } public boolean contains(Object o) { return map.containsKey(o); } public boolean remove(Object o) { return map.remove(o) == PRESENT; } }看到了吗？HashSet就是把元素作为HashMap的key存进去，value统一填一个占位用的常量PRESENT。于是HashMap里和key相关的所有特性——哈希散列、去重、扩容——全被Set继承了。“去重”的本质也清楚了：HashMap的key本身就不允许重复。
理解了这层关系，第二个问题自然浮出来：HashMap是怎么把任意对象“散列”到数组里的？简化来看就是三步：
int h = key.hashCode(); // 第一步：调用对象的hashCode int hash = h ^ (h >>> 16); // 第二步：扰动函数，混合高低位 int index = (table.length - 1) & hash; // 第三步：映射到桶下标数组的每个位置叫“桶”，多个元素算出的index相同就发生哈希冲突。JDK 8之后的做法是：桶里先挂链表，元素数量超过阈值（链表长度≥8且数组长度≥64）后把链表转成红黑树。这也是为什么HashMap和HashSet的性能在数据分布均匀时能稳定在O(1)——如果所有元素全撞到一个桶里，最坏会退化成O(log n)甚至O(n)。
2.2 hashCode与equals的契约：不被重视就会出大问题
HashSet去重的判断逻辑分两步：先比hashCode定位桶，再在桶里用equals逐个比较。这个流程逼迫你记住一个硬性契约：
两个对象equals返回true，hashCode必须相等；hashCode相等，equals不一定相等。
违反契约的后果很严重。我见过最典型的错误是：定义了一个车票类，只重写了equals没重写hashCode，结果两张“等价”的车票因为hashCode不同，被放进了两个不同的桶，去重完全失效；反过来只重写hashCode不重写equals，会出现“hashCode相同但equals为false”的对象堆在同一桶里，HashSet能装得下一堆重复元素。
正确的写法应该是这样：
public class Ticket { private final String trainNo; private final String date; public Ticket(String trainNo, String date) { this.trainNo = trainNo; this.date = date; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Ticket ticket = (Ticket) o; return Objects.equals(trainNo, ticket.trainNo) && Objects.equals(date, ticket.date); } @Override public int hashCode() { return Objects.hash(trainNo, date); } }实操层面的关键是：参与equals的字段，最好都放进hashCode；如果业务上允许两个对象“内容等价”，那这两个对象的哈希结果必须一样。碰到真正需要手写hashCode的场景，用Objects.hash()就够了，别自己想花哨的位运算公式——我用过的经验是，朴素写法不仅正确率高，维护性也更好。
2.3 扩容与负载因子：为什么默认0.75，为什么容量要是2的幂
HashSet默认初始容量是16，负载因子是0.75。这两个数字不是拍脑袋定的。负载因子代表“数组被占用了多少比例时开始扩容”：默认情况下，桶数组用到12个（16×0.75）就触发一次扩容，容量翻倍到32，所有元素要重新散列。
为什么是0.75而不是1或0.5？这是空间和时间的权衡。调成1，桶利用率高了，但冲突概率变大，查询变慢；调成0.5，更快但一半空间闲置。我实测过数据量小时差距不明显，可数据量到百万级，0.75这个折中值确实最稳。
再看容量为什么要设计成2的幂。因为(table.length - 1) & hash这段位运算，等于hash % table.length取模，但位运算比取模快得多。还有一个隐藏好处：HashMap扩容时旧元素迁移新桶，可以通过“看新增位是0还是1”直接判断元素留在原位还是移动到“原索引+旧容量”的位置，省一次取模运算。这套设计在源码里反复出现，属于那种“底层优化你不一定用得上，但理解了会发现很多细节都是为一个目标服务的”典型例子。
这里给一个不少老手都会犯迷糊的初始化建议：假设你要往HashSet里塞100万个元素，直接new HashSet<>(1000000)其实不够聪明，因为初始容量会被调整成不小于指定值的2的幂（也就是1048576），但扩容阈值是容量×负载因子，约786432个元素时就会触发一次扩容。真不想扩容，初始化容量至少得取1_000_000 / 0.75 + 1，再让HashMap向上取到2的幂，也就是2097152。简单说，就是按“期望数据量除以负载因子再加一”去设置初始容量。
3. LinkedHashSet：想要顺序又想要速度的折中方案
3.1 双向链表+哈希表的组合逻辑
LinkedHashSet的代码量小得惊人，整个类几乎没写什么逻辑，因为它继承HashSet后，只是把底层的HashMap换成了LinkedHashMap。LinkedHashMap在HashMap的基础上，给每个节点额外增加了before、after两个引用，串成一条双向链表，专门用来记录元素进入的顺序。
这个设计带来一个关键行为变化：迭代LinkedHashSet时，元素的输出顺序等于插入顺序。注意，是“插入顺序”，不是“访问顺序”，也不是“自然排序”。试一段代码：
LinkedHashSet<String> set = new LinkedHashSet<>(); set.add("C"); set.add("A"); set.add("B"); set.add("A"); // 重复，被忽略 System.out.println(set); // [C, A, B]第二个“A”被忽略，而且不会把第一次插入的“A”挪到末尾。也就是说，重复元素不会改变它在链表里的位置。这个细节在实际业务里很重要——如果你要做“去重后仍然保留第一次出现的时间顺序”，LinkedHashSet天然就满足。
代价也很明确：每个元素多维护两个指针，占内存比HashSet多一点；插入和删除因为多了一步链表指针维护，性能略低于HashSet。但这个差距在常规业务规模下几乎感知不到，千万不要为了“省这点效率”放弃一个本来就足够好的选择。
3.2 什么业务场景真正需要插入顺序
我实际项目里用过LinkedHashSet的地方，一个典型的场景是“活动报名顺序去重”。用户提交报名记录，同一用户只能算一次，但后台展示时要按首次提交时间排序，这用LinkedHashSet一把梭就完成，不用先HashSet去重再额外按时间排序。类似的还有：消息系统里保留多人会话的首条消息顺序、日志采集时按第一次出现的host去重、爬虫任务里维护已访问URL并保持发现次序。
另一个容易和LinkedHashSet混淆的需求是“按热度排序”或者“按自然顺序排序”，那是TreeSet和业务排序的活。如果你只是想“保持我加入时的样子”，LinkedHashSet就是最合适的那个。它像是HashSet与TreeSet之间的缓冲带——既不放弃哈希结构的查询速度，又拿到了确定的迭代顺序。
4. TreeSet的红黑树世界：从Comparable到Comparator
4.1 为什么TreeSet能排序：二叉搜索树到红黑树的演进
TreeSet的内部同样借用了另一棵大树——TreeMap。TreeMap底层是一棵红黑树，一种自平衡的二叉搜索树。二叉搜索树的规则是：左子树的所有节点小于根节点，右子树的所有节点大于根节点，于是中序遍历就能得到有序序列。理想情况下插入、删除、查找都是O(log n)，但普通二叉搜索树有个致命弱点：如果数据恰好是递增插入，树会退化成一条链表，复杂度直接掉到O(n)。
红黑树的使命就是阻止这种退化。它通过五条规则约束树的形状：
- 节点非红即黑
- 根节点是黑色
- 所有叶子节点（NIL）是黑色
- 红色节点的子节点必须是黑色
- 任意节点到它所有叶子节点的路径上，黑色节点数量相同
这套规则听起来抽象，实际效果是保证任意路径的长度不会超过最短路径的两倍，树始终维持“近似平衡”。插入和删除时如果打破了规则，就通过变色和旋转（左旋、右旋）来修复。作为Java开发者，你不必每次插入都手动画树，但要理解：TreeSet的“自动排序”不是魔法，而是红黑树在每次插入和删除后做维护的结果，这也是它时间复杂度稳定O(log n)的根本原因。
4.2 比较器设计：compare返回0就是同一个元素
TreeSet里的“去重”和HashSet完全不同。HashSet靠hashCode + equals判等，TreeSet只认一个东西：比较器的结果。元素之间通过Comparable（自然排序）或自定义Comparator（比较器排序）比较，只要compare返回0，TreeSet就认为两个元素相等，后插入的那个直接被丢弃。
这一点极其重要，因为很多坑都从这里来。看个例子：
TreeSet<String> treeSet = new TreeSet<>(); treeSet.add("b"); treeSet.add("a"); treeSet.add("c"); System.out.println(treeSet); // [a, b, c]，自然排序字符串的compareTo按字典序比较，所以输出是有序的。但如果自定义比较器时“偷懒”，只看一部分字段，就会发生“两个内容不同的对象被当成同一个元素”的诡异现象：
TreeSet<User> set = new TreeSet<>(Comparator.comparing(User::getAge)); set.add(new User("Tom", 20)); set.add(new User("Jerry", 20)); System.out.println(set.size()); // 1，因为比较器只看age，两者相等这和HashSet靠equals判断的直觉完全不同，很多从HashSet切到TreeSet的开发者第一周都会在这里翻车。所以设计比较器时要问自己：我定义的这个“相等”边界，和业务上的相等概念一致吗？不一致就换一种比较策略。第二个容易犯的错是：参与排序的字段一旦在元素放入TreeSet后被修改，红黑树不会自动重新调整位置，排序状态会整个错乱。要避免这种情况，要么把元素设计成不可变类，要么禁止修改参与排序的字段。
4.3 TreeSet的NavigableSet能力与性能边界
TreeSet实现了NavigableSet，远不止“有序集合”这么简单。它自带一批范围操作，这是HashSet给不了的：
TreeSet<Integer> set = new TreeSet<>(); set.addAll(Arrays.asList(10, 5, 20, 15, 30)); System.out.println(set.first()); // 5 System.out.println(set.last()); // 30 System.out.println(set.lower(15)); // 10，严格小于15的最大元素 System.out.println(set.floor(15)); // 15，小于等于15的最大元素 System.out.println(set.ceiling(18)); // 20，大于等于18的最小元素 System.out.println(set.higher(20)); // 30，严格大于20的最小元素 System.out.println(set.subSet(10, 30)); // [10, 15, 20]，左闭右开这类方法在“排行榜前几名”“按时间筛选区间”“库存水位区间判定”等场景里非常实用。比如要查最近7天的活跃用户集合里，介于某两个时间点的用户，TreeSet直接给出结果，而用HashSet你得遍历所有元素再一个个过滤，复杂度完全不在一个量级。
当然，事情总有另一面。TreeSet每次插入都要做一次树结构的查找和平衡维护，常数开销比哈希大得多；如果数据量达到百万级，同一条插入操作它能比HashSet慢一个数量级。所以我说“快，但快得有代价”这句话同样适用于反向选择：TreeSet的排序能力是它的核心价值，如果一个场景根本不需要有序访问，就不该用它，这是后面选型部分的出发点之一。
5. 实战选型与性能对比：别凭感觉写代码
5.1 三种实现的差异表格
很多教科书喜欢把HashSet、LinkedHashSet、TreeSet的区别写成一段话，我却觉得不如一张表来得直观：
| 对比维度 | HashSet | LinkedHashSet | TreeSet |
|---|---|---|---|
| 底层结构 | HashMap | HashMap + 双向链表 | TreeMap（红黑树） |
| 元素顺序 | 无保证 | 插入顺序 | 自然/自定义排序 |
| 判重依据 | hashCode + equals | hashCode + equals | compare结果是否0 |
| 允许null | 允许一个null | 允许一个null | 自然排序时不允许 |
| 插入/删除 | O(1) 平均 | O(1) 平均，常数略高 | O(log n) |
| 有序遍历 | 不支持 | 按插入序 | 按排序序 |
| 范围查询 | 不支持 | 不支持 | 支持 |
| 典型内存开销 | 较低 | 每个节点多两个引用 | 节点含颜色标记，开销较大 |
这里有个容易忽略的点：TreeSet的自然排序模式下，null无法参与比较，会直接抛NullPointerException；而自定义Comparator可以自己决定怎么处理null，有些人故意写Comparator.nullsLast(...)来放行。HashSet则明确允许一个null，因为null的hash固定为0，只会落在一个固定位置。
5.2 真实环境下的性能对比思路
不谈数据量的性能结论都是耍流氓。我做过一次比较粗糙但能说明问题的实验：用100万条随机字符串，分别往三个Set里add和contains，记录耗时。三次运行取平均值后，结果规律的排序是：HashSet最快，LinkedHashSet微慢大约3%到5%，TreeSet明显慢了不少，add和contains都在HashSet的5倍左右耗时。
为什么TreeSet这么慢？一方面O(log n)和O(1)在百万数据下差别确实开始显现，每次树旋转、变色都有常数开销；另一方面，每插入一个对象都要做一次完整的比较链查找，而字符串比较本身有代价。这说明了什么？如果你的业务只是“去重+判存在”，HashSet就是数据量越大、优势越大的选择；而如果数据量只有几千条，三者差异小到可以忽略，这时候就该让业务需求决定选型，而不是被“性能差异”吓住。
写这类基准测试时有个小建议：别用IntelliJ IDEA里直接跑主函数读时间，JVM有预热和JIT编译的干扰。要么用JMH，要么至少先循环几十万次“热身”，再测目标操作，否则测出来的数字会偏差很大。
5.3 按场景选型的决策清单
结合上面的理论，我给自己整理了一个选型决策清单，闭着眼睛也能选：
- 只去重、不关心顺序：直接HashSet，最省事
- 去重但想保留第一次出现的顺序：LinkedHashSet，天然满足
- 去重后还要按键排序、或需要范围查询：TreeSet
- 元素是枚举，且量很小：用EnumSet，内部是位向量，省内存且极快
- 高并发环境，读远多于写：CopyOnWriteArraySet
- 高并发环境，高频写入且需要有序：ConcurrentSkipListSet，跳表实现，无锁读
最后两条可能有人不熟，简单说一句：CopyOnWriteArraySet底层是CopyOnWriteArrayList，每次写操作复制整个数组，所以只适合读多写极少；ConcurrentSkipListSet底层是跳表，插入删除不会像红黑树那样频繁旋转，并发度更好，而且天然有序。
6. 用Set踩过的坑：每一个都值得记下来
6.1 可变对象放进Set后改字段：contains瞬间失灵
这是我在业务代码里见过出现次数最多、也最难排查的一个坑。假设有一个User对象，id和age都参与hashCode，放进HashSet后某个逻辑改了age，下一次contains一个“字段完全一致”的新对象，返回的居然是false。
原因并不复杂：HashSet先算hashCode定位桶，age改掉后hashCode变了，新对象算出的桶位置和旧对象所在的桶位置不一样，equals还没来得及比较，就已经在“找桶”这一步岔开了。旧对象则还窝在原来的桶里，成了永远访问不到的元素。
解决手段就那么几种，按优先级说：优先把放进Set的对象设计成不可变类，字段一律final；如果做不到，就严格禁止在Set存续期间修改任何参与hashCode/equals的字段；再退一步，需要修改时必须先remove，改完再add。
6.2 眼睁睁看着remove失效的现场
和上一坑“同源”的是remove失效。你把集合里的某个对象拿出来改了字段，再想remove这个对象，发现remove返回false，元素还在集合里躺着。原因和contains一样：remove第一步也是按当前hashCode找桶，对象hash变了，自然找不到原来的位置。
更麻烦的是，这个“找不回来”的元素会一直留在HashSet里，造成真正意义上的内存泄漏——集合永远无法释放它。我遇到的一次线上内存增长事故，根因就是这个：一个全局缓存Set存放了一批任务对象，某个线程改了任务对象的属性字段，导致这些对象全部“沉底”，Set越涨越大，又没有remove机会，最终把堆撑爆。所以这条必须当成红线来执行：入Set对象的hashCode关键字段，进了集合就是只读的。
6.3 null、迭代时的并发问题
HashSet允许存一个null，TreeSet在自然排序模式下不允许null。这个差异在序列化、前端展示、数据库查询结果处理时容易被踩到。比如你从数据库查出一批可能为null的编号放进TreeSet，不判空直接add，运行时NPE当场就抛出来了，而且抛的位置离真正的null来源很远，排查要花不少时间。
另一个高频问题是迭代时修改。HashSet不是线程安全的，如果在for-each遍历过程中另一个线程执行了add，很可能抛出ConcurrentModificationException。理解机制比记结论更有用：这个异常来自modCount快速失败机制——迭代器生成时记录了一个修改计数，只要实际修改次数和记录不一致，迭代器立刻罢工，宁可抛异常也不给你“脏读”的机会。
线程安全方案有三档，按并发强度选择：轻度并发用Collections.synchronizedSet(new HashSet<>())简单包一层；读多写少用CopyOnWriteArraySet；并发强度高且有排序需求用ConcurrentSkipListSet。对绝大多数业务系统，第一档其实就够了，过度设计没必要。
6.4 初始容量调优：一个容易被忽略的内存细节
很多人new HashSet()一写就是默认容量，数据量小无所谓，但如果你要往里面塞几十万上百万元素，默认16的数组会因为反复扩容产生大量拷贝和rehash开销。前面提过期望数据量 / 负载因子 + 1的调整方法，这里再补充一个细节：真正的初始化容量会被HashMap内部的tableSizeFor向上取成2的幂。所以只要按公式算一个数，得到的结果够用且不会频繁扩容就行，不必精确到个位。
这个优化在TreeSet身上意义不大，因为红黑树是动态节点分配，不存在“扩容搬迁”的概念，硬塞一个巨大初始容量反而浪费。处理集合初始容量时，我的习惯是：先估算数据量级，再决定是否值得优化；只有超过10万条时才认真调，其余情况保持默认，代码可读性优先。
最后再分享一个小技巧
用Set这么多年，我最受益的一条经验是：写工具方法时多考虑“返回类型能不能是接口”。比如写一个去重方法，返回值声明为Set<String>，调用方后续想换成LinkedHashSet或TreeSet，完全不用改方法签名，只改内部一行实现。这样一来，HashSet和TreeSet之间的切换就变成了一行代码的事，选型的余地也就留住了。别小看这个习惯，线上出性能问题时，它往往能让你十分钟内完成结构替换，而不是熬夜重构一堆调用方代码。
