java溯本求源之基础(二十八)--Set集合详解

1、Set接口概述

1.1. Set接口的定义

Set是一个集合接口，继承自Collection接口，主要特点如下：

• 无序性：Set集合中的元素是无序的，不保证元素插入时的顺序。即使添加元素的顺序不一定等于遍历顺序。

元素唯一性：Set中的元素不允许重复。不同于List，Set会通过对象的hashCode()和equals()方法判断是否已存在相同的元素。如果存在重复元素，add()方法会返回false。

Set<String> set = new HashSet<>();
set.add("Java");
set.add("Python");
set.add("Java"); // 重复元素，不加入
System.out.println(set); // 输出：[Java, Python]

1.2 Set接口的继承结构

Set接口是Collection接口的子接口，它有多个实现类。常见的实现类有：

• HashSet：基于哈希表实现，元素无序，查找、插入和删除操作效率高。
• LinkedHashSet：基于哈希表和双向链表实现，元素按插入顺序排列。
• TreeSet：基于红黑树实现，支持有序存储，元素按自然顺序或指定Comparator排序。
• EnumSet：专门用于存储枚举类型元素，性能优越。
• CopyOnWriteArraySet：基于CopyOnWriteArrayList实现，线程安全。
• ConcurrentSkipListSet：基于跳表实现，支持并发操作，并保持元素有序。

1.3. Set接口的常用方法

• add(E e)：添加元素到集合中。如果元素已存在，返回false。
• remove(Object o)：从集合中删除指定元素。
• contains(Object o)：判断集合中是否包含指定元素。
• size()：返回集合中的元素个数。
• isEmpty()：判断集合是否为空。
• clear()：清空集合中的所有元素。
• iterator()：返回集合的迭代器，用于遍历集合。

Set<String> set = new HashSet<>();
set.add("Java");
set.add("Python");
System.out.println(set.contains("Java")); // 输出：true
System.out.println(set.size()); // 输出：2
set.remove("Java");
System.out.println(set.contains("Java")); // 输出：false

1.4. Set的应用场景

Set集合适用于以下场景：

• 去重操作：通过Set可以轻松去除重复元素，确保集合中的每个元素都是唯一的。
• 快速查找：Set基于哈希表存储，查找效率较高，适合频繁查找的场景。
• 集合运算：如交集、并集、差集等操作，Set提供了非常便捷的API来处理这些需求。

 2、Set接口的实现类详解 —— HashSet

2.1. HashSet的存储结构

在 JDK 8 中，HashSet 是基于 HashMap 实现的，所有的元素都作为 HashMap 的键存储，值则是一个固定的常量对象 PRESENT。其存储结构大致如下：

• 内部通过一个哈希表（数组+链表+红黑树）实现。
• 元素存储时会根据其 hashCode() 方法计算哈希值，将其分配到哈希表的某个桶（bucket）中。
• 在 JDK 8 中，当链表长度超过 8 且桶内元素总数超过 64 时，会将链表转换为红黑树，从而优化查找性能。

private transient HashMap<E,Object> map;// 一个常量对象，用于填充 HashMap 的值
private static final Object PRESENT = new Object();

2.2. 线程安全性

HashSet 本身不是线程安全的。如果在多线程环境下需要使用 HashSet，需要额外的同步措施，比如使用 Collections.synchronizedSet() 方法来包装：

Set<String> synchronizedSet = Collections.synchronizedSet(new HashSet<>());

或者，直接使用线程安全的集合类，例如 ConcurrentSkipListSet。

2.3. HashSet的主要特点

• 无序性：存储元素的顺序不受插入顺序的影响，输出顺序可能是随机的。
• 唯一性：HashSet 使用 hashCode() 和 equals() 方法来判断元素的唯一性。
• 支持null值：在 JDK 8 中，HashSet 允许存储一个 null 元素。
• 性能：插入、删除和查找的时间复杂度为 O(1)（理想情况下，哈希冲突少）。

2.4. HashSet的适用场景

• 快速去重：适合存储不重复的集合，例如用户 ID 集合。
• 高效查找：可以在大数据量下高效地判断元素是否存在。

        在 JDK 8 中，桶内元素使用链表存储。当链表长度超过 8 且总桶数量超过 64 时，链表转换为红黑树。

3、Set接口的实现类详解 —— LinkedHashSet

3.1. LinkedHashSet的存储结构

        在 JDK 8 中，LinkedHashSet 是 HashSet 的子类，其存储结构基于 LinkedHashMap 实现，主要通过双向链表维护元素的插入顺序。

