Java 中 Set 集合

一、Set 集合基础：核心特点（入门）

Set 是 Java 集合框架（Collection）的子接口，它的核心定位是存储不重复的元素，这是和 List 最核心的区别。

1. 核心特点

2. 常用子实现类

日常开发中，Set 最常用的三个实现类是：

• HashSet：最常用，基于哈希表实现，无序、查询效率高
• LinkedHashSet：HashSet 的子类，基于哈希表 + 链表，保证元素的插入顺序
• TreeSet：基于红黑树实现，能对元素进行自然排序或自定义排序

二、Set 核心实现类的底层原理（进阶）

1. HashSet（最核心）

（1）底层结构

JDK 8 及以后，HashSet 的底层是HashMap（之前是 HashMap + 链表），更具体地说：

• HashSet 内部维护一个 HashMap 对象，把自己要存储的元素作为 HashMap 的key
• HashMap 的 value 是一个固定的空对象（PRESENT），仅作为占位符

（2）去重原理（核心）

HashSet 判断元素是否重复，依赖两个方法：

1. hashCode()：先计算元素的哈希值，确定元素在哈希表中的 “桶位置”
2. equals()：如果哈希值相同，再通过 equals 方法判断元素是否真的相等

graph TD A[添加元素e] --> B[计算e的hashCode()] B --> C{哈希值是否已存在?} C -->|否| D[直接存入哈希表] C -->|是| E[调用equals()比较已有元素和e] E -->|相等| F[不存入，去重成功] E -->|不相等| G[存入（哈希冲突，用链表/红黑树存储）]

2. LinkedHashSet

• 底层是LinkedHashMap（HashMap 的子类）
• 相比 HashSet，多了一个双向链表维护元素的插入顺序，因此遍历顺序和插入顺序一致
• 去重原理和 HashSet 完全相同，只是多了顺序保证，性能略低于 HashSet

3. TreeSet

• 底层是TreeMap，基于红黑树（一种自平衡的二叉查找树）实现
• 核心特点：有序（自然排序，如数字升序、字符串字典序；或自定义排序）
• 去重原理：不依赖 hashCode 和 equals，而是依赖比较规则（Comparable/Comparator）：
  • 如果元素实现了Comparable接口，调用compareTo()方法，返回 0 则认为元素重复
  • 如果自定义了Comparator比较器，调用compare()方法，返回 0 则认为元素重复
• 注意：TreeSet 存储的元素必须是 “可比较的”，否则会抛出ClassCastException

三、自定义对象去重（实战重点）

日常开发中，我们经常需要存储自定义对象（如 User、Student）到 Set 中并实现去重，这是 Set 最核心的实战场景，分两种情况讲解：

场景 1：HashSet/LinkedHashSet 存储自定义对象去重

核心要求：必须重写自定义对象的hashCode()和equals()方法。

示例：Student 类（按学号去重）

import java.util.HashSet; import java.util.Objects; // 自定义学生类 class Student { private String id; // 学号（唯一标识） private String name; private int age; // 构造方法 public Student(String id, String name, int age) { this.id = id; this.name = name; this.age = age; } // 重写equals：只要学号相同，就认为是同一个学生 @Override public boolean equals(Object o) { if (this == o) return true; // 引用相同，直接相等 if (o == null || getClass() != o.getClass()) return false; // 类型不同，不相等 Student student = (Student) o; return Objects.equals(id, student.id); // 仅比较学号 } // 重写hashCode：基于学号生成哈希值（保证equals相等的对象，hashCode一定相等） @Override public int hashCode() { return Objects.hash(id); } // 重写toString，方便打印查看 @Override public String toString() { return "Student{id='" + id + "', name='" + name + "', age=" + age + "}"; } } // 测试类 public class HashSetCustomObjectTest { public static void main(String[] args) { HashSet<Student> studentSet = new HashSet<>(); // 添加3个学生，其中两个学号相同（应该去重） studentSet.add(new Student("001", "张三", 20)); studentSet.add(new Student("002", "李四", 21)); studentSet.add(new Student("001", "张三三", 20)); // 学号和第一个相同，应被去重 // 遍历输出：只会打印2个学生（001和002） for (Student s : studentSet) { System.out.println(s); } } }

关键说明：

• 重写equals的规则：你认为哪些字段相同就代表对象重复，就比较哪些字段（示例中只比较学号）。
• 重写hashCode的原则：
  1. equals 相等的对象，hashCode 必须相等（示例中都基于 id 生成，保证这一点）；
  2. hashCode 相等的对象，equals 不一定相等（哈希冲突）。
