# 并叉集
# Hash 集
哈希集(Hash Set)是基于哈希表实现的一种数据结构,主要用于存储不重复的元素集合。它提供了高效的元素查找、插入和删除操作。哈希集的核心思想是使用一个哈希函数将集合中的每个元素映射到哈希表的一个位置(称为 “槽” 或 “桶”),以便快速访问。
# 哈希集的特点
- 唯一性:哈希集中不允许存储重复的元素。
- 无序性:元素在哈希集中的存储位置是根据哈希函数计算得出的,因此元素的存储顺序并不是按照插入顺序排列的。
- 高效性:在理想情况下,哈希集可以提供接近常数时间复杂度的元素查找、插入和删除操作。
# 哈希集的操作
- 插入:将新元素添加到哈希集中。如果该元素已经存在,则操作失败或不进行任何操作。
- 查找:检查某个元素是否存在于哈希集中。
- 删除:从哈希集中移除一个元素。
# 哈希冲突
当两个或多个元素通过哈希函数映射到哈希表的同一个位置时,就发生了哈希冲突。为了解决哈希冲突,有几种常见的策略:
- 开放寻址法:当发生冲突时,探查哈希表中的下一个空槽,并将元素插入其中。
- 链地址法(分离链接法):每个哈希表的槽指向一个链表,所有映射到同一个位置的元素都存储在这个链表中。
#include <iostream> | |
#include <unordered_set> | |
using namespace std; | |
int main() { | |
unordered_set<int> hashSet; | |
// 插入元素 | |
hashSet.insert(1); | |
hashSet.insert(2); | |
hashSet.insert(3); | |
hashSet.insert(1); // 重复插入,集合中仍然只会有一个 1 | |
// 检查元素是否存在 | |
if (hashSet.find(2) != hashSet.end()) { | |
cout << "2 is found in the hash set." << endl; | |
} | |
// 删除元素 | |
hashSet.erase(2); | |
if (hashSet.find(2) == hashSet.end()) { | |
cout << "2 is not found after being erased." << endl; | |
} | |
return 0; | |
} |