• 哈希表：通过哈希表快速定位元素。
• 双向链表：每个元素还会维护一个前驱和后继节点，用于记录插入顺序，从而保证遍历顺序与插入顺序一致。

        由于 LinkedHashSet 是通过链表维护顺序的，其性能比 HashSet 略低，尤其在插入和删除操作时需要额外维护链表。

3.2. 线程安全性
        同样地，LinkedHashSet 本身并不是线程安全的

3.3. LinkedHashSet的主要特点

• 有序性：元素的存储顺序与插入顺序一致。
• 唯一性：LinkedHashSet 使用 hashCode() 和 equals() 方法判断元素唯一性，与 HashSet 相同。
• 支持null值：允许存储一个 null 元素。
• 性能：由于维护链表，其插入和删除操作性能略低于 HashSet。

3.4. LinkedHashSet的适用场景

• 需要去重但保留插入顺序的场景：如记录按顺序存储的唯一访问日志。
• 高效遍历有序集合：相较于 TreeSet，LinkedHashSet 不排序，性能更高。

3.5. LinkedHashSet的优缺点

优点	缺点
保证插入顺序，方便遍历	内存占用较高，维护链表需要额外的开销
操作方法与 HashSet 一致，使用简单	插入和删除操作性能略低于 HashSet
可以高效处理有序且唯一的集合场景	不支持并发访问，需手动同步或使用线程安全集合

4、Set接口的实现类详解 —— CopyOnWriteArraySet

4.1. CopyOnWriteArraySet的存储结构

  CopyOnWriteArraySet 是基于 CopyOnWriteArrayList 实现的线程安全集合。它的核心思想是“写时复制”，即每次修改集合（如插入、删除）时，都会创建一个新的底层数组，并将修改后的数据复制到新数组中。

• 存储方式：内部使用 CopyOnWriteArrayList 存储元素。
• 去重实现：通过检查数组中是否已经包含该元素，来保证元素的唯一性。

private final CopyOnWriteArrayList<E> al;

4.2. 线程安全性

CopyOnWriteArraySet 是线程安全的集合实现，适合多线程环境下的读操作较多、写操作较少的场景。由于“写时复制”的机制，所有的写操作（如 add, remove）都会创建新的数组，因此在写操作频繁时效率较低。

4.3. CopyOnWriteArraySet的主要特点

• 线程安全：通过写时复制实现线程安全，适合读多写少的场景。
• 有序性：CopyOnWriteArraySet 保留插入元素的顺序，与插入顺序一致。
• 唯一性：通过调用底层 CopyOnWriteArrayList 的 contains 方法，判断元素是否已经存在。
• 性能：
  • 读操作性能高，因为底层数组在写操作时被复制，不会影响读线程。
  • 写操作性能较低，因为每次写操作都需要复制整个数组。

4.4. CopyOnWriteArraySet的适用场景

• 读多写少的并发场景：如缓存、订阅者列表等。
• 需要线程安全的集合：但对写操作性能要求不高

4.5. CopyOnWriteArraySet的优缺点

优点	缺点
线程安全，适合多线程环境	写操作性能较低，复制数组耗费时间和内存
读操作性能高，写操作不会阻塞读线程	占用更多内存空间，因为每次写操作都复制数组
保留插入顺序，使用简单	不适合写操作频繁的场景

5、Set接口的实现类详解 —— ConcurrentSkipListSet

5.1. ConcurrentSkipListSet的存储结构

ConcurrentSkipListSet 是基于跳表（Skip List）实现的线程安全有序集合。

• 存储方式：内部使用跳表（类似于多级链表结构）来存储元素。
• 排序方式：
  • 默认根据元素的自然顺序排序（要求元素实现 Comparable 接口）。
  • 可以通过构造方法传入自定义的 Comparator 来实现自定义排序。

5.2. 线程安全性

ConcurrentSkipListSet 是线程安全的集合，支持高效的并发访问。它通过分段锁的机制允许多个线程同时访问集合，不同于 CopyOnWriteArraySet 的写时复制机制。

5.3. ConcurrentSkipListSet的主要特点

• 线程安全：多线程环境下，能够安全、高效地执行读写操作。
• 有序性：集合中的元素始终按照自然顺序或自定义顺序排列。
• 唯一性：通过 compareTo 或 Comparator 判断元素的唯一性。
• 性能：
  • 读写性能较高，适合频繁插入、删除的并发场景。
  • 插入、删除和查找的时间复杂度为 O(log n)。

