【集合框架Set接口】

👉 想存一堆用户，但发现有重复的？
👉 用 Set 去重，但结果顺序乱了？
👉 面试官问：“HashSet 和 TreeSet 有什么区别？” 你只会说“一个无序一个有序”？

一、Set 是什么？—— 无序不可重复的“集合”

🎯 核心特点

• 无序（Unordered）：不保证元素的插入顺序（某些实现如 LinkedHashSet 除外）
• 不允许重复：每个元素在集合中最多出现一次
• 基于 equals() 和 hashCode() 判断重复

✅ 典型场景：

• 用户去重
• 标签集合
• 权限集合

🖼️ 图示：Set 的逻辑结构

+——–+ +——–+ +——–+
| Apple | | Banana | | Orange |
+——–+ +——–+ +——–+

✅ 核心操作：

• 添加元素：add(E e) —— 如果元素已存在，返回 false
• 删除元素：remove(Object o)
• 判断是否包含：contains(Object o)

二、Set 的核心实现类

1. HashSet —— 基于“哈希表”的实现（最常用）

🎯 核心特性

• 底层是 HashMap：元素作为 HashMap 的 key 存储
• 添加、删除、查找极快：平均时间复杂度 O(1)
• 不保证顺序
• 允许一个 null 值

Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple"); // 重复，添加失败，返回 false
System.out.println(set.size()); // 输出 2

🔍 去重原理详解

// HashSet 内部持有一个 HashMap
private transient HashMap<E,Object> map;

// add 方法本质是 put 到 HashMap 的 key
public boolean add(E e) {
return map.put(e, PRESENT) == null;
}

✅ PRESENT 是一个静态常量，所有 key 共享同一个 value。

🖼️ 图示：HashSet 的底层结构

HashSet
|
v
HashMap
+—————–+
| key: "Apple" | -> value: PRESENT (常量)
+—————–+
| key: "Banana" | -> value: PRESENT
+—————–+
| key: "Orange" | -> value: PRESENT
+—————–+

✅ 去重依赖 hashCode() 和 equals()：

❌ 经典误区：自定义对象未重写 hashCode() 和 equals()

class User {
String name;
int age;
// 未重写 hashCode 和 equals
}

Set<User> users = new HashSet<>();
users.add(new User("Alice", 25));
users.add(new User("Alice", 25)); // 被认为是两个不同的对象！

✅ 正确做法：重写 hashCode() 和 equals()，确保逻辑相等的对象哈希值也相等。

2. LinkedHashSet —— HashSet + 双向链表（维护插入顺序）

🎯 核心特性

• 继承 HashSet，在 HashMap 基础上增加双向链表
• 维护插入顺序
• 性能接近 HashSet，但内存稍大（维护链表）

Set<String> set = new LinkedHashSet<>();
set.add("C");
set.add("A");
set.add("B");
System.out.println(set); // 输出 [C, A, B]（有序！）

🖼️ 图示：LinkedHashSet 的底层结构

LinkedHashSet
|
v
LinkedHashMap (继承 HashMap)
+—————–+
| key: "C" | -> value: PRESENT
| (linked to A) |
+—————–+
| key: "A" | -> value: PRESENT
| (linked to B) |
+—————–+
| key: "B" | -> value: PRESENT
| (linked to null)|
+—————–+

双向链表：C <-> A <-> B

✅ 适用场景：需要去重且保持插入顺序，如最近访问记录、配置项。

3. TreeSet —— 基于“红黑树”的实现（自动排序）

🎯 核心特性

• 底层是 TreeMap：基于红黑树（Red-Black Tree）
• 元素自动排序：自然序（Comparable）或自定义比较器（Comparator）
• 不允许 null 值（因为比较时会抛出 NullPointerException）
• 性能 O(log n)，比 HashSet 慢

Set<Integer> set = new TreeSet<>();
set.add(3);
set.add(1);
set.add(2);
System.out.println(set); // 输出 [1, 2, 3]（有序！）

🖼️ 图示：TreeSet 的底层结构（红黑树）

(2)
/ \\
(1) (3)
/ \\ / \\
null null null null

✅ 排序规则：

• 自然序：实现 Comparable 接口
• 自定义序：传入 Comparator

// 自定义比较器：按字符串长度排序
Set<String> set = new TreeSet<>((a, b) -> a.length() – b.length());
set.add("hi");
set.add("hello");
set.add("a");
System.out.println(set); // 输出 [a, hi, hello]

✅ 适用场景：需要排序的去重集合，如排行榜、优先队列、范围查询。

三、Set 的常用方法详解

1. 添加元素

boolean added = set.add("Apple"); // 成功返回 true，重复返回 false

2. 删除元素

boolean removed = set.remove("Apple"); // 成功返回 true，不存在返回 false

3. 判断是否包含

boolean contains = set.contains("Apple");

4. 集合操作（交集、并集、差集）

Set<String> set1 = new HashSet<>(Arrays.asList("A", "B", "C"));
Set<String> set2 = new HashSet<>(Arrays.asList("B", "C", "D"));

// 并集：set1 ∪ set2
Set<String> union = new HashSet<>(set1);
union.addAll(set2); // [A, B, C, D]

// 交集：set1 ∩ set2
Set<String> intersection = new HashSet<>(set1);
intersection.retainAll(set2); // [B, C]

// 差集：set1 – set2
Set<String> difference = new HashSet<>(set1);
difference.removeAll(set2); // [A]

四、高频问题 & 高分回答

Q1: HashSet 的去重原理是什么？

答：
HashSet 内部持有一个 HashMap，元素作为 HashMap 的 key 存储。
利用 HashMap 的 key 不可重复的特性来保证 HashSet 的唯一性。
add(e) 本质是 map.put(e, PRESENT)，PRESENT 是一个静态常量。

Q2: 为什么 TreeSet 不允许 null 值？

答：
因为 TreeSet 需要对元素进行比较排序。
当插入 null 时，会调用 compareTo() 方法，导致 NullPointerException。
即使第一个元素是 null，后续插入非 null 元素时也会尝试与 null 比较，同样会抛出异常。

Q3: LinkedHashSet 如何维护插入顺序？

答：
LinkedHashSet 继承自 HashSet，底层使用 LinkedHashMap。
LinkedHashMap 在 HashMap 的基础上，增加了一条双向链表，
将所有节点按照插入顺序串联起来，从而维护了插入顺序。

Q4: HashSet 和 TreeSet 如何选择？

答：

• HashSet：追求极致性能，不关心顺序，允许 null；
• TreeSet：需要自动排序，支持范围查询，不允许 null。
  一般情况下优先选 HashSet，只有需要排序时才用 TreeSet。

五、总结：一张表搞懂 Set 的选型

🔚 最后一句话

Set 接口是 Java 集合框架中“去重”功能的基石。
从 HashSet 的哈希表，到 TreeSet 的红黑树，
每一个实现都体现了对时间复杂度、空间复杂度、排序需求的权衡。
只有当你真正理解了 hashCode() 和 equals() 的契约，
以及红黑树的自平衡原理，
你才能写出高效、正确、专业的去重逻辑！

希望这篇能帮你彻底搞懂 Set 接口及其常见实现！