• IDE（如 IDEA）可以自动生成 equals 和 hashCode，建议直接用自动生成的（快捷键：Alt + Insert）。

场景 2：TreeSet 存储自定义对象去重

有两种实现方式：实现 Comparable 接口（推荐）、自定义 Comparator 比较器。

方式 1：实现 Comparable 接口

import java.util.TreeSet; // 学生类实现Comparable接口，指定比较规则 class Student implements Comparable<Student> { private String id; private String name; private int age; public Student(String id, String name, int age) { this.id = id; this.name = name; this.age = age; } // 重写compareTo：按学号比较，返回0则去重 @Override public int compareTo(Student o) { // 按学号字典序比较 return this.id.compareTo(o.id); // 如果想多字段比较：先按学号，再按年龄 // int idCompare = this.id.compareTo(o.id); // return idCompare != 0 ? idCompare : Integer.compare(this.age, o.age); } @Override public String toString() { return "Student{id='" + id + "', name='" + name + "', age=" + age + "}"; } } // 测试类 public class TreeSetCustomObjectTest1 { public static void main(String[] args) { TreeSet<Student> studentSet = new TreeSet<>(); studentSet.add(new Student("001", "张三", 20)); studentSet.add(new Student("002", "李四", 21)); studentSet.add(new Student("001", "张三三", 20)); // 学号相同，被去重 // 遍历输出：有序（按学号字典序），且只有2个元素 for (Student s : studentSet) { System.out.println(s); } } }

方式 2：自定义 Comparator 比较器（灵活，不修改原类）

import java.util.Comparator; import java.util.TreeSet; // 学生类（不实现Comparable） class Student { private String id; private String name; private int age; public Student(String id, String name, int age) { this.id = id; this.name = name; this.age = age; } @Override public String toString() { return "Student{id='" + id + "', name='" + name + "', age=" + age + "}"; } // getter方法（比较器需要获取字段） public String getId() { return id; } } // 测试类：用Comparator自定义比较规则 public class TreeSetCustomObjectTest2 { public static void main(String[] args) { // 创建TreeSet时传入Comparator，指定按学号比较 TreeSet<Student> studentSet = new TreeSet<>(new Comparator<Student>() { @Override public int compare(Student s1, Student s2) { return s1.getId().compareTo(s2.getId()); } }); studentSet.add(new Student("001", "张三", 20)); studentSet.add(new Student("002", "李四", 21)); studentSet.add(new Student("001", "张三三", 20)); // 去重 for (Student s : studentSet) { System.out.println(s); } } }

四、进阶注意点

1. HashSet 性能：
   • 增删改查的平均时间复杂度是 O (1)，哈希冲突严重时会退化为 O (n)（链表）或 O (logn)（红黑树）。
   • 尽量让 hashCode 分布均匀，减少哈希冲突（IDE 自动生成的 hashCode 已优化）。
2. TreeSet 性能：
   • 增删改查的时间复杂度是 O (logn)，比 HashSet 略慢，但胜在有序。
3. 不可变对象：
   • 存储到 Set 中的对象如果是可变的（比如修改了用于比较的字段），可能导致去重失效。
   • 示例：把 Student 对象存入 HashSet 后，修改其 id 字段，会导致后续无法正确识别该对象，甚至出现重复元素。

总结

1. 核心特点：Set 集合的核心是元素不重复，无索引，HashSet 无序、LinkedHashSet 保证插入顺序、TreeSet 保证排序顺序。
2. 去重原理：HashSet/LinkedHashSet 依赖hashCode()+equals()，TreeSet 依赖Comparable/Comparator的比较规则（返回 0 则去重）。
3. 自定义对象去重：用 HashSet 需重写hashCode()和equals()，用 TreeSet 需实现Comparable或传入Comparator，且比较规则要和 “去重逻辑” 一致。

HashSet的底层结构

一、HashSet 底层的 “本质”：基于 HashMap 封装

首先要明确一个核心结论：HashSet 本身没有独立的底层结构，它是对 HashMap 的 “轻量封装”。

• HashSet 内部会维护一个HashMap类型的成员变量（源码中叫map）。
• 当你向 HashSet 中添加元素时，实际上是把这个元素作为HashMap 的 key存入，而 HashMap 的 value 是一个固定的、静态的空对象（PRESENT，类型为Object），仅作为占位符使用（因为 HashMap 必须有 key-value 对，而 HashSet 只需要 key）。

源码佐证（JDK 8）：

