集合数据结构之哈希集、有序集合

一、集合（Set）

1. 定义

集合是一种无序的数据结构，主要用于存储不重复的元素。集合中的元素不能重复，因此适合用于需要唯一性的数据场景。集合提供了常用的操作，如添加、删除和检查元素是否存在。

2. 特点

• 唯一性：集合中不允许有重复元素。
• 无序性：集合中的元素没有特定的顺序。
• 高效性：集合通常提供高效的元素查找、插入和删除操作。

3. 应用场景

• 数据去重：从列表中去除重复元素。
• 集合运算：进行并集、交集、差集等集合运算。
• 快速查找：检查元素是否存在于数据集中。

---

二、哈希集（Hash Set）

1. 定义

哈希集是一种基于哈希表实现的集合，使用哈希函数将元素映射到哈希表的索引。由于哈希集依赖哈希函数，查找、插入和删除操作的平均时间复杂度为 O(1)。

2. 特点

• 快速操作：由于哈希表的特性，基本操作（如添加、删除和查找）的时间复杂度为 O(1)。
• 无序性：元素的存储没有顺序，不会按照插入的顺序排列。
• 动态扩展：当元素数量超过一定阈值时，哈希集会自动扩展以保持性能。

3. 优缺点

• 优点：
  • 高效性：适合快速查找和插入操作。
  • 简单性：易于实现和使用。
• 缺点：
  • 无序性：不支持按顺序遍历元素。
  • 内存消耗：可能会有额外的内存开销，因为需要存储哈希表。

4. 应用场景

• 去重操作：在处理数据时快速去除重复元素。
• 快速查找：需要频繁查找元素的场景，如缓存实现。

5. 示例代码（Java 实现哈希集）

import java.util.HashSet;public class HashSetExample {public static void main(String[] args) {HashSet<String> hashSet = new HashSet<>();// 添加元素hashSet.add("Apple");hashSet.add("Banana");hashSet.add("Orange");hashSet.add("Banana"); // 重复元素，不会被添加// 打印集合System.out.println("哈希集中的元素: " + hashSet);// 检查元素是否存在System.out.println("是否包含 Apple? " + hashSet.contains("Apple"));// 删除元素hashSet.remove("Banana");System.out.println("删除 Banana 后的元素: " + hashSet);}
}

三、有序集合（Sorted Set）

1. 定义

有序集合是一种能够保持元素有序的集合，通常基于红黑树或其他排序算法实现。Java 中的 TreeSet 是一个典型的有序集合实现。

2. 特点

• 排序性：元素根据自然顺序或自定义比较器进行排序。
• 无重复元素：与一般集合相同，有序集合也不允许重复元素。
• 范围查找：可以有效地执行范围查询，查找某一范围内的元素。

3. 优缺点

• 优点：
  • 有序性：能够按照顺序访问元素，适合需要排序的应用场景。
  • 范围查询：支持高效的范围查询操作。
• 缺点：
  • 性能开销：插入和删除操作的时间复杂度为 O(log⁡n)，比哈希集稍慢。
  • 内存消耗：相对于哈希集，有序集合通常需要更多的内存来维护顺序。

4. 应用场景

• 排序数据存储：需要保持元素有序的情况，如排行榜、优先队列。
• 范围查询：如查找某一范围内的数值。

5. 示例代码（Java 实现有序集合）

import java.util.TreeSet;public class SortedSetExample {public static void main(String[] args) {TreeSet<Integer> sortedSet = new TreeSet<>();// 添加元素sortedSet.add(5);sortedSet.add(3);sortedSet.add(8);sortedSet.add(1);sortedSet.add(3); // 重复元素，不会被添加// 打印集合System.out.println("有序集合中的元素: " + sortedSet);// 范围查询System.out.println("小于 5 的元素: " + sortedSet.headSet(5));System.out.println("大于 3 的元素: " + sortedSet.tailSet(3));}
}

总结比较

集合类型	特点	操作复杂度	应用场景
哈希集 (Hash Set)	元素无序，不允许重复，快速查找和插入	添加、删除、查找：O(1)	去重、快速查找
有序集合 (Sorted Set)	元素有序，不允许重复	添加、删除、查找：O(log⁡n)	排序存储、范围查询