Java Set 集合详解
Set是Java集合框架中用于存储不重复元素的核心接口，它继承自Collection接口，提供了元素唯一性的保证。在Java开发中，Set集合被广泛应用于去重、集合运算、缓存实现等各种场景，是数据处理和算法实现的重要基础。
核心特性
Set接口 = 元素唯一性 + 无序性 + 集合运算 + 高性能查找 + 去重能力
- 🔍 元素唯一性：集合中每个元素只能出现一次，自动拒绝重复元素
- 🔀 无序性：大多数实现不保证元素的存储顺序（LinkedHashSet例外）
- 🔢 集合运算：支持并集(∪)、交集(∩)、差集(-)等数学集合操作
- ⚡ 高性能查找：多数实现提供O(1)查找性能，适合频繁检索
- 🧹 天然去重：添加重复元素时自动去重，不抛异常而是返回false
1. Set接口基础概念
1.1 什么是Set接口？
Set接口是Java集合框架中的核心接口，它继承自Collection接口，为不重复元素的集合提供了完整的抽象。
Set集合具有以下核心特征：
- 元素唯一性：不允许存储重复的元素，每个元素在集合中只能出现一次
- 无序性：大多数实现类不保证元素的存储顺序
- 继承Collection：具有Collection接口的所有基本方法
- 无索引访问：不支持通过索引直接访问元素
- 集合运算：支持并集、交集、差集等集合运算
1.2 Set接口的重要性
| 重要性 | 具体体现 | 业务价值 |
|---|---|---|
| 数据去重 | 自动去除重复元素 | 保证数据的一致性和准确性 |
| 快速查找 | 基于哈希的O(1)查找 | 提高数据检索效率 |
| 集合运算 | 支持复杂的集合操作 | 简化数据处理逻辑 |
| 缓存实现 | 天然适合缓存数据结构 | 支持高效的缓存管理 |
1.3 Set接口设计原则
Set接口的设计遵循以下几个核心原则：
唯一性原则
保证集合中每个元素的唯一性，避免重复数据
无序性原则
大多数实现类不保证元素的存储顺序，提高性能
集合运算原则
支持完整的集合运算，满足数学集合论的需求
高性能原则
提供高效的查找、插入、删除操作
Set接口核心方法示例
java
1public interface Set<E> extends Collection<E> {2 3 // ========== 基本操作 ==========4 boolean add(E e); // 添加元素，重复时返回false5 boolean remove(Object o); // 删除指定元素6 boolean contains(Object o); // 检查是否包含指定元素7 8 // ========== 集合运算 ==========9 boolean addAll(Collection<? extends E> c); // 添加集合（并集）10 boolean removeAll(Collection<?> c); // 删除集合（差集）11 boolean retainAll(Collection<?> c); // 保留集合（交集）12 void clear(); // 清空集合13 14 // ========== 查询操作 ==========15 int size(); // 获取元素个数16 boolean isEmpty(); // 判断是否为空17 18 // ========== 迭代器 ==========19 Iterator<E> iterator(); // 获取迭代器20}1.4 Set接口方法分类详解
Set接口提供了丰富的方法来操作不重复元素的集合，这些方法可以分为几个主要类别：
- 基本操作方法
- 集合运算方法
- 迭代器方法
Set基本操作方法
java
1public interface Set<E> extends Collection<E> {2 3 // 添加和删除元素4 boolean add(E e); // 添加元素，重复时返回false5 boolean remove(Object o); // 删除指定元素6 boolean contains(Object o); // 检查是否包含指定元素7 8 // 集合信息9 int size(); // 获取集合大小10 boolean isEmpty(); // 判断是否为空11 void clear(); // 清空集合12}| 方法 | 描述 | 返回值 | 特殊行为 |
|---|---|---|---|
add(E e) | 添加元素到集合 | 成功添加返回true，元素已存在返回false | 添加重复元素不会抛异常 |
remove(Object o) | 从集合移除元素 | 存在并移除返回true，不存在返回false | 性能因实现类而异 |
contains(Object o) | 检查元素是否在集合中 | 存在返回true，不存在返回false | HashSet为O(1)，TreeSet为O(log n) |
Set集合运算方法
java
1public interface Set<E> extends Collection<E> {2 3 // 并集操作4 boolean addAll(Collection<? extends E> c); // 添加另一个集合的所有元素5 6 // 差集操作7 boolean removeAll(Collection<?> c); // 删除另一个集合中的所有元素8 9 // 交集操作10 boolean retainAll(Collection<?> c); // 只保留另一个集合中存在的元素11}| 方法 | 描述 | 数学表示 | 应用场景 |
|---|---|---|---|
addAll(Collection<? extends E> c) | 添加另一个集合的所有元素（并集） | A ∪ B | 合并两个分类集合 |
retainAll(Collection<?> c) | 只保留也在指定集合中的元素（交集） | A ∩ B | 查找共同元素 |
removeAll(Collection<?> c) | 移除指定集合中的所有元素（差集） | A - B | 从一个集合中剔除特定元素 |
集合运算示例
java
1public void setOperationsExample() {2 Set<String> set1 = new HashSet<>(Arrays.asList("A", "B", "C"));3 Set<String> set2 = new HashSet<>(Arrays.asList("B", "C", "D"));4 5 // 并集：set1 ← set1 ∪ set2 = {A, B, C, D}6 set1.addAll(set2);7 8 // 交集：set1 ← set1 ∩ set2 = {B, C}9 set1.retainAll(set2);10 11 // 差集：set1 ← set1 - set2 = {A}12 set1.removeAll(set2);13}Set迭代器方法
java
1public interface Set<E> extends Collection<E> {2 3 // 获取迭代器4 Iterator<E> iterator(); // 获取集合的迭代器5 6 // 继承自Collection的其他迭代方法7 // forEach(Consumer<? super E> action) // Java 8+ 的forEach方法8 // spliterator() // Java 8+ 的并行迭代器9}| 方法 | 描述 | 返回值 | 特性 |
|---|---|---|---|
iterator() | 获取迭代器 | Iterator对象 | 允许遍历并可选择性删除元素 |
forEach(Consumer) | 对每个元素执行操作 | void | 简化迭代代码，Java 8+ |
迭代与遍历
遍历Set集合的4种方式：
- for-each循环：
for (E element : set) { ... } - Iterator：
Iterator<E> it = set.iterator(); while(it.hasNext()) { ... } - Lambda forEach：
set.forEach(e -> System.out.println(e)); - Stream API：
set.stream().forEach(e -> System.out.println(e));
Set迭代示例
java
1public void iterationExample() {2 Set<String> set = new HashSet<>(Arrays.asList("A", "B", "C"));3 4 // 方式1：for-each循环5 for (String element : set) {6 System.out.println(element);7 }8 9 // 方式2：Iterator (支持删除)10 Iterator<String> it = set.iterator();11 while (it.hasNext()) {12 String element = it.next();13 if (element.equals("B")) {14 it.remove(); // 安全删除元素15 }16 }17 18 // 方式3：Lambda forEach (Java 8+)19 set.forEach(element -> System.out.println(element));20}1.5 Set接口方法对比分析
| 操作类型 | 方法名 | 返回值 | 说明 | 使用场景 |
|---|---|---|---|---|
| 添加操作 | add(E) | boolean | 添加元素，重复时返回false | 基本元素添加 |
| 删除操作 | remove(Object) | boolean | 删除元素，不存在时返回false | 基本元素删除 |
| 查找操作 | contains(Object) | boolean | 检查元素是否存在 | 元素存在性检查 |
| 集合运算 | addAll(Collection) | boolean | 并集操作 | 合并两个集合 |
| 集合运算 | removeAll(Collection) | boolean | 差集操作 | 从集合中移除元素 |
| 集合运算 | retainAll(Collection) | boolean | 交集操作 | 保留共同元素 |
方法使用建议
- 添加元素：使用add()方法，注意处理重复元素的情况
- 删除元素：使用remove()方法，注意处理元素不存在的情况
- 集合运算：使用addAll()、removeAll()、retainAll()进行复杂操作
- 性能考虑：contains()操作在HashSet中为O(1)，在TreeSet中为O(log n)
2. Set 实现类详解
- HashSet
- LinkedHashSet
- TreeSet
- EnumSet
2.1 HashSet 概述
核心特点
HashSet是Set接口最常用的实现类，基于HashMap实现，具有以下特点：
- 🔍 基于HashMap：底层使用HashMap存储元素
- 🔀 无序性：不保证元素的存储顺序
- ⚡ 高性能：查找、插入、删除操作平均时间复杂度O(1)
- ⚪ 允许null：支持null元素
- ⚠️ 线程不安全：在多线程环境下需要外部同步
适用场景
- 需要快速查找、插入、删除的场景
- 数据去重处理
- 缓存实现
- 集合运算
- 对元素顺序没有要求的场景
2.2 HashSet 内部结构
HashSet基于HashMap实现，通过HashMap的键来存储Set的元素，值使用一个固定的虚拟对象。
核心字段
HashSet核心字段
java
1public class HashSet<E> extends AbstractSet<E>2 implements Set<E>, Cloneable, java.io.Serializable {3 4 // 底层使用HashMap存储元素5 private transient HashMap<E,Object> map;6 7 // 虚拟值，用于HashMap的值部分8 private static final Object PRESENT = new Object();9}构造方法
HashSet构造方法
java
1public class HashSet<E> extends AbstractSet<E> {2 3 /**4 * 构造一个默认初始容量的空HashSet5 */6 public HashSet() {7 map = new HashMap<>();8 }9 10 /**11 * 构造一个指定初始容量的空HashSet12 */13 public HashSet(int initialCapacity) {14 map = new HashMap<>(initialCapacity);15 }16 17 /**18 * 构造一个指定初始容量和负载因子的空HashSet19 */20 public HashSet(int initialCapacity, float loadFactor) {21 map = new HashMap<>(initialCapacity, loadFactor);22 }23 24 /**25 * 构造一个包含指定集合元素的HashSet26 */27 public HashSet(Collection<? extends E> c) {28 map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));29 addAll(c);30 }31}内存布局示意图
1HashSet 实例2┌─────────────────────────────────────────┐3│ map: HashMap<E,Object> │4│ ├── "Java" → PRESENT │5│ ├── "Python" → PRESENT │6│ ├── "C++" → PRESENT │7│ └── null → PRESENT │8│ │9│ PRESENT: Object (虚拟值) │10└─────────────────────────────────────────┘2.3 HashSet 核心方法实现
2.3.1 添加元素
HashSet添加元素实现
java
1public class HashSet<E> extends AbstractSet<E> {2 3 /**4 * 添加元素到HashSet5 * 时间复杂度：平均O(1)，最坏情况O(n)6 */7 public boolean add(E e) {8 // 使用HashMap的put方法，如果键不存在则返回null9 return map.put(e, PRESENT) == null;10 }11 12 /**13 * 批量添加元素14 * 时间复杂度：O(n)，n为要添加的元素个数15 */16 public boolean addAll(Collection<? extends E> c) {17 boolean modified = false;18 for (E e : c) {19 if (add(e)) {20 modified = true;21 }22 }23 return modified;24 }25}2.3.2 删除元素
HashSet删除元素实现
java
1public class HashSet<E> extends AbstractSet<E> {2 3 /**4 * 从HashSet中删除指定元素5 * 时间复杂度：平均O(1)，最坏情况O(n)6 */7 public boolean remove(Object o) {8 // 使用HashMap的remove方法，如果键存在则返回对应的值9 return map.remove(o) == PRESENT;10 }11 12 /**13 * 批量删除元素14 * 时间复杂度：O(n)，n为要删除的元素个数15 */16 public boolean removeAll(Collection<?> c) {17 boolean modified = false;18 for (Object o : c) {19 if (remove(o)) {20 modified = true;21 }22 }23 return modified;24 }25}2.3.3 查找元素
HashSet查找元素实现
java
1public class HashSet<E> extends AbstractSet<E> {2 3 /**4 * 检查HashSet是否包含指定元素5 * 时间复杂度：平均O(1)，最坏情况O(n)6 */7 public boolean contains(Object o) {8 // 使用HashMap的containsKey方法9 return map.containsKey(o);10 }11 12 /**13 * 检查HashSet是否包含指定集合的所有元素14 * 时间复杂度：O(n)，n为指定集合的大小15 */16 public boolean containsAll(Collection<?> c) {17 for (Object o : c) {18 if (!contains(o)) {19 return false;20 }21 }22 return true;23 }24}2.3.4 集合运算
HashSet集合运算实现
java
1public class HashSet<E> extends AbstractSet<E> {2 3 /**4 * 保留交集：只保留在指定集合中也存在的元素5 * 时间复杂度：O(n)，n为指定集合的大小6 */7 public boolean retainAll(Collection<?> c) {8 boolean modified = false;9 Iterator<E> it = iterator();10 while (it.hasNext()) {11 if (!c.contains(it.next())) {12 it.remove();13 modified = true;14 }15 }16 return modified;17 }18 19 /**20 * 清空HashSet21 * 时间复杂度：O(n)，n为集合大小22 */23 public void clear() {24 map.clear();25 }26}2.4 HashSet 性能分析
2.4.1 时间复杂度对比
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 添加元素 | 平均O(1) | 基于哈希值直接定位 |
| 删除元素 | 平均O(1) | 基于哈希值直接定位 |
| 查找元素 | 平均O(1) | 基于哈希值直接定位 |
| 遍历元素 | O(n) | 需要遍历所有元素 |
| 集合运算 | O(n) | 需要遍历集合元素 |
2.4.2 空间复杂度
- 存储开销：每个元素占用一个HashMap节点
- 哈希表开销：需要额外的哈希表数组空间
- 负载因子：影响空间使用效率，默认0.75
2.4.3 性能优化建议
HashSet性能优化示例
java
1public class HashSetOptimization {2 3 /**4 * 预分配容量优化5 */6 public static void capacityOptimization() {7 // 知道大概元素数量时，预分配容量8 int expectedSize = 1000;9 Set<String> optimizedSet = new HashSet<>(expectedSize);10 11 // 避免频繁扩容12 for (int i = 0; i < expectedSize; i++) {13 optimizedSet.add("item" + i);14 }15 }16 17 /**18 * 批量操作优化19 */20 public static void batchOperationOptimization() {21 Set<String> set1 = new HashSet<>();22 Set<String> set2 = new HashSet<>();23 24 // 批量添加，比循环add效率高25 set1.addAll(set2);26 27 // 批量删除28 set1.removeAll(set2);29 30 // 保留交集31 set1.retainAll(set2);32 }33 34 /**35 * 元素类型优化36 */37 public static void elementTypeOptimization() {38 // 推荐：使用不可变对象39 Set<String> goodSet = new HashSet<>();40 41 // 不推荐：使用可变对象42 Set<StringBuilder> badSet = new HashSet<>();43 }44}2.5 HashSet 使用示例
2.5.1 基本操作示例
HashSet基本操作示例
java
1public class HashSetBasicExample {2 3 public static void main(String[] args) {4 // 创建HashSet5 Set<String> set = new HashSet<>();6 7 // 添加元素8 set.add("Java");9 set.add("Python");10 set.add("C++");11 set.add("JavaScript");12 13 // 尝试添加重复元素14 boolean added = set.add("Java");15 System.out.println("添加重复元素Java: " + added); // false16 17 System.out.println("Set大小: " + set.size()); // 418 19 // 检查元素是否存在20 boolean contains = set.contains("Python");21 System.out.println("是否包含Python: " + contains); // true22 23 // 删除元素24 boolean removed = set.remove("C++");25 System.out.println("删除C++: " + removed); // true26 27 // 遍历元素28 System.out.println("Set中的元素:");29 for (String item : set) {30 System.out.println(item);31 }32 33 // 清空集合34 set.clear();35 System.out.println("清空后大小: " + set.size()); // 036 }37}2.5.2 集合运算示例
HashSet集合运算示例
java
1public class HashSetSetOperationsExample {2 3 public static void main(String[] args) {4 // 创建两个Set5 Set<String> set1 = new HashSet<>();6 set1.add("Java");7 set1.add("Python");8 set1.add("C++");9 set1.add("JavaScript");10 11 Set<String> set2 = new HashSet<>();12 set2.add("Python");13 set2.add("C++");14 set2.add("Go");15 set2.add("Rust");16 17 System.out.println("Set1: " + set1);18 System.out.println("Set2: " + set2);19 20 // 并集操作21 Set<String> union = new HashSet<>(set1);22 union.addAll(set2);23 System.out.println("并集: " + union);24 25 // 交集操作26 Set<String> intersection = new HashSet<>(set1);27 intersection.retainAll(set2);28 System.out.println("交集: " + intersection);29 30 // 差集操作31 Set<String> difference = new HashSet<>(set1);32 difference.removeAll(set2);33 System.out.println("差集(Set1 - Set2): " + difference);34 35 // 对称差集36 Set<String> symmetricDifference = new HashSet<>(union);37 symmetricDifference.removeAll(intersection);38 System.out.println("对称差集: " + symmetricDifference);39 }40}2.5.3 去重示例
HashSet去重示例
java
1public class HashSetDeduplicationExample {2 3 public static void main(String[] args) {4 // 数组去重5 String[] array = {"Java", "Python", "Java", "C++", "Python", "JavaScript"};6 Set<String> uniqueSet = new HashSet<>(Arrays.asList(array));7 String[] uniqueArray = uniqueSet.toArray(new String[0]);8 9 System.out.println("原始数组: " + Arrays.toString(array));10 System.out.println("去重后: " + Arrays.toString(uniqueArray));11 12 // 列表去重13 List<Integer> list = Arrays.asList(1, 2, 3, 2, 4, 1, 5, 3, 6);14 Set<Integer> uniqueNumbers = new HashSet<>(list);15 List<Integer> uniqueList = new ArrayList<>(uniqueNumbers);16 17 System.out.println("原始列表: " + list);18 System.out.println("去重后: " + uniqueList);19 20 // 对象去重21 List<Person> people = Arrays.asList(22 new Person("Alice", 25),23 new Person("Bob", 30),24 new Person("Alice", 25), // 重复25 new Person("Charlie", 35)26 );27 28 Set<Person> uniquePeople = new HashSet<>(people);29 System.out.println("去重后的人数: " + uniquePeople.size());30 uniquePeople.forEach(System.out::println);31 }32 33 // Person类34 static class Person {35 private String name;36 private int age;37 38 public Person(String name, int age) {39 this.name = name;40 this.age = age;41 }42 43 @Override44 public boolean equals(Object o) {45 if (this == o) return true;46 if (o == null || getClass() != o.getClass()) return false;47 Person person = (Person) o;48 return age == person.age && Objects.equals(name, person.name);49 }50 51 @Override52 public int hashCode() {53 return Objects.hash(name, age);54 }55 56 @Override57 public String toString() {58 return "Person{name='" + name + "', age=" + age + "}";59 }60 }61}3.1 LinkedHashSet 概述
核心特点
LinkedHashSet是HashSet的子类，在HashSet的基础上维护了插入顺序，具有以下特点：
- 🔄 继承HashSet：基于HashSet实现，具有HashSet的所有特性
- 📝 维护顺序：通过双向链表维护元素的插入顺序
- ⚖️ 性能平衡：在HashSet高性能的基础上增加了顺序维护
- ⚪ 允许null：支持null元素
- ⚠️ 线程不安全：在多线程环境下需要外部同步
适用场景
- 需要保持元素插入顺序的场景
- 需要去重且保持顺序的场景
- LRU缓存实现
- 需要按插入顺序遍历的场景
3.2 LinkedHashSet 内部结构
LinkedHashSet继承自HashSet，通过重写HashSet的构造方法来实现顺序维护。
核心字段
LinkedHashSet核心字段
java
1public class LinkedHashSet<E> extends HashSet<E>2 implements Set<E>, Cloneable, java.io.Serializable {3 4 // 继承自HashSet的字段5 // private transient HashMap<E,Object> map;6 // private static final Object PRESENT = new Object();7 8 // 通过调用HashSet的特定构造方法来维护顺序9 // 这个构造方法会创建LinkedHashMap而不是HashMap10}构造方法
LinkedHashSet构造方法
java
1public class LinkedHashSet<E> extends HashSet<E> {2 3 /**4 * 构造一个默认初始容量的空LinkedHashSet5 */6 public LinkedHashSet() {7 super(16, .75f, true); // 调用HashSet的特定构造方法8 }9 10 /**11 * 构造一个指定初始容量的空LinkedHashSet12 */13 public LinkedHashSet(int initialCapacity) {14 super(initialCapacity, .75f, true);15 }16 17 /**18 * 构造一个指定初始容量和负载因子的空LinkedHashSet19 */20 public LinkedHashSet(int initialCapacity, float loadFactor) {21 super(initialCapacity, loadFactor, true);22 }23 24 /**25 * 构造一个包含指定集合元素的LinkedHashSet26 */27 public LinkedHashSet(Collection<? extends E> c) {28 super(Math.max(2*c.size(), 11), .75f, true);29 addAll(c);30 }31}内存布局示意图
1LinkedHashSet 实例2┌─────────────────────────────────────────┐3│ map: LinkedHashMap<E,Object> │4│ ├── "Java" → PRESENT │5│ ├── "Python" → PRESENT │6│ ├── "C++" → PRESENT │7│ └── "JavaScript" → PRESENT │8│ │9│ 双向链表维护插入顺序: │10│ Java ←→ Python ←→ C++ ←→ JavaScript │11│ │12│ PRESENT: Object (虚拟值) │13└─────────────────────────────────────────┘3.3 LinkedHashSet 核心特性
3.3.1 顺序维护机制
LinkedHashSet顺序维护
java
1public class LinkedHashSet<E> extends HashSet<E> {2 3 /**4 * LinkedHashSet通过调用HashSet的特定构造方法来实现顺序维护5 * 该构造方法会创建LinkedHashMap而不是HashMap6 */7 8 // HashSet中的特定构造方法（包私有）9 HashSet(int initialCapacity, float loadFactor, boolean dummy) {10 map = new LinkedHashMap<>(initialCapacity, loadFactor);11 }12}3.3.2 性能特点
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 添加元素 | 平均O(1) | 基于哈希值定位 + 链表维护 |
| 删除元素 | 平均O(1) | 基于哈希值定位 + 链表维护 |
| 查找元素 | 平均O(1) | 基于哈希值直接定位 |
| 遍历元素 | O(n) | 按插入顺序遍历 |
| 顺序访问 | O(1) | 通过链表直接访问 |
3.4 LinkedHashSet 使用示例
3.4.1 基本操作示例
LinkedHashSet基本操作示例
java
1public class LinkedHashSetBasicExample {2 3 public static void main(String[] args) {4 // 创建LinkedHashSet5 Set<String> linkedHashSet = new LinkedHashSet<>();6 7 // 添加元素8 linkedHashSet.add("Java");9 linkedHashSet.add("Python");10 linkedHashSet.add("C++");11 linkedHashSet.add("JavaScript");12 13 System.out.println("LinkedHashSet按插入顺序:");14 for (String item : linkedHashSet) {15 System.out.println(item);16 }17 18 // 与HashSet对比19 Set<String> hashSet = new HashSet<>();20 hashSet.add("Java");21 hashSet.add("Python");22 hashSet.add("C++");23 hashSet.add("JavaScript");24 25 System.out.println("\nHashSet顺序（可能不同）:");26 for (String item : hashSet) {27 System.out.println(item);28 }29 30 // 删除元素后顺序保持不变31 linkedHashSet.remove("Python");32 System.out.println("\n删除Python后:");33 for (String item : linkedHashSet) {34 System.out.println(item);35 }36 }37}3.4.2 去重保持顺序示例
LinkedHashSet去重保持顺序示例
java
1public class LinkedHashSetDeduplicationExample {2 3 public static void main(String[] args) {4 // 使用LinkedHashSet进行去重并保持顺序5 List<String> list = Arrays.asList("Java", "Python", "Java", "C++", "Python", "JavaScript");6 7 // 使用LinkedHashSet去重8 Set<String> uniqueSet = new LinkedHashSet<>(list);9 List<String> uniqueList = new ArrayList<>(uniqueSet);10 11 System.out.println("原始列表: " + list);12 System.out.println("去重后保持顺序: " + uniqueList);13 14 // 与HashSet对比15 Set<String> hashSet = new HashSet<>(list);16 List<String> hashSetList = new ArrayList<>(hashSet);17 18 System.out.println("HashSet去重（顺序可能不同）: " + hashSetList);19 }20}3.4.3 LRU缓存实现示例
LinkedHashSet实现LRU缓存示例
java
1public class LinkedHashSetLRUCacheExample {2 3 // 简单的LRU缓存实现4 static class LRUCache<K, V> {5 private final int capacity;6 private final LinkedHashMap<K, V> cache;7 8 public LRUCache(int capacity) {9 this.capacity = capacity;10 this.cache = new LinkedHashMap<K, V>(capacity, 0.75f, true) {11 @Override12 protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {13 return size() > capacity;14 }15 };16 }17 18 public V get(K key) {19 return cache.get(key);20 }21 22 public void put(K key, V value) {23 cache.put(key, value);24 }25 26 public void remove(K key) {27 cache.remove(key);28 }29 30 public int size() {31 return cache.size();32 }33 34 public Set<K> keySet() {35 return cache.keySet();36 }37 }38 39 public static void main(String[] args) {40 // 创建LRU缓存41 LRUCache<String, String> cache = new LRUCache<>(3);42 43 // 添加元素44 cache.put("key1", "value1");45 cache.put("key2", "value2");46 cache.put("key3", "value3");47 48 System.out.println("缓存键集合: " + cache.keySet());49 50 // 访问key1，使其成为最近使用的51 cache.get("key1");52 53 // 添加新元素，会淘汰最久未使用的54 cache.put("key4", "value4");55 56 System.out.println("添加key4后: " + cache.keySet());57 }58}4.1 TreeSet 概述
核心特点
TreeSet是基于TreeMap实现的有序Set，具有以下特点：
- 🌳 基于TreeMap：底层使用TreeMap存储元素
- 📊 有序性：元素按照自然顺序或自定义比较器排序
- ⛔ 不允许null：不支持null元素
- ⚠️ 线程不安全：在多线程环境下需要外部同步
- 📉 性能特点：查找、插入、删除操作时间复杂度O(log n)
适用场景
- 需要元素有序的场景
- 需要范围查询的场景
- 需要获取最大最小元素的场景
- 需要按顺序遍历的场景
4.2 TreeSet 内部结构
TreeSet基于TreeMap实现，通过TreeMap的键来存储Set的元素，值使用一个固定的虚拟对象。
核心字段
TreeSet核心字段
java
1public class TreeSet<E> extends AbstractSet<E>2 implements NavigableSet<E>, Cloneable, java.io.Serializable {3 4 // 底层使用NavigableMap存储元素5 private transient NavigableMap<E,Object> m;6 7 // 虚拟值，用于NavigableMap的值部分8 private static final Object PRESENT = new Object();9}构造方法
TreeSet构造方法
java
1public class TreeSet<E> extends AbstractSet<E> {2 3 /**4 * 构造一个使用自然顺序的空TreeSet5 */6 public TreeSet() {7 this(new TreeMap<E,Object>());8 }9 10 /**11 * 构造一个使用指定比较器的空TreeSet12 */13 public TreeSet(Comparator<? super E> comparator) {14 this(new TreeMap<>(comparator));15 }16 17 /**18 * 构造一个包含指定集合元素的TreeSet19 */20 public TreeSet(Collection<? extends E> c) {21 this();22 addAll(c);23 }24 25 /**26 * 构造一个包含指定SortedSet元素的TreeSet27 */28 public TreeSet(SortedSet<E> s) {29 this(s.comparator());30 addAll(s);31 }32 33 /**34 * 包私有构造方法，用于内部实现35 */36 TreeSet(NavigableMap<E,Object> m) {37 this.m = m;38 }39}内存布局示意图
1TreeSet 实例 (红黑树)2┌─────────────────────────────────────────┐3│ m: TreeMap<E,Object> │4│ │5│ 红黑树结构: │6│ C++ │7│ / \ │8│ Java Python │9│ / │10│ JavaScript │11│ │12│ 每个节点: key → PRESENT │13│ PRESENT: Object (虚拟值) │14└─────────────────────────────────────────┘4.3 TreeSet 核心方法实现
4.3.1 添加元素
TreeSet添加元素实现
java
1public class TreeSet<E> extends AbstractSet<E> {2 3 /**4 * 添加元素到TreeSet5 * 时间复杂度：O(log n)6 */7 public boolean add(E e) {8 // 使用TreeMap的put方法，如果键不存在则返回null9 return m.put(e, PRESENT) == null;10 }11 12 /**13 * 批量添加元素14 * 时间复杂度：O(n log n)，n为要添加的元素个数15 */16 public boolean addAll(Collection<? extends E> c) {17 boolean modified = false;18 for (E e : c) {19 if (add(e)) {20 modified = true;21 }22 }23 return modified;24 }25}4.3.2 删除元素
TreeSet删除元素实现
java
1public class TreeSet<E> extends AbstractSet<E> {2 3 /**4 * 从TreeSet中删除指定元素5 * 时间复杂度：O(log n)6 */7 public boolean remove(Object o) {8 // 使用TreeMap的remove方法，如果键存在则返回对应的值9 return m.remove(o) == PRESENT;10 }11 12 /**13 * 清空TreeSet14 * 时间复杂度：O(n)，n为集合大小15 */16 public void clear() {17 m.clear();18 }19}4.3.3 查找元素
TreeSet查找元素实现
java
1public class TreeSet<E> extends AbstractSet<E> {2 3 /**4 * 检查TreeSet是否包含指定元素5 * 时间复杂度：O(log n)6 */7 public boolean contains(Object o) {8 // 使用TreeMap的containsKey方法9 return m.containsKey(o);10 }11 12 /**13 * 获取第一个元素（最小元素）14 * 时间复杂度：O(log n)15 */16 public E first() {17 return m.firstKey();18 }19 20 /**21 * 获取最后一个元素（最大元素）22 * 时间复杂度：O(log n)23 */24 public E last() {25 return m.lastKey();26 }27}4.3.4 导航方法
TreeSet导航方法实现
java
1public class TreeSet<E> extends AbstractSet<E> {2 3 /**4 * 获取小于指定元素的最大元素5 * 时间复杂度：O(log n)6 */7 public E lower(E e) {8 return m.lowerKey(e);9 }10 11 /**12 * 获取小于等于指定元素的最大元素13 * 时间复杂度：O(log n)14 */15 public E floor(E e) {16 return m.floorKey(e);17 }18 19 /**20 * 获取大于等于指定元素的最小元素21 * 时间复杂度：O(log n)22 */23 public E ceiling(E e) {24 return m.ceilingKey(e);25 }26 27 /**28 * 获取大于指定元素的最小元素29 * 时间复杂度：O(log n)30 */31 public E higher(E e) {32 return m.higherKey(e);33 }34}4.4 TreeSet 性能分析
4.4.1 时间复杂度对比
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 添加元素 | O(log n) | 需要维护红黑树平衡 |
| 删除元素 | O(log n) | 需要维护红黑树平衡 |
| 查找元素 | O(log n) | 基于红黑树查找 |
| 获取最大最小 | O(log n) | 基于红黑树查找 |
| 遍历元素 | O(n) | 中序遍历红黑树 |
| 范围查询 | O(log n + k) | k为结果集大小 |
4.4.2 空间复杂度
- 存储开销：每个元素占用一个红黑树节点
- 树结构开销：需要额外的树节点引用
- 平衡开销：维护红黑树平衡的额外开销
4.5 TreeSet 使用示例
4.5.1 基本操作示例
TreeSet基本操作示例
java
1public class TreeSetBasicExample {2 3 public static void main(String[] args) {4 // 自然顺序排序5 Set<String> naturalOrderSet = new TreeSet<>();6 naturalOrderSet.add("Java");7 naturalOrderSet.add("Python");8 naturalOrderSet.add("C++");9 naturalOrderSet.add("JavaScript");10 11 System.out.println("自然顺序:");12 for (String item : naturalOrderSet) {13 System.out.println(item);14 }15 16 // 自定义比较器（逆序）17 Set<String> customOrderSet = new TreeSet<>((s1, s2) -> s2.compareTo(s1));18 customOrderSet.add("Java");19 customOrderSet.add("Python");20 customOrderSet.add("C++");21 customOrderSet.add("JavaScript");22 23 System.out.println("\n自定义顺序（逆序）:");24 for (String item : customOrderSet) {25 System.out.println(item);26 }27 28 // 数字排序29 Set<Integer> numberSet = new TreeSet<>();30 numberSet.add(5);31 numberSet.add(2);32 numberSet.add(8);33 numberSet.add(1);34 numberSet.add(3);35 36 System.out.println("\n数字排序:");37 for (Integer num : numberSet) {38 System.out.println(num);39 }40 }41}4.5.2 导航方法示例
TreeSet导航方法示例
java
1public class TreeSetNavigationExample {2 3 public static void main(String[] args) {4 // 创建TreeSet5 TreeSet<String> treeSet = new TreeSet<>();6 treeSet.add("Alice");7 treeSet.add("Bob");8 treeSet.add("Charlie");9 treeSet.add("David");10 treeSet.add("Eve");11 treeSet.add("Frank");12 13 System.out.println("TreeSet: " + treeSet);14 15 // 获取第一个和最后一个元素16 String first = treeSet.first();17 String last = treeSet.last();18 System.out.println("第一个元素: " + first);19 System.out.println("最后一个元素: " + last);20 21 // 导航方法22 String target = "Charlie";23 String lower = treeSet.lower(target);24 String floor = treeSet.floor(target);25 String ceiling = treeSet.ceiling(target);26 String higher = treeSet.higher(target);27 28 System.out.println("\n导航方法示例（目标: " + target + "）:");29 System.out.println("lower: " + lower); // 小于Charlie的最大元素30 System.out.println("floor: " + floor); // 小于等于Charlie的最大元素31 System.out.println("ceiling: " + ceiling); // 大于等于Charlie的最小元素32 System.out.println("higher: " + higher); // 大于Charlie的最小元素33 34 // 子集操作35 SortedSet<String> subSet = treeSet.subSet("Bob", "Eve");36 System.out.println("\n子集 [Bob, Eve): " + subSet);37 38 SortedSet<String> headSet = treeSet.headSet("David");39 System.out.println("头集 [开始, David): " + headSet);40 41 SortedSet<String> tailSet = treeSet.tailSet("David");42 System.out.println("尾集 [David, 结束): " + tailSet);43 }44}4.5.3 自定义对象排序示例
TreeSet自定义对象排序示例
java
1public class TreeSetCustomObjectExample {2 3 // 学生类4 static class Student implements Comparable<Student> {5 private String name;6 private int age;7 private double score;8 9 public Student(String name, int age, double score) {10 this.name = name;11 this.age = age;12 this.score = score;13 }14 15 @Override16 public int compareTo(Student other) {17 // 首先按分数排序（降序），分数相同时按年龄排序（升序）18 int scoreCompare = Double.compare(other.score, this.score);19 if (scoreCompare != 0) {20 return scoreCompare;21 }22 return Integer.compare(this.age, other.age);23 }24 25 @Override26 public String toString() {27 return "Student{name='" + name + "', age=" + age + ", score=" + score + "}";28 }29 }30 31 public static void main(String[] args) {32 // 使用自然顺序的TreeSet33 Set<Student> studentSet = new TreeSet<>();34 studentSet.add(new Student("Alice", 20, 85.5));35 studentSet.add(new Student("Bob", 22, 90.0));36 studentSet.add(new Student("Charlie", 21, 85.5));37 studentSet.add(new Student("David", 23, 88.0));38 39 System.out.println("按分数降序、年龄升序排列:");40 for (Student student : studentSet) {41 System.out.println(student);42 }43 44 // 使用自定义比较器的TreeSet45 Set<Student> ageSet = new TreeSet<>((s1, s2) -> Integer.compare(s1.age, s2.age));46 ageSet.addAll(studentSet);47 48 System.out.println("\n按年龄升序排列:");49 for (Student student : ageSet) {50 System.out.println(student);51 }52 }53}5. 其他Set实现类详解
5.1 CopyOnWriteArraySet 实现类详解
5.1.1 CopyOnWriteArraySet 概述
核心特点
CopyOnWriteArraySet是基于CopyOnWriteArrayList实现的线程安全Set，具有以下特点：
- 基于CopyOnWriteArrayList：底层使用CopyOnWriteArrayList存储元素
- 线程安全：所有操作都是线程安全的
- 写时复制：修改操作会创建新的数组副本
- 读多写少：适合读多写少的场景
- 性能特点：读操作性能好，写操作性能较差
5.1.2 CopyOnWriteArraySet 使用示例
CopyOnWriteArraySet使用示例
java
1public class CopyOnWriteArraySetExample {2 3 public static void main(String[] args) {4 // 创建线程安全的Set5 Set<String> set = new CopyOnWriteArraySet<>();6 7 // 多线程安全操作8 Thread t1 = new Thread(() -> {9 for (int i = 0; i < 1000; i++) {10 set.add("Thread1-" + i);11 }12 });13 14 Thread t2 = new Thread(() -> {15 for (int i = 0; i < 1000; i++) {16 set.add("Thread2-" + i);17 }18 });19 20 t1.start();21 t2.start();22 23 try {24 t1.join();25 t2.join();26 } catch (InterruptedException e) {27 e.printStackTrace();28 }29 30 System.out.println("最终大小: " + set.size());31 32 // 遍历操作（线程安全）33 for (String item : set) {34 // 遍历过程中可以安全地修改集合35 set.add("new-item");36 }37 }38}5.2.1 EnumSet 概述
核心特点
EnumSet是专门为枚举类型设计的高效Set实现，具有以下特点：
- 🔠 专门为枚举设计：只能存储枚举类型的元素
- ⚡ 高性能：基于位向量实现，性能极高
- 📊 内存效率：使用位运算，内存占用极小
- ⚠️ 线程不安全：在多线程环境下需要外部同步
- ⛔ 不允许null：不支持null元素
5.2.2 EnumSet 使用示例
EnumSet使用示例
java
1public class EnumSetExample {2 3 // 颜色枚举4 enum Color {5 RED, GREEN, BLUE, YELLOW, BLACK, WHITE6 }7 8 // 权限枚举9 enum Permission {10 READ, WRITE, EXECUTE, DELETE11 }12 13 public static void main(String[] args) {14 // 创建包含所有元素的EnumSet15 EnumSet<Color> allColors = EnumSet.allOf(Color.class);16 System.out.println("所有颜色: " + allColors);17 18 // 创建空的EnumSet19 EnumSet<Color> emptyColors = EnumSet.noneOf(Color.class);20 emptyColors.add(Color.RED);21 emptyColors.add(Color.GREEN);22 System.out.println("部分颜色: " + emptyColors);23 24 // 创建指定范围的EnumSet25 EnumSet<Color> rangeColors = EnumSet.range(Color.RED, Color.BLUE);26 System.out.println("范围颜色: " + rangeColors);27 28 // 创建指定元素的EnumSet29 EnumSet<Color> specificColors = EnumSet.of(Color.RED, Color.BLUE, Color.WHITE);30 System.out.println("指定颜色: " + specificColors);31 32 // 权限管理示例33 EnumSet<Permission> userPermissions = EnumSet.of(Permission.READ, Permission.WRITE);34 System.out.println("用户权限: " + userPermissions);35 36 // 检查权限37 boolean canRead = userPermissions.contains(Permission.READ);38 boolean canExecute = userPermissions.contains(Permission.EXECUTE);39 System.out.println("可以读取: " + canRead);40 System.out.println("可以执行: " + canExecute);41 42 // 添加权限43 userPermissions.add(Permission.EXECUTE);44 System.out.println("添加执行权限后: " + userPermissions);45 46 // 移除权限47 userPermissions.remove(Permission.WRITE);48 System.out.println("移除写权限后: " + userPermissions);49 }50}5.3 ConcurrentSkipListSet 实现类详解
5.3.1 ConcurrentSkipListSet 概述
核心特点
ConcurrentSkipListSet是基于ConcurrentSkipListMap实现的线程安全有序Set，具有以下特点：
- 基于跳表：底层使用跳表数据结构
- 线程安全：所有操作都是线程安全的
- 有序性：元素按照自然顺序或自定义比较器排序
- 高性能：查找、插入、删除操作时间复杂度O(log n)
- 不允许null：不支持null元素
5.3.2 ConcurrentSkipListSet 使用示例
ConcurrentSkipListSet使用示例
java
1public class ConcurrentSkipListSetExample {2 3 public static void main(String[] args) {4 // 创建线程安全的有序Set5 Set<String> set = new ConcurrentSkipListSet<>();6 7 // 多线程并发添加元素8 Thread t1 = new Thread(() -> {9 for (int i = 0; i < 100; i++) {10 set.add("Thread1-" + i);11 }12 });13 14 Thread t2 = new Thread(() -> {15 for (int i = 0; i < 100; i++) {16 set.add("Thread2-" + i);17 }18 });19 20 t1.start();21 t2.start();22 23 try {24 t1.join();25 t2.join();26 } catch (InterruptedException e) {27 e.printStackTrace();28 }29 30 System.out.println("最终大小: " + set.size());31 32 // 有序遍历33 System.out.println("前10个元素:");34 int count = 0;35 for (String item : set) {36 if (count++ < 10) {37 System.out.println(item);38 } else {39 break;40 }41 }42 43 // 数字排序示例44 Set<Integer> numberSet = new ConcurrentSkipListSet<>();45 numberSet.add(5);46 numberSet.add(2);47 numberSet.add(8);48 numberSet.add(1);49 numberSet.add(3);50 51 System.out.println("有序数字: " + numberSet);52 }53}6. 实际应用场景
6.1 数据去重处理
数据去重处理示例
java
1public class DataDeduplicationExample {2 3 public static void main(String[] args) {4 // 用户ID去重5 List<String> userIds = Arrays.asList("user1", "user2", "user1", "user3", "user2", "user4");6 Set<String> uniqueUserIds = new HashSet<>(userIds);7 System.out.println("去重后的用户ID: " + uniqueUserIds);8 9 // 保持插入顺序的去重10 List<String> orderedIds = Arrays.asList("user1", "user2", "user1", "user3", "user2", "user4");11 Set<String> orderedUniqueIds = new LinkedHashSet<>(orderedIds);12 System.out.println("保持顺序的去重: " + orderedUniqueIds);13 14 // 对象去重15 List<Employee> employees = Arrays.asList(16 new Employee("Alice", "IT"),17 new Employee("Bob", "HR"),18 new Employee("Alice", "IT"), // 重复19 new Employee("Charlie", "Finance")20 );21 22 Set<Employee> uniqueEmployees = new HashSet<>(employees);23 System.out.println("去重后的员工: " + uniqueEmployees);24 }25 26 static class Employee {27 private String name;28 private String department;29 30 public Employee(String name, String department) {31 this.name = name;32 this.department = department;33 }34 35 @Override36 public boolean equals(Object o) {37 if (this == o) return true;38 if (o == null || getClass() != o.getClass()) return false;39 Employee employee = (Employee) o;40 return Objects.equals(name, employee.name) && 41 Objects.equals(department, employee.department);42 }43 44 @Override45 public int hashCode() {46 return Objects.hash(name, department);47 }48 49 @Override50 public String toString() {51 return "Employee{name='" + name + "', department='" + department + "'}";52 }53 }54}6.2 集合运算应用
集合运算应用示例
java
1public class SetOperationsApplicationExample {23 public static void main(String[] args) {4 // 用户权限管理5 Set<String> adminPermissions = new HashSet<>(Arrays.asList("read", "write", "delete", "admin"));6 Set<String> userPermissions = new HashSet<>(Arrays.asList("read", "write"));7 Set<String> guestPermissions = new HashSet<>(Arrays.asList("read"));8 9 // 计算权限差异10 Set<String> adminOnlyPermissions = new HashSet<>(adminPermissions);11 adminOnlyPermissions.removeAll(userPermissions);12 System.out.println("管理员独有权限: " + adminOnlyPermissions);13 14 // 计算共同权限15 Set<String> commonPermissions = new HashSet<>(userPermissions);16 commonPermissions.retainAll(guestPermissions);17 System.out.println("用户和访客共同权限: " + commonPermissions);18 19 // 权限升级20 Set<String> upgradedPermissions = new HashSet<>(userPermissions);21 upgradedPermissions.addAll(Arrays.asList("delete"));22 System.out.println("升级后的用户权限: " + upgradedPermissions);23 24 // 标签系统25 Set<String> user1Tags = new HashSet<>(Arrays.asList("java", "spring", "database"));26 Set<String> user2Tags = new HashSet<>(Arrays.asList("python", "spring", "machine-learning"));27 28 // 共同兴趣29 Set<String> commonInterests = new HashSet<>(user1Tags);30 commonInterests.retainAll(user2Tags);31 System.out.println("共同兴趣: " + commonInterests);32 33 // 推荐标签34 Set<String> recommendedTags = new HashSet<>(user2Tags);35 recommendedTags.removeAll(user1Tags);36 System.out.println("推荐给用户1的标签: " + recommendedTags);37 }38}6.3 缓存实现
缓存实现示例
java
1public class CacheImplementationExample {2 3 // 简单缓存实现4 static class SimpleCache<K, V> {5 private final Map<K, V> cache = new HashMap<>();6 private final Set<K> accessedKeys = new LinkedHashSet<>();7 private final int maxSize;8 9 public SimpleCache(int maxSize) {10 this.maxSize = maxSize;11 }12 13 public V get(K key) {14 V value = cache.get(key);15 if (value != null) {16 // 记录访问顺序17 accessedKeys.remove(key);18 accessedKeys.add(key);19 }20 return value;21 }22 23 public void put(K key, V value) {24 if (cache.size() >= maxSize && !cache.containsKey(key)) {25 // 移除最久未访问的元素26 K oldestKey = accessedKeys.iterator().next();27 accessedKeys.remove(oldestKey);28 cache.remove(oldestKey);29 }30 31 cache.put(key, value);32 accessedKeys.remove(key);33 accessedKeys.add(key);34 }35 36 public void remove(K key) {37 cache.remove(key);38 accessedKeys.remove(key);39 }40 41 public int size() {42 return cache.size();43 }44 45 public Set<K> keySet() {46 return new HashSet<>(cache.keySet());47 }48 }49 50 public static void main(String[] args) {51 // 创建缓存52 SimpleCache<String, String> cache = new SimpleCache<>(3);53 54 // 添加元素55 cache.put("key1", "value1");56 cache.put("key2", "value2");57 cache.put("key3", "value3");58 59 System.out.println("缓存大小: " + cache.size());60 System.out.println("缓存键: " + cache.keySet());61 62 // 访问元素63 cache.get("key1");64 65 // 添加新元素，会淘汰最久未访问的66 cache.put("key4", "value4");67 68 System.out.println("添加key4后: " + cache.keySet());69 70 // 使用TreeSet实现有序缓存71 Set<String> sortedCache = new TreeSet<>();72 sortedCache.add("item3");73 sortedCache.add("item1");74 sortedCache.add("item2");75 76 System.out.println("有序缓存: " + sortedCache);77 }78}6.4 黑名单/白名单系统
黑名单白名单系统示例
java
1public class BlacklistWhitelistExample {2 3 // 黑名单系统4 static class BlacklistSystem {5 private final Set<String> blacklist = new HashSet<>();6 private final Set<String> whitelist = new HashSet<>();7 8 public void addToBlacklist(String item) {9 blacklist.add(item);10 whitelist.remove(item); // 从白名单中移除11 }12 13 public void addToWhitelist(String item) {14 whitelist.add(item);15 blacklist.remove(item); // 从黑名单中移除16 }17 18 public boolean isAllowed(String item) {19 // 如果在黑名单中，则不允许20 if (blacklist.contains(item)) {21 return false;22 }23 // 如果白名单为空，则允许所有非黑名单项目24 if (whitelist.isEmpty()) {25 return true;26 }27 // 否则只允许白名单中的项目28 return whitelist.contains(item);29 }30 31 public void removeFromBlacklist(String item) {32 blacklist.remove(item);33 }34 35 public void removeFromWhitelist(String item) {36 whitelist.remove(item);37 }38 39 public Set<String> getBlacklist() {40 return new HashSet<>(blacklist);41 }42 43 public Set<String> getWhitelist() {44 return new HashSet<>(whitelist);45 }46 }47 48 public static void main(String[] args) {49 BlacklistSystem system = new BlacklistSystem();50 51 // 添加黑名单52 system.addToBlacklist("spam@example.com");53 system.addToBlacklist("malware.com");54 55 // 添加白名单56 system.addToWhitelist("trusted@company.com");57 system.addToWhitelist("partner.com");58 59 // 测试访问控制60 System.out.println("spam@example.com 允许: " + system.isAllowed("spam@example.com"));61 System.out.println("trusted@company.com 允许: " + system.isAllowed("trusted@company.com"));62 System.out.println("unknown@example.com 允许: " + system.isAllowed("unknown@example.com"));63 64 // 移除黑名单项目65 system.removeFromBlacklist("spam@example.com");66 System.out.println("移除黑名单后 spam@example.com 允许: " + system.isAllowed("spam@example.com"));67 }68}7. 最佳实践总结
7.1 Set实现类选择策略
选择建议
选择合适的Set实现类需要考虑以下因素：
- 性能要求：查找、插入、删除的性能需求
- 顺序要求：是否需要保持元素顺序
- 线程安全：是否在多线程环境下使用
- 内存约束：内存使用限制
- 功能需求：是否需要特殊功能（如导航方法）
| 实现类 | 适用场景 | 优势 | 劣势 |
|---|---|---|---|
| HashSet | 一般用途、去重 | 性能最好、内存效率高 | 无序、线程不安全 |
| LinkedHashSet | 需要保持插入顺序 | 保持顺序、性能好 | 内存开销稍大 |
| TreeSet | 需要有序、范围查询 | 有序、支持导航方法 | 性能较差、内存开销大 |
| CopyOnWriteArraySet | 读多写少、线程安全 | 线程安全、读性能好 | 写性能差、内存开销大 |
| EnumSet | 枚举类型 | 性能极高、内存效率最高 | 只能存储枚举 |
| ConcurrentSkipListSet | 并发有序Set | 线程安全、有序 | 性能中等 |
7.2 性能优化策略
Set性能优化示例
java
1public class SetPerformanceOptimization {2 3 /**4 * 预分配容量优化5 */6 public static void capacityOptimization() {7 // 知道大概元素数量时，预分配容量8 int expectedSize = 1000;9 Set<String> optimizedSet = new HashSet<>(expectedSize);10 11 // 避免频繁扩容12 for (int i = 0; i < expectedSize; i++) {13 optimizedSet.add("item" + i);14 }15 }16 17 /**18 * 批量操作优化19 */20 public static void batchOperationOptimization() {21 Set<String> set1 = new HashSet<>();22 Set<String> set2 = new HashSet<>();23 24 // 批量添加，比循环add效率高25 set1.addAll(set2);26 27 // 批量删除28 set1.removeAll(set2);29 30 // 保留交集31 set1.retainAll(set2);32 }33 34 /**35 * 元素类型优化36 */37 public static void elementTypeOptimization() {38 // 推荐：使用不可变对象39 Set<String> goodSet = new HashSet<>();40 41 // 不推荐：使用可变对象42 Set<StringBuilder> badSet = new HashSet<>();43 }44 45 /**46 * 遍历优化47 */48 public static void iterationOptimization() {49 Set<String> set = new HashSet<>();50 51 // 推荐：使用增强for循环52for (String item : set) {53 System.out.println(item);54}5556 // 推荐：使用forEach方法57 set.forEach(System.out::println);58 59 // 不推荐：使用迭代器（除非需要删除元素）60Iterator<String> iterator = set.iterator();61while (iterator.hasNext()) {62 String item = iterator.next();63 System.out.println(item);64 }65 }66}7.3 常见陷阱和解决方案
注意事项
- equals和hashCode一致性：自定义对象必须正确实现equals和hashCode方法
- 可变对象问题：避免使用可变对象作为Set元素
- 线程安全问题：在多线程环境下选择合适的线程安全实现
- null值处理：某些Set实现不支持null值
- 性能考虑：根据使用场景选择合适的实现类
常见陷阱示例
java
1public class SetCommonTraps {2 3 /**4 * equals和hashCode不一致陷阱5 */6 public static void equalsHashCodeTrap() {7 // 错误：equals和hashCode不一致8 Set<BadPerson> badSet = new HashSet<>();9 BadPerson p1 = new BadPerson("Alice", 25);10 BadPerson p2 = new BadPerson("Alice", 25);11 12 badSet.add(p1);13 badSet.add(p2); // 可能添加成功，因为hashCode不同14 15 System.out.println("BadSet大小: " + badSet.size()); // 可能是216 17 // 正确：equals和hashCode一致18 Set<GoodPerson> goodSet = new HashSet<>();19 GoodPerson p3 = new GoodPerson("Alice", 25);20 GoodPerson p4 = new GoodPerson("Alice", 25);21 22 goodSet.add(p3);23 goodSet.add(p4); // 不会添加，因为equals返回true24 25 System.out.println("GoodSet大小: " + goodSet.size()); // 126 }27 28 /**29 * 可变对象陷阱30 */31 public static void mutableObjectTrap() {32 Set<StringBuilder> set = new HashSet<>();33 StringBuilder sb = new StringBuilder("Hello");34 set.add(sb);35 36 System.out.println("添加前: " + set.contains(sb)); // true37 38 // 修改对象内容39 sb.append(" World");40 41 System.out.println("修改后: " + set.contains(sb)); // false42 System.out.println("Set内容: " + set);43 }44 45 /**46 * 线程安全陷阱47 */48 public static void threadSafetyTrap() {49 Set<String> set = new HashSet<>(); // 线程不安全50 51 // 错误：多线程访问52 Thread t1 = new Thread(() -> {53 for (int i = 0; i < 1000; i++) {54 set.add("Thread1-" + i);55 }56 });57 58 Thread t2 = new Thread(() -> {59 for (int i = 0; i < 1000; i++) {60 set.add("Thread2-" + i);61 }62 });63 64 // 正确：使用线程安全的Set65 Set<String> safeSet = new CopyOnWriteArraySet<>();66 // 或者使用 Collections.synchronizedSet(new HashSet<>())67 }68 69 static class BadPerson {70 private String name;71 private int age;72 73 public BadPerson(String name, int age) {74 this.name = name;75 this.age = age;76 }77 78 @Override79 public boolean equals(Object o) {80 if (this == o) return true;81 if (o == null || getClass() != o.getClass()) return false;82 BadPerson that = (BadPerson) o;83 return age == that.age && Objects.equals(name, that.name);84 }85 86 // 错误：hashCode与equals不一致87 @Override88 public int hashCode() {89 return Objects.hash(name); // 只使用name90 }91 }92 93 static class GoodPerson {94 private String name;95 private int age;96 97 public GoodPerson(String name, int age) {98 this.name = name;99 this.age = age;100 }101 102 @Override103 public boolean equals(Object o) {104 if (this == o) return true;105 if (o == null || getClass() != o.getClass()) return false;106 GoodPerson that = (GoodPerson) o;107 return age == that.age && Objects.equals(name, that.name);108 }109 110 // 正确：hashCode与equals一致111 @Override112 public int hashCode() {113 return Objects.hash(name, age); // 使用所有字段114 }115 }116}7.4 测试和调试建议
Set测试调试示例
java
1public class SetTestingDebugging {2 3 /**4 * 单元测试示例5 */6 public static void unitTestExample() {7 Set<String> set = new HashSet<>();8 9 // 测试添加操作10 assert set.isEmpty();11 set.add("test");12 assert set.size() == 1;13 assert set.contains("test");14 15 // 测试删除操作16 set.remove("test");17 assert set.isEmpty();18 19 System.out.println("所有测试通过");20 }21 22 /**23 * 性能测试示例24 */25 public static void performanceTestExample() {26 int size = 100000;27 28 // HashSet性能测试29 long start = System.currentTimeMillis();30 Set<Integer> hashSet = new HashSet<>();31 for (int i = 0; i < size; i++) {32 hashSet.add(i);33 }34 long hashSetTime = System.currentTimeMillis() - start;35 36 // TreeSet性能测试37 start = System.currentTimeMillis();38 Set<Integer> treeSet = new TreeSet<>();39 for (int i = 0; i < size; i++) {40 treeSet.add(i);41 }42 long treeSetTime = System.currentTimeMillis() - start;43 44 System.out.println("HashSet添加" + size + "个元素耗时: " + hashSetTime + "ms");45 System.out.println("TreeSet添加" + size + "个元素耗时: " + treeSetTime + "ms");46 }47 48 /**49 * 并发测试示例50 */51 public static void concurrentTestExample() {52 Set<String> set = new CopyOnWriteArraySet<>();53 int threadCount = 10;54 int operationsPerThread = 1000;55 56 // 创建多个线程并发操作57 Thread[] threads = new Thread[threadCount];58 for (int i = 0; i < threadCount; i++) {59 final int threadId = i;60 threads[i] = new Thread(() -> {61 for (int j = 0; j < operationsPerThread; j++) {62 set.add("Thread" + threadId + "-Item" + j);63 }64 });65 }66 67 // 启动所有线程68 for (Thread thread : threads) {69 thread.start();70 }71 72 // 等待所有线程完成73 for (Thread thread : threads) {74 try {75 thread.join();76 } catch (InterruptedException e) {77 e.printStackTrace();78 }79 }80 81 System.out.println("最终Set大小: " + set.size());82 System.out.println("期望大小: " + (threadCount * operationsPerThread));83 }84}8. 总结
Set接口作为Java集合框架的重要组成部分，提供了丰富多样的不重复元素集合实现，满足了不同场景下的需求。通过深入理解各种Set实现类的特性和使用场景，我们可以构建出高效、可靠的数据处理应用程序。
在实际开发中，需要综合考虑以下几个方面：
- 功能需求：根据业务需求选择合适的Set类型
- 性能要求：考虑查找、插入、删除性能
- 内存约束：考虑内存使用效率
- 线程安全：在多线程环境下选择合适的实现
- 顺序要求：是否需要保持元素顺序
通过合理使用Set集合，我们可以构建出高效、可靠的Java应用程序。
9. 面试题精选
9.1 基础概念题
Q: HashSet和TreeSet的区别是什么？
A: 主要区别包括：
- 底层实现：HashSet基于HashMap，TreeSet基于TreeMap
- 元素顺序：HashSet无序，TreeSet有序
- 性能特点：HashSet O(1)，TreeSet O(log n)
- null值支持：HashSet允许null，TreeSet不允许null
- 使用场景：HashSet适合一般用途，TreeSet适合需要排序的场景
Q: HashSet如何保证元素唯一性？
A: HashSet保证元素唯一性的机制：
- 哈希算法：计算元素的哈希值确定存储位置
- equals比较：哈希值相同时使用equals方法比较
- 不添加重复：如果元素已存在则不添加
- 依赖实现：要求元素正确实现equals和hashCode方法
9.2 性能优化题
Q: 如何优化Set的性能？
A: 主要优化策略：
- 预分配容量：使用带初始容量的构造函数
- 批量操作：使用addAll()而非循环add()
- 选择合适的实现类：根据使用场景选择最合适的Set
- 避免频繁扩容：合理设置初始容量
- 使用不可变对象：避免使用可变对象作为元素
Q: 什么场景下选择TreeSet？
A: TreeSet适用场景：
- 需要元素有序的场景
- 需要范围查询的场景
- 需要获取最大最小元素的场景
- 需要按顺序遍历的场景
- 需要导航方法的场景
9.3 实践应用题
Q: 如何实现线程安全的Set操作？
A: 线程安全方案：
- 使用CopyOnWriteArraySet：读多写少场景
- 使用ConcurrentSkipListSet：需要有序的并发场景
- Collections.synchronizedSet()：包装现有Set
- 外部同步：使用synchronized或Lock
- 并发集合：考虑使用ConcurrentHashMap.keySet()
Q: 如何处理Set中的自定义对象？
A: 处理方案：
- 正确实现equals和hashCode：保证一致性
- 使用不可变对象：避免可变对象问题
- 实现Comparable接口：用于TreeSet排序
- 提供Comparator：自定义排序规则
- 考虑性能影响：复杂对象的比较开销
Q: Set的遍历方式有哪些？
A: 遍历方式：
- 增强for循环：
for (E item : set) - 迭代器：
Iterator<E> iterator = set.iterator() - forEach方法：
set.forEach(System.out::println) - Stream API：
set.stream().forEach(System.out::println) - 并行流：
set.parallelStream().forEach(System.out::println)
9.4 高级应用题
Q: 如何实现一个自定义的Set？
A: 实现步骤：
- 继承AbstractSet：实现基本的Set操作
- 实现核心方法：add、remove、contains、size等
- 保证元素唯一性：实现去重逻辑
- 考虑性能优化：选择合适的底层数据结构
- 实现迭代器：支持遍历操作
Q: EnumSet的优势和应用场景？
A: 优势和场景：
- 性能极高：基于位向量实现
- 内存效率：使用位运算，内存占用极小
- 类型安全：只能存储枚举类型
- 应用场景：权限管理、状态标记、配置选项
- 创建方式：allOf、noneOf、range、of等方法
Q: LinkedHashSet的实现原理？
A: 实现原理：
- 继承HashSet：复用HashSet的所有功能
- LinkedHashMap：底层使用LinkedHashMap而非HashMap
- 双向链表：维护元素的插入顺序
- 性能平衡：在HashSet高性能基础上增加顺序维护
- 构造方法：调用HashSet的特定构造方法
面试要点
- 理解底层实现：掌握各种Set的内部结构和工作原理
- 性能分析：能够分析不同操作的时间复杂度
- 场景选择：根据具体需求选择合适的Set实现
- 线程安全：理解线程安全和并发控制机制
- 最佳实践：了解常见陷阱和优化策略
通过本章的学习，你应该已经掌握了Java Set集合的核心概念、实现原理和最佳实践。Set是Java数据处理和算法实现的重要基础，深入理解其特性和使用场景，对于编写高效、可靠的Java程序至关重要。
评论