第15课：集合框架 - Set

🎯 学习目标

理解 Set 的去重原理（hashCode + equals 协定）
掌握 HashSet 的底层结构（数组 + 链表 + 红黑树）
理解 LinkedHashSet（插入顺序）、TreeSet（排序）的原理与选择
掌握自定义对象在 Set 中的正确使用（重写 hashCode/equals）
识别陷阱（hashCode/equals 不一致、可变对象作 key、TreeSet 自然排序）

📖 一、概念讲解：Set 的去重原理

1. Set 是什么

Set 是不允许重复元素的集合。核心问题是：怎么判断两个元素"相等"？

java

Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Apple");          // 重复，不会添加
System.out.println(set.size());   // 1

2. 去重靠 hashCode + equals 协定

HashSet 底层是 HashMap（元素作为 key，value 是占位对象）。判断"重复"分两步：

add(e) 流程：
1. 计算 e.hashCode() → 定位桶（数组下标 = hash & (n-1)）
2. 桶里没有元素 → 直接放入（新元素）
3. 桶里有元素 → 逐个用 equals 比较：
   a. 若有一个 equals 返回 true → 视为重复，不添加
   b. 全部 equals false → 加入桶（链表/红黑树）

关键认知：hashCode 是"快速预筛"——先用 hash 缩小到某个桶，再用 equals 精确比较。这就是为什么hashCode 和 equals 必须一致：两个 equals 相等的对象必须返回相同 hashCode，否则会被分到不同桶，导致"逻辑相同"的对象都存进去（去重失效）。

3. 底层数据结构演进

JDK 7：数组 + 链表（头插法）
JDK 8：数组 + 链表 + 红黑树
  - 桶里元素 ≥ 8 且数组长度 ≥ 64 → 链表转红黑树（查找 O(log n)）
  - 元素降到 ≤ 6 → 退回链表

为什么转红黑树？hash 碰撞严重时链表变长，查找退化为 O(n)。红黑树保证 O(log n)。但树节点占用更大内存，所以阈值 8 才转（泊松分布下随机 hash 碰撞到 8 的概率极低）。

📖 二、HashSet

java

Set<String> set = new HashSet<>();
set.add("Apple");
set.add("Banana");
set.add("Apple");                 // 重复不添加
System.out.println(set);            // [Apple, Banana]（无序）
System.out.println(set.size());    // 2
System.out.println(set.contains("Apple"));   // true，O(1)
set.remove("Banana");

性能：add/contains/remove 平均 O(1)（hash 计算 + 桶内少量比较）。最坏 O(log n)（转树后）。

📖 三、自定义对象的 Set 去重

必须同时重写 equals 和 hashCode，否则去重失效：

java

public class Person {
    String name;
    int age;

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Person p = (Person) o;
        return age == p.age && Objects.equals(name, p.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);   // 用参与 equals 的字段算 hash
    }
}

规则：hashCode 用到的字段必须是 equals 用到的字段的子集。即"equals 相等 → hashCode 必相等"。反方向不要求（hash 相等的对象可以不 equals，那是正常碰撞）。

📖 四、LinkedHashSet（插入顺序）

java

Set<String> set = new LinkedHashSet<>();
set.add("C"); set.add("A"); set.add("B");
System.out.println(set);   // [C, A, B]（保持插入顺序）

原理：在 HashMap 基础上额外维护一条双向链表记录插入顺序。遍历时按链表顺序。代价是多一条链表的内存。

另有 LinkedHashSet 的"访问顺序"模式（构造器传 true），但 Set 层面较少用（Map 的 LRU 缓存常用）。

📖 五、TreeSet（排序）

java

// 自然排序（元素须实现 Comparable）
Set<Integer> set = new TreeSet<>();
set.add(5); set.add(2); set.add(8);
System.out.println(set);   // [2, 5, 8]

