集合（Set）
在计算机数据结构中，集合（Set） 是一种由无序且唯一的元素组成的数据结构，其核心特性是元素不可重复，且不支持通过索引访问（因无序性）。它的设计目标是高效地实现元素的插入、删除和查找操作，同时天然支持集合间的数学运算（如并集、交集、差集等）。
一、集合的核心特性
- 唯一性：集合中不会存在重复元素，插入重复元素时会被自动忽略。
- 无序性：元素在集合中没有固定顺序，不能通过索引（如
[0]）访问（有序集合除外）。 - 高效性：基于哈希表或树的实现，使基本操作（插入、删除、查找）的时间复杂度通常为
O(1)（哈希实现）或O(log n)（树实现）。
二、集合的基本操作
常见操作及说明：
add(element)：向集合中添加元素（若元素已存在则不执行）。remove(element)：删除集合中的指定元素（若不存在则可能报错或返回false）。contains(element)：判断元素是否在集合中（返回boolean）。size()：返回集合中元素的个数。clear()：清空集合中的所有元素。- 集合运算：
union(set2)（并集）、intersection(set2)（交集）、difference(set2)（差集）等。
三、集合的实现方式
集合的实现依赖于底层数据结构，常见有两种主流方式：
1. 基于哈希表的实现（无序集合）
如 Java 中的HashSet、Python 中的set，核心是利用哈希表（Hash Table）的特性：
- 原理：通过哈希函数将元素映射到哈希表的索引位置，利用哈希表的“键唯一”特性保证集合元素的唯一性。
- 特性：无序，插入/删除/查找的平均时间复杂度为
O(1)（哈希冲突时可能退化，但实际应用中极少）。 - 适用场景：无需关注元素顺序，仅需去重或快速判断元素是否存在（如用户 ID 去重、关键词过滤）。
2. 基于树的实现（有序集合）
如 Java 中的TreeSet、C++中的set，底层通常是红黑树（一种自平衡二叉搜索树）：
- 原理：元素按特定规则（自然顺序或自定义比较器）排序，通过树结构保证有序性和唯一性。
- 特性：有序（可按规则遍历），插入/删除/查找的时间复杂度为
O(log n)。 - 适用场景：需要对元素进行排序或范围查询（如按分数排序的学生 ID 集合、查询某个区间内的元素）。
四、集合的应用场景
- 去重处理：快速去除列表中重复的元素（如将
[1,2,2,3]转为集合后得到{1,2,3}）。 - 集合运算：
- 交集（共同元素）：如求两个班级学生的共同成员、两个用户群体的共同好友。
- 并集（合并元素）：如合并两个日志文件中的所有唯一 ID。
- 差集（独有元素）：如统计“仅 A 平台有而 B 平台没有的用户”。
- 快速查找：判断元素是否存在（如检测用户是否已注册、关键词是否在敏感词库中），效率远高于列表的线性查找（
O(n)）。
五、与其他数据结构的区别
- 与列表（List）：列表有序可重复，支持索引访问；集合无序不可重复，无索引。
- 与映射（Map）：集合可视为“只有键没有值”的映射。例如 Java 的
HashSet底层基于HashMap实现，用键存储元素，值为固定空对象。
总结
集合的核心价值是保证元素唯一性和高效的操作效率，其实现方式（哈希/树）决定了是否有序。根据场景选择无序集合（追求效率）或有序集合（需要排序），能极大提升数据处理的性能。