一、整体架构图Set (接口) ├── HashSet │ └── LinkedHashSet ├── TreeSet ├── CopyOnWriteArraySet └── ConcurrentSkipListSet └── (Java 6)二、详解1. HashSetHashSet 就是披着 Set 外衣的 HashMap——它把所有元素当作 HashMap 的 Key用一个固定的空对象占住 Value 位借助哈希表的 O(1) 查找实现快速去重。元素必须正确重写 hashCode() 和 equals()否则去重逻辑会失效。定位最基础、最常用的去重集合追求极致速度。项目内容底层HashMapE, Object有序性❌ 完全无序迭代顺序不可预测null 支持✅ 允许一个null线程安全❌ 非线程安全时间复杂度O(1) — add/remove/contains空间开销较小仅存储 Key 一个固定空对象核心源码publicclassHashSetEextendsAbstractSetEimplementsSetE{privatetransientHashMapE,Objectmap;privatestaticfinalObjectPRESENTnewObject();// 所有 Value 都是它publicbooleanadd(Ee){returnmap.put(e,PRESENT)null;// 返回 null 说明是新增}}本质HashSet HashMap 的 Key 集合。去重原理hashCode() 定位桶 → equals() 比较桶内元素 → 相同则覆盖不同则链入。1. 计算 hashCode() → 定位桶位置 2. 桶内无元素 → 直接插入 3. 桶内有元素 → 用 equals() 逐个比较 - equals 返回 true → 认为是重复不插入返回旧值 - 全部不相等 → 链入桶内JDK8 可能转红黑树所以元素必须正确重写 hashCode() 和 equals()否则去重失效。扩容机制完全继承 HashMap 的规则默认初始容量16负载因子0.75扩容时机元素数 容量 × 0.75扩容方式容量翻倍所有元素 rehash 重新分布2. LinkedHashSet定位HashSet 的有序升级版保留插入顺序。项目内容底层LinkedHashMapE, Object有序性✅插入有序按添加顺序迭代null 支持✅ 允许一个null线程安全❌ 非线程安全时间复杂度O(1)空间开销略大于 HashSet额外维护双向链表核心机制在 HashMap 的每个节点上额外挂了两个指针 before / after形成一条按插入顺序链接的双向链表。// LinkedHashMap.Entry 继承 HashMap.Node多了两个指针staticclassEntryK,VextendsHashMap.NodeK,V{EntryK,Vbefore,after;// 双向链表指针}迭代时遍历这条双向链表而非哈希桶数组因此顺序稳定。适用场景需要按添加顺序去重如配置项加载、历史记录去重。3. TreeSet定位有序集合元素自动排序支持范围查询。项目内容底层TreeMapE, Object红黑树有序性✅自然排序或自定义比较器排序null 支持❌ 不允许null无法比较线程安全❌ 非线程安全时间复杂度O(log n) — add/remove/contains空间开销较大每个节点存左右子树指针、颜色标记核心机制publicclassTreeSetEextendsAbstractSetEimplementsNavigableSetE{privatetransientNavigableMapE,Objectm;publicbooleanadd(Ee){returnm.put(e,PRESENT)null;}}底层是红黑树自平衡二叉搜索树元素按比较规则排列元素实现 Comparable 接口自然排序或构造时传入 Comparator自定义排序特有 APIElower(Ee);// 严格小于 e 的最大元素Efloor(Ee);// 小于等于 e 的最大元素Eceiling(Ee);// 大于等于 e 的最小元素Ehigher(Ee);// 严格大于 e 的最小元素SortedSetEsubSet(Efrom,Eto);// 范围子集适用场景需要排序、范围查询、排行榜、区间检索。4. CopyOnWriteArraySet定位线程安全的读多写少集合写操作复制整个数组。项目内容底层CopyOnWriteArrayListE数组有序性✅ 插入有序按数组索引null 支持✅ 允许null线程安全✅ 线程安全写时复制时间复杂度读 O(1)写 O(n)空间开销写操作时翻倍复制新数组核心机制publicclassCopyOnWriteArraySetEextendsAbstractSetE{privatefinalCopyOnWriteArrayListEal;publicbooleanadd(Ee){returnal.addIfAbsent(e);// 先遍历检查是否存在不存在则复制数组添加}}写时复制COW读操作直接读当前数组无锁极快写操作加锁 → 复制新数组 → 修改新数组 → 替换引用注意add() 时先用 indexOf 遍历检查是否已存在O(n)再复制数组插入。所以去重效率不高数据量大时慎用。适用场景事件监听器列表、配置项集合——读极多、写极少、遍历频繁。5. ConcurrentSkipListSet定位线程安全的有序集合高并发下的 TreeSet 替代品项目内容底层ConcurrentSkipListMapE, Object跳表有序性✅ 自然排序或自定义排序null 支持❌ 不允许null线程安全✅ 线程安全CAS 细粒度锁时间复杂度O(log n)空间开销较大跳表多层索引核心机制底层是 **跳表**Skip List——一种用概率平衡替代严格旋转的平衡数据结构Level 3: 1 ------------------------- 9 Level 2: 1 --------- 5 --------- 9 Level 1: 1 - 3 - 5 - 7 - 9无锁读CAS 写并发性能优于 TreeSet synchronized支持 NavigableSet 全部范围查询 API适用场景高并发下需要排序、范围查询替代 Collections.synchronizedSortedSet(new TreeSet())。三、对比总表特性HashSetLinkedHashSetTreeSetCopyOnWriteArraySetConcurrentSkipListSet底层结构HashMapLinkedHashMapTreeMap(红黑树)CopyOnWriteArrayList(数组)ConcurrentSkipListMap(跳表)有序性❌ 无序✅ 插入有序✅ 排序有序✅ 插入有序✅ 排序有序null 元素✅ 1个✅ 1个❌ 不允许✅ 允许❌ 不允许线程安全❌❌❌✅ COW✅ CASadd 复杂度O(1)O(1)O(log n)O(n)O(log n)contains 复杂度O(1)O(1)O(log n)O(n)O(log n)遍历性能与容量相关与容量相关与元素数相关极快快照与元素数相关内存开销小中双向链表大树节点写时翻倍大多层索引迭代器fail-fastfail-fastfail-fast快照弱一致弱一致比较依据hashCodeequalshashCodeequalsComparable/ComparatorequalsComparable/Comparator四、原理深度对比集合去重方式关键点HashSethashCode()→ 桶定位 →equals()比较哈希冲突用链表/红黑树解决LinkedHashSet同 HashSet额外维护插入顺序链表不影响去重TreeSetcompareTo()/compare()比较比较结果为 0 即视为重复CopyOnWriteArraySetequals()遍历数组查找线性扫描效率低ConcurrentSkipListSet跳表索引定位 →compareTo()比较CAS 保证并发安全重要陷阱TreeSet 的 “相等” 陷阱TreeSetPersonsetnewTreeSet((a,b)-a.age-b.age);// 如果两个人 age 相同compare 返回 0TreeSet 认为它们是同一个元素// 即使 name 不同第二个也会被去重掉CopyOnWriteArraySet 的性能陷阱// 每次 add 都要 O(n) 扫描 数组复制数据量大时极慢CopyOnWriteArraySetIntegersetnewCopyOnWriteArraySet();for(inti0;i10000;i){set.add(i);// 越来越慢}五、选择决策树需要线程安全 ├── 是 │ ├── 需要排序/范围查询 → ConcurrentSkipListSet │ └── 读多写少、数据量小 → CopyOnWriteArraySet └── 否 ├── 需要排序/范围查询 → TreeSet ├── 需要保留插入顺序 → LinkedHashSet └── 只追求最快去重 → HashSet六、总结集合一句话HashSet最快的去重桶无序O(1)LinkedHashSet有记忆的去重桶记住你来过的顺序TreeSet会自动排队的去重桶支持第几名到第几名CopyOnWriteArraySet写一次复制全班的去重桶读飞快、写巨慢ConcurrentSkipListSet多人同时排队的去重桶并发安全还能查排名