// 定制排序
Set<String> desc = new TreeSet<>(Comparator.reverseOrder());
desc.add("Apple"); desc.add("Banana"); desc.add("Cherry");
System.out.println(desc);   // [Cherry, Banana, Apple]

// 范围查询（TreeSet 独有）
NavigableSet<Integer> ns = new TreeSet<>(Arrays.asList(1,3,5,7,9));
System.out.println(ns.headSet(5));   // [1,3]（<5）
System.out.println(ns.tailSet(5));   // [5,7,9]（>=5）
System.out.println(ns.subSet(3,7));  // [3,5]（[3,7)）

原理：底层红黑树（自平衡二叉搜索树）。add/remove/contains 均 O(log n)。元素必须 Comparable 或提供 Comparator。

📖 六、Set 应用

1. 去重

java

List<Integer> list = Arrays.asList(1, 2, 2, 3, 3, 3);
Set<Integer> set = new HashSet<>(list);   // [1, 2, 3]
// JDK 8+ 也可用 Stream distinct
list.stream().distinct().toList();

2. 集合运算

java

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> inter = new HashSet<>(a); inter.retainAll(b);    // 交集 [3,4]
Set<Integer> diff  = new HashSet<>(a); diff.removeAll(b);     // 差集 [1,2]

⚠️ 七、常见陷阱

陷阱1：只重写 equals 不重写 hashCode

java

class Person { /* 只重写 equals，不重写 hashCode */ }
Set<Person> set = new HashSet<>();
set.add(new Person("张三"));
set.add(new Person("张三"));   // 默认 hashCode 基于地址，两次 hash 不同 → 分到不同桶 → 都存进去
System.out.println(set.size());   // 2（去重失效！应为 1）

陷阱2：可变对象作 Set 元素（或 Map key）

java

Person p = new Person("张三", 20);
set.add(p);
p.setAge(30);    // 修改了参与 hashCode 的字段
set.contains(p);  // false！hash 变了，定位到别的桶，找不到
set.remove(p);    // 失败，内存泄漏

规避：作 Set 元素/Map key 的对象应为不可变，或至少不修改参与 hashCode 的字段。

陷阱3：TreeSet 元素类型不一致

java

Set<Object> set = new TreeSet<>();
set.add("A"); set.add(1);   // ClassCastException：String 与 Integer 不可比

TreeSet 排序依赖 Comparable/Comparator，类型必须一致。

陷阱4：HashSet 允许 null，TreeSet 不允许

java

Set<String> hs = new HashSet<>(); hs.add(null);   // ✅ 允许一个 null
Set<String> ts = new TreeSet<>(); ts.add(null);    // ❌ NPE（比较 null 抛异常）

陷阱5：以为 Set 有序

HashSet 无序，遍历顺序不保证。依赖顺序必须用 LinkedHashSet/TreeSet。

🆚 八、Java vs C 对比

特性	C 语言	Java
集合	无标准库，手写链表/数组	Set 体系丰富
去重	手动遍历比较 O(n)	HashSet O(1) 自动去重
哈希	手写哈希表	HashMap/HashSet 内置
排序集合	无	TreeSet 红黑树，自动排序+范围查询

对 C 程序员：Set 把 C 里"手动遍历去重"的 O(n) 操作降为 O(1)，且封装了哈希桶管理。但代价是要正确实现 hashCode/equals 协定——这是 C 程序员容易忽略的（C 没有这种约定）。

💡 九、最佳实践

默认 HashSet：最快，无序，允许 null。
需保留插入顺序 → LinkedHashSet（多一条链表的内存换顺序）。
需排序/范围查询 → TreeSet（O(log n)，元素须 Comparable）。
自定义对象务必同时重写 equals 和 hashCode，且字段一致。
作 Set 元素/Map key 的对象应不可变，避免修改字段导致定位失效。
集合运算用 JDK 方法：addAll/retainAll/removeAll，勿手写循环。

📝 练习预告