5.4. ConcurrentSkipListSet的适用场景

• 需要排序的并发场景：如排行榜、优先级队列等。
• 需要线程安全的有序集合：适合对插入、删除和查找操作都比较频繁的场景。

5.5. ConcurrentSkipListSet的优缺点

优点	缺点
线程安全，适合高并发环境	内存占用高于基于数组实现的集合结构
有序性支持，适合需要排序的场景	性能略低于无序的集合结构（如 HashSet）
读写操作性能较高，适合插入和删除频繁的场景	不支持存储 null 元素

6.自定义对象去重

        当集合中存储的是自定义对象时，为了实现去重功能，必须正确重写 hashCode 和 equals 方法

7. Set的注意事项

• null 值处理：

  • HashSet 和 LinkedHashSet 支持一个 null 元素。
  • TreeSet 和 ConcurrentSkipListSet 不支持 null 元素。

• 自定义对象的去重规则：

  • 确保 hashCode 和 equals 方法一致性。
  • hashCode 的返回值应尽量均匀分布，避免哈希冲突。

• 线程安全问题：

  • 如果需要线程安全，可以使用 Collections.synchronizedSet 包装一个 Set，或直接使用并发集合如 CopyOnWriteArraySet 和 ConcurrentSkipListSet。

8、总结

8.1. Set接口实现类的总结

实现类	特点	线程安全性	存储结构	适用场景
HashSet	无序、唯一、效率高	非线程安全	哈希表	高效的无序集合，适用于普通单线程场景
LinkedHashSet	有序（按插入顺序）、唯一	非线程安全	哈希表 + 双向链表	需要按插入顺序遍历的场景，如缓存、存储日志
TreeSet	有序、唯一（自然排序或自定义排序）	非线程安全	红黑树	需要有序操作的场景，如排行榜、集合排序操作
CopyOnWriteArraySet	线程安全、适合读多写少	线程安全	CopyOnWriteArrayList	读多写少的场景，如事件监听器、订阅者模式
ConcurrentSkipListSet	线程安全、有序（自然排序或自定义排序）	线程安全	跳表 (Skip List)	需要高并发和有序操作的场景，如优先级队列、并发集合操作

8.2. 各实现类的适用场景

• HashSet：
  • 适用于不关心元素顺序的普通集合操作，能提供较高的性能，常用于需要去重的场景，如记录日志的唯一性检测。
• LinkedHashSet：
  • 如果需要保持元素的插入顺序，可以使用 LinkedHashSet。它非常适合缓存、历史记录管理等场景。
• TreeSet：
  • 当你需要对集合中的元素进行排序时，TreeSet 是一个很好的选择。它可以用于排序、查找区间值等场景。
• CopyOnWriteArraySet：
  • 适用于多线程环境中，读取操作频繁且写入操作相对较少的场景。例如，当事件源或发布者频繁向集合中添加/删除元素时，可以使用它。
• ConcurrentSkipListSet：
  • 当你需要同时支持排序和并发操作时，ConcurrentSkipListSet 是理想的选择。它适合用在并发场景下的高效数据结构，尤其是在元素频繁插入/删除并且需要保持有序时。

8.3. 选择合适的实现类

选择合适的 Set 实现类，应该根据具体需求来判断。以下是一些常见的最佳实践：

• 性能要求：

  • 如果对性能要求较高，且不关心元素的顺序，HashSet 是最佳选择。
  • 如果需要保证元素顺序，并且不关心排序，使用 LinkedHashSet。
  • 如果需要排序，且可以容忍一定的性能开销，可以使用 TreeSet。

• 线程安全：

  • 如果在多线程环境下使用 Set，且不希望手动加锁，CopyOnWriteArraySet 或 ConcurrentSkipListSet 是线程安全的集合类。
  • 如果使用 HashSet 或 LinkedHashSet，可以使用 Collections.synchronizedSet 来使其线程安全，但它依赖于显式同步，可能会影响性能。

• 有序性需求：

  • 当需要排序时，TreeSet 和 ConcurrentSkipListSet 都可以提供自然顺序或自定义顺序的排序功能。
  • 如果需要在多线程环境下使用有序集合，ConcurrentSkipListSet 是更好的选择。

• 内存和性能平衡：

  • 对于需要频繁读取且数据量较大的情况，CopyOnWriteArraySet 提供了很高的读取性能，但写入性能较差，适合读多写少的场景。
  • 对于频繁修改集合内容的场景，建议使用 ConcurrentSkipListSet 或者 HashSet。