Set

ℹ️定位说明

本篇是 Set 系列总览：一图两表建立"三实现怎么选"的认知，再补集合运算与去重实操。三个实现的深读：无序之选 HashSet、保序之选 LinkedHashSet、排序之选 TreeSet。

Set 是 Java 集合框架中的核心接口，继承自 Collection 接口，主要用于存储 唯一元素，其核心特点如下：

唯一性约束
- 不允许存储重复元素，重复元素的判定基于 equals() 和 hashCode() 方法（需二者一致）。
- 若自定义对象存入 Set，需重写 equals() 和 hashCode() 以保证唯一性逻辑正确。
无索引访问
- 不支持通过索引（如 get(index)）直接访问元素，元素顺序由具体实现类决定。
- 遍历元素通常使用 Iterator 或增强型 for 循环。
适用场景
- 数据去重（如过滤重复数据）。
- 存储需要唯一性的数据集（如用户唯一标识、权限集合）。

核心实现类对比

实现类	数据结构	元素顺序	线程安全	性能特点	典型场景
HashSet	哈希表（HashMap 底层）	无序（元素插入顺序可能被打乱）	非线程安全	插入、删除、查询平均时间复杂度为 O(1)，依赖哈希算法	快速去重、无需顺序的唯一性存储
LinkedHashSet	哈希表 + 双向链表	按插入顺序保持有序	非线程安全	插入、删除稍慢于 `HashSet`，但遍历时按顺序访问	需要保留插入顺序的去重场景
TreeSet	红黑树（NavigableSet 实现）	按自然顺序（`Comparable`）或定制顺序排序	非线程安全	插入、删除、查询时间复杂度为 O(log n)，支持范围查询	排序需求明确的唯一性数据（如排行榜、区间数据）

对比维度	HashSet	LinkedHashSet	TreeSet
底层实现	基于 HashMap（哈希表 + 链地址法）	基于 LinkedHashMap（哈希表 + 双向链表）	基于 TreeMap（红黑树）
数据顺序	完全无序	插入顺序（默认）或访问顺序（需配置）	自然排序（Comparable）或定制排序（Comparator）
允许 null 元素	✅ 允许 1 个 null	✅ 允许 1 个 null	❌ 禁止（比较逻辑无法处理 null）
时间复杂度	插入/删除/查找：平均 O(1)，最坏 O(n) 或 O(log n)（树化后）	同 HashSet，但链表操作增加微小开销	插入/删除/查找：O(log n)
内存占用	最低（仅哈希表）	较高（额外维护双向链表指针）	最高（树节点存储父子指针和颜色标记）
线程安全	❌ 不安全	❌ 不安全	❌ 不安全
去重依据	hashCode() + equals()	同 HashSet	compareTo() 或 Comparator.compare()（比较结果为 0 视为重复）
主要优势	最高效的随机访问	保留插入顺序，遍历性能更优	自动排序，支持范围查询
主要劣势	无序，无法预测迭代顺序	内存开销略高	性能低于哈希表，不支持 null
扩容机制	默认 2 倍扩容，负载因子 0.75	同 HashSet	无扩容概念（动态调整树结构）
典型使用场景	快速去重、存在性检查、集合运算	保留插入顺序的去重（如操作日志） LRU 缓存实现	排序集合（如排行榜）范围查询（如成绩区间筛选）

关键特性补充

线程安全
- 所有 Set 实现类默认非线程安全，多线程环境下需手动同步（如使用 Collections.synchronizedSet() 包装）或选择并发容器（如 ConcurrentSkipListSet）。
性能差异
- HashSet 是最常用的实现类，性能高效且适用于大多数场景。
- TreeSet 因排序特性，适用于需要元素有序的场景，但性能略低于 HashSet。
- LinkedHashSet 兼顾插入顺序和哈希表性能，适合需要有序遍历的去重场景。

与 List 的核心区别

维度	Set	List
元素重复性	不允许重复（唯一性）	允许重复
索引支持	不支持（无 `get(index)`）	支持（通过索引访问）
典型场景	去重、唯一性校验	有序数据存储、频繁索引访问

最佳实践建议

优先选择 HashSet：若无顺序或排序需求，HashSet 是性能最优的选择。
需要顺序时选 LinkedHashSet：如需要保留元素插入顺序（如日志记录去重）。
排序场景用 TreeSet：元素需按自然顺序或定制规则排序时（如数值大小、字母顺序）。
多线程环境：使用 Collections.synchronizedSet(new HashSet<>()) 或并发集合（如 ConcurrentHashMap 的键集合）保证线程安全。

上手示例：去重与集合运算

// 1. 一行去重（List → Set）
List<String> words = Arrays.asList("apple", "pear", "apple", "banana", "pear");
Set<String> distinct = new HashSet<>(words);
System.out.println(distinct);            // [banana, pear, apple]（顺序不保证）

// 2. 保序去重：LinkedHashSet 既去重又记住先后
Set<String> ordered = new LinkedHashSet<>(words);
System.out.println(ordered);             // [apple, pear, banana]

// 3. 集合运算（数学课那套：交/并/差）
Set<Integer> a = new HashSet<>(Arrays.asList(1, 2, 3, 4));
Set<Integer> b = new HashSet<>(Arrays.asList(3, 4, 5, 6));

Set<Integer> union = new HashSet<>(a);
union.addAll(b);                          // 并集 [1, 2, 3, 4, 5, 6]

Set<Integer> intersect = new HashSet<>(a);
intersect.retainAll(b);                   // 交集 [3, 4]

Set<Integer> diff = new HashSet<>(a);
diff.removeAll(b);                        // 差集 [1, 2]

// 4. 排序去重：TreeSet 自动排好
Set<Integer> sorted = new TreeSet<>(Arrays.asList(5, 1, 3, 1, 5));
System.out.println(sorted);               // [1, 3, 5]

⚠️`retainAll`/`removeAll` 是"就地修改"

它们改的是调用者本身，返回值只是 boolean（是否发生变化）——想让 a.retainAll(b) 的结果不影响 a，必须先拷贝一份（上面示例就是这么写的）。直接 a.retainAll(b) 后 a 就变交远了，这是新手高频翻车点。

通过合理选择 Set 实现类，可以高效解决数据唯一性和存储需求。

⬅️ Vector 🏠 00-Java ➡️ HashSet

00-Set总览

Set