完成 练习/Ex15_Set.java 中的 6 道题：

HashSet 基本操作与去重
自定义对象去重（重写 hashCode/equals）
LinkedHashSet 保序
TreeSet 排序与范围查询
集合运算（并/交/差）
综合：用 Set 实现单词去重统计

完成后对比 答案/Sol15.java，查看逐行讲解与多解法。

📖 十、HashSet 的容量与扩容

HashSet 底层是 HashMap，因此容量和负载因子也来自 HashMap。

关键概念：

text

capacity：桶数组长度。
loadFactor：负载因子，默认 0.75。
threshold：扩容阈值，capacity * loadFactor。
size：当前元素数量。

当 size > threshold 时会扩容，通常扩大为原来的 2 倍。

为什么默认负载因子是 0.75？

text

负载因子太低：空间浪费，数组很空。
负载因子太高：冲突增多，链表或树更长。
0.75 是时间和空间之间的经验折中。

如果能预估元素数量，可以指定初始容量，减少扩容：

java

int expectedSize = 10_000;
int capacity = (int) (expectedSize / 0.75f) + 1;
Set<String> set = new HashSet<>(capacity);

扩容代价不小，因为所有元素都要重新分布到新桶中。

📖 十一、equals/hashCode 协定

Java 对象相等性有明确协定。

equals 要满足：

text

自反性：x.equals(x) 必须为 true。
对称性：x.equals(y) 与 y.equals(x) 结果一致。
传递性：x.equals(y)，y.equals(z)，则 x.equals(z)。
一致性：对象未变时，多次调用结果一致。
非空性：x.equals(null) 必须为 false。

hashCode 要满足：

text

equals 相等的对象，hashCode 必须相等。
hashCode 相等的对象，不要求 equals 相等。
对象未变时，hashCode 应保持一致。

推荐写法：

java

public final class UserKey {
    private final long tenantId;
    private final String username;

    public UserKey(long tenantId, String username) {
        this.tenantId = tenantId;
        this.username = username;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof UserKey other)) return false;
        return tenantId == other.tenantId && Objects.equals(username, other.username);
    }

    @Override
    public int hashCode() {
        return Objects.hash(tenantId, username);
    }
}

把 Set 元素设计成不可变对象，是避免后续定位失败的最稳方式。

🧪 十二、实战案例：标签去重并保持顺序

需求：用户提交标签列表，去重、去空、保持首次出现顺序。

java

public static List<String> normalizeTags(List<String> input) {
    Set<String> tags = new LinkedHashSet<>();
    for (String item : input) {
        if (item == null) {
            continue;
        }
        String tag = item.trim();
        if (!tag.isEmpty()) {
            tags.add(tag.toLowerCase(Locale.ROOT));
        }
    }
    return new ArrayList<>(tags);
}

为什么用 LinkedHashSet？

text

HashSet：能去重，但不保证顺序。
TreeSet：能去重和排序，但会改变用户输入顺序。
LinkedHashSet：去重，同时保留首次出现顺序。

这类场景在标签、权限、菜单、导入数据清洗中很常见。

📊 十三、Set 选型表

需求	推荐实现	原因
只要去重	`HashSet`	平均 O(1)，最常用
去重并保留插入顺序	`LinkedHashSet`	双向链表记录顺序
去重并排序	`TreeSet`	红黑树维护排序
并发读写	`ConcurrentHashMap.newKeySet()`	并发安全
枚举值集合	`EnumSet`	位向量实现，极高效
小规模不可变集合	`Set.of(...)`	简洁，不可变

EnumSet 示例：

java

enum Role { ADMIN, USER, AUDITOR }

Set<Role> roles = EnumSet.of(Role.ADMIN, Role.USER);

如果元素类型是枚举，EnumSet 通常比 HashSet 更快、更省内存。

🛠 十四、Set 排查清单

当 Set 行为不符合预期时，按下面检查：