public class HashSet<E> extends AbstractSet<E> implements Set<E>, Cloneable, java.io.Serializable { // 核心：HashSet 内部的 HashMap private transient HashMap<E,Object> map; // 固定的占位符 value private static final Object PRESENT = new Object(); // HashSet 的无参构造器 → 本质是创建一个空的 HashMap public HashSet() { map = new HashMap<>(); } // HashSet 的 add 方法 → 本质是调用 HashMap 的 put 方法 public boolean add(E e) { return map.put(e, PRESENT)==null; } // HashSet 的 remove 方法 → 本质是调用 HashMap 的 remove 方法 public boolean remove(Object o) { return map.remove(o)==PRESENT; } }

从源码能直接看出：HashSet 的所有核心操作（add/remove/contains 等），都是通过调用 HashMap 的对应方法实现的，它只是一个 “只使用 key 的 HashMap 包装器”。

总结

1. 核心本质：HashSet 没有独立底层结构，是对 HashMap 的封装，元素存储为 HashMap 的 key，value 是固定空对象。
2. 底层依赖：HashMap 的 “数组 + 链表 + 红黑树” 结构，数组是主容器，链表解决哈希冲突，红黑树优化高频冲突场景。
3. 存储流程：计算元素哈希值→确定桶位置→通过 hashCode ()+equals () 判重→存入 / 扩容，这也是 HashSet 去重的底层逻辑。

补充：HashSet 中 “元素唯一性”

一、先拆解两个 “相等” 分别对应什么

1. 哈希值相等：是 “数字相等”（底层标识的初步匹配）

hashCode()方法的返回值是一个int类型的数字（比如 12345、67890），“哈希值相等” 就是这两个数字完全一样。

• 这个数字的本质：是对象的 “哈希标识”，HashMap/HashSet 用它快速定位元素该放在哪个 “桶” 里（类似快递的分区编号）。
• 举例子：
  • 字符串s1 = "Java"，s1.hashCode()返回 2301506；
  • 字符串s2 = new String("Java")，s2.hashCode()也返回 2301506；
  • 这就叫 “哈希值相等”—— 两个对象的hashCode()返回的数字一样。
  • 如果是未重写hashCode()的自定义对象：new Student("001")和new Student("001")的hashCode()返回的是两个不同的数字（因为默认基于内存地址生成），这就是 “哈希值不相等”。

2. 内容相等：是 “业务逻辑上的相等”（你定义的相等规则）

equals()方法返回true，代表你认为这两个对象 “在业务意义上是同一个”，而不是 “内存地址相同”（Object 类默认是比较内存地址，但我们重写后就是比较业务字段）。

• 这个 “内容” 的本质：是你自定义的规则（比如 “学号相同就是同一个学生”“手机号相同就是同一个用户”）。
• 举例子：
  • 对于重写了equals()的 Student 类：s1 = new Student("001", "张三")，s2 = new Student("001", "张三三")，因为equals()只比较学号，所以s1.equals(s2)返回true（业务上相等）；
  • 对于未重写equals()的 Student 类：即使两个对象学号、姓名都一样，equals()也返回false（因为默认比较内存地址，两个对象是不同的内存地址）；
  • 对于 String 类："Java".equals(new String("Java"))返回true（String 已经重写了equals()，比较的是字符串内容）。

二、两个条件的关系：是 “先筛后验”，必须同时满足才判定为 “重复元素”

HashSet 判断 “两个元素是否重复”，是先通过哈希值快速筛，再通过 equals 精准验，只有两步都满足 “相等”，才会认为是重复元素。

补充：LinkedHashSet 基础

一、LinkedHashSet 基础：核心特点（入门）

LinkedHashSet 是 HashSet 的直接子类，因此它完全继承了 HashSet 的核心特性，同时又新增了自己的核心能力 ——保证元素的插入顺序。

1. 核心特点（对比 HashSet 记忆）

2. 直观示例：验证 “插入顺序”

先通过一个简单例子，感受 LinkedHashSet 和 HashSet 的核心差异：

import java.util.HashSet; import java.util.LinkedHashSet; public class LinkedHashSetBasicTest { public static void main(String[] args) { // 1. HashSet：无序 HashSet<String> hashSet = new HashSet<>(); hashSet.add("苹果"); hashSet.add("香蕉"); hashSet.add("橙子"); System.out.println("HashSet遍历结果：" + hashSet); // 输出（顺序随机）：比如 [橙子, 苹果, 香蕉] // 2. LinkedHashSet：按插入顺序遍历 LinkedHashSet<String> linkedHashSet = new LinkedHashSet<>(); linkedHashSet.add("苹果"); linkedHashSet.add("香蕉"); linkedHashSet.add("橙子"); System.out.println("LinkedHashSet遍历结果：" + linkedHashSet); // 输出（固定）：[苹果, 香蕉, 橙子] } }

从示例能直接看出：LinkedHashSet 遍历出来的元素顺序，和你添加的顺序完全一致，这是它和 HashSet 最直观的区别。

二、LinkedHashSet 底层原理（进阶）

因为 LinkedHashSet 是 HashSet 的子类，所以它的底层原理和 HashSet 高度相似，核心差异在于 “底层依赖的 Map 不同”——HashSet 依赖 HashMap，LinkedHashSet 依赖 LinkedHashMap。

1. 核心结论：LinkedHashSet 是 LinkedHashMap 的 “包装器”

和 HashSet 封装 HashMap 一样，LinkedHashSet 内部也维护一个LinkedHashMap对象，所有核心操作（add/remove/contains）都是调用 LinkedHashMap 的方法实现的：

• 存储元素时：把元素作为 LinkedHashMap 的key，value 是固定的空对象PRESENT（和 HashSet 完全一样）；
• 判重规则：和 HashSet 完全一致（hashCode()+equals()），自定义对象去重仍需重写这两个方法；
• 唯一差异：LinkedHashMap 比 HashMap 多了一个双向链表，用于维护元素的插入顺序。

2. 源码佐证（JDK 8）

public class LinkedHashSet<E> extends HashSet<E> implements Set<E>, Cloneable, java.io.Serializable { // 无参构造器：调用父类 HashSet 的构造器，创建一个 LinkedHashMap public LinkedHashSet() { super(16, 0.75f, true); // 第三个参数 true 代表“访问顺序”？不，是“是否按插入顺序” } // 父类 HashSet 的这个构造器（仅给 LinkedHashSet 调用） HashSet(int initialCapacity, float loadFactor, boolean dummy) { map = new LinkedHashMap<>(initialCapacity, loadFactor); // 核心：创建 LinkedHashMap } // add 方法直接继承自 HashSet，本质是调用 LinkedHashMap 的 put 方法 // public boolean add(E e) { return map.put(e, PRESENT)==null; } }

从源码能看出：LinkedHashSet 没有重写任何核心方法，只是在构造时把底层的 map 从 HashMap 换成了 LinkedHashMap。

3. LinkedHashMap 的底层结构（LinkedHashSet 顺序的核心）

LinkedHashMap 是 HashMap 的子类，它的底层结构是“数组 + 链表 + 红黑树 + 双向链表”：

• 基础结构（数组 + 链表 + 红黑树）：和 HashMap 完全一致，用于存储元素、解决哈希冲突；
• 新增结构（双向链表）：额外维护一个 “头节点→元素节点→尾节点” 的双向链表，每个节点除了保存哈希表的信息，还保存了before（前一个节点）和after（后一个节点）指针，用于记录元素的插入顺序。

4. 可视化理解：LinkedHashSet 底层结构

LinkedHashSet (外部表现) ↓ 内部依赖 LinkedHashMap ├── table (桶数组，和 HashMap 一样) │ ├── 下标0: null │ ├── 下标1: Node("苹果", PRESENT) → null │ ├── 下标2: Node("香蕉", PRESENT) → null │ └── ... ├── 双向链表（维护插入顺序）： │ 头节点 → Node("苹果") → Node("香蕉") → Node("橙子") → 尾节点 ├── size (元素个数) └── PRESENT (固定value)

• 哈希表（数组 + 链表 + 红黑树）：负责快速查找、判重（和 HashSet 一样）；
• 双向链表：负责维护顺序（遍历的时候，直接遍历这个双向链表，因此能保证插入顺序）。

5. LinkedHashSet 存储元素的流程（对比 HashSet）

以linkedHashSet.add("苹果")为例，流程和 HashSet 几乎一致，只多了 “维护双向链表” 的步骤：

1. 计算 “苹果” 的哈希值，确定桶位置；
2. 通过hashCode()+equals()判断是否重复，重复则不存入；
3. 不重复则：
   • 把元素存入哈希表的对应桶中；
   • 把元素节点添加到双向链表的尾部（保证插入顺序）。

三、LinkedHashSet 自定义对象去重（实战）

因为 LinkedHashSet 的判重规则和 HashSet 完全一致，所以自定义对象去重的方式也完全相同 —— 必须同时重写hashCode()和equals()，且逻辑要一致。