text

是否重写了 equals。
是否同时重写了 hashCode。
equals 和 hashCode 使用的字段是否一致。
元素加入 Set 后是否修改了关键字段。
是否误以为 HashSet 有遍历顺序。
TreeSet 的 Comparator 是否与 equals 一致。
是否把 null 放进不允许 null 的实现。
并发环境是否使用了非线程安全 Set。

TreeSet 还有一个特殊点：

text

TreeSet 判断重复依赖 compareTo/Comparator 返回 0。
HashSet 判断重复依赖 equals。

如果 Comparator 只比较年龄：

java

new TreeSet<>(Comparator.comparingInt(Person::getAge));

那么两个同年龄的人会被 TreeSet 认为“重复”，即使姓名不同。

✅ 十五、掌握标准

学完本课后，应能做到：

text

能解释 Set 为什么能去重。
能说清 HashSet 与 HashMap 的关系。
能正确实现 equals 和 hashCode。
能解释可变对象作为 Set 元素的风险。
能根据顺序、排序、并发需求选择 Set 实现。
能使用 addAll、retainAll、removeAll 做集合运算。
能识别 TreeSet Comparator 与 equals 不一致的问题。
能在标签去重、权限集合、枚举集合中选择合适实现。

Set 的难点不是 API，而是“相等性定义”。一旦相等性定义错，去重、查找、删除都会出问题。

🎓 下一步

第16课：集合框架 - Map — HashMap 底层、扩容、ConcurrentHashMap

第15课：集合框架 - Set ​

🎯 学习目标 ​

📖 一、概念讲解：Set 的去重原理 ​

1. Set 是什么 ​

2. 去重靠 hashCode + equals 协定 ​

3. 底层数据结构演进 ​

📖 二、HashSet ​

📖 三、自定义对象的 Set 去重 ​

📖 四、LinkedHashSet（插入顺序） ​

📖 五、TreeSet（排序） ​

📖 六、Set 应用 ​

1. 去重 ​

2. 集合运算 ​

⚠️ 七、常见陷阱 ​

陷阱1：只重写 equals 不重写 hashCode ​

陷阱2：可变对象作 Set 元素（或 Map key） ​

陷阱3：TreeSet 元素类型不一致 ​

陷阱4：HashSet 允许 null，TreeSet 不允许 ​

陷阱5：以为 Set 有序 ​

🆚 八、Java vs C 对比 ​

💡 九、最佳实践 ​

📝 练习预告 ​

📖 十、HashSet 的容量与扩容 ​

📖 十一、equals/hashCode 协定 ​

🧪 十二、实战案例：标签去重并保持顺序 ​

📊 十三、Set 选型表 ​

🛠 十四、Set 排查清单 ​

✅ 十五、掌握标准 ​

🎓 下一步 ​

第15课：集合框架 - Set

🎯 学习目标

📖 一、概念讲解：Set 的去重原理

1. Set 是什么

2. 去重靠 hashCode + equals 协定

3. 底层数据结构演进

📖 二、HashSet

📖 三、自定义对象的 Set 去重

📖 四、LinkedHashSet（插入顺序）

📖 五、TreeSet（排序）

📖 六、Set 应用

1. 去重

2. 集合运算

⚠️ 七、常见陷阱

陷阱1：只重写 equals 不重写 hashCode

陷阱2：可变对象作 Set 元素（或 Map key）

陷阱3：TreeSet 元素类型不一致

陷阱4：HashSet 允许 null，TreeSet 不允许

陷阱5：以为 Set 有序

🆚 八、Java vs C 对比

💡 九、最佳实践

📝 练习预告

📖 十、HashSet 的容量与扩容

📖 十一、equals/hashCode 协定

🧪 十二、实战案例：标签去重并保持顺序

📊 十三、Set 选型表

🛠 十四、Set 排查清单

✅ 十五、掌握标准

🎓 下一步