C++ unordered_set使用哈希集合实现（集合.unordered_set...）

C++ unordered_set基于哈希表实现，提供平均O(1)的插入、查找和删除操作，不保证元素顺序。它使用哈希函数将元素映射到桶中，采用链地址法解决冲突，默认使用std::hash，支持自定义哈希函数。当负载因子超过阈值（默认1.0）时触发rehash，可通过reserve预分配空间优化性能。相比set的O(log n)操作和有序存储，unordered_set更适合无需排序且追求高效存取的场景。

c++ unordered_set使用哈希集合实现

C++

unordered_set

使用哈希表实现，提供快速的元素查找、插入和删除操作。它不保证元素的特定顺序，但提供接近常数时间的平均复杂度。

哈希集合实现

unordered_set

是一个关联容器，它存储唯一元素的集合，并且允许快速查找元素。其底层实现基于哈希表，这意味着元素通过哈希函数映射到桶（buckets）中。

基本操作：

插入 (insert): 计算元素的哈希值，找到对应的桶，并将元素添加到桶中。如果桶中已经存在相同的元素，则插入失败（因为
```
unordered_set
```
只存储唯一元素）。
查找 (find): 计算元素的哈希值，找到对应的桶，然后在桶中搜索该元素。
删除 (erase): 计算元素的哈希值，找到对应的桶，然后在桶中删除该元素。
计数 (count): 计算元素的哈希值，找到对应的桶，然后在桶中检查该元素是否存在。返回 1 如果存在，否则返回 0。

哈希冲突：

由于哈希函数可能将不同的元素映射到同一个桶中，因此哈希冲突是不可避免的。

unordered_set

通常使用以下方法解决哈希冲突：

链地址法 (Separate Chaining): 每个桶存储一个链表（或其他数据结构）来存储所有哈希到该桶的元素。这是
```
unordered_set
```
最常用的冲突解决策略。
开放寻址法 (Open Addressing): 当发生冲突时，尝试寻找下一个可用的桶来存储元素。

unordered_set

通常使用链地址法，因为它实现简单，且在负载因子（元素数量与桶数量的比率）较低时，性能表现良好。

代码示例：

#include <iostream>
#include <unordered_set>

int main() {
  std::unordered_set<int> mySet;

  // 插入元素
  mySet.insert(10);
  mySet.insert(20);
  mySet.insert(30);
  mySet.insert(20); // 插入重复元素，不会生效

  // 查找元素
  if (mySet.find(20) != mySet.end()) {
    std::cout << "20 found in the set" << std::endl;
  } else {
    std::cout << "20 not found in the set" << std::endl;
  }

  // 删除元素
  mySet.erase(20);

  // 再次查找元素
  if (mySet.find(20) != mySet.end()) {
    std::cout << "20 found in the set" << std::endl;
  } else {
    std::cout << "20 not found in the set" << std::endl;
  }

  // 遍历集合
  std::cout << "Set elements: ";
  for (const int& element : mySet) {
    std::cout << element << " ";
  }
  std::cout << std::endl;

  return 0;
}

unordered_set

的性能高度依赖于哈希函数和负载因子。一个好的哈希函数应该尽可能地将元素均匀地分布到不同的桶中，以减少哈希冲突。当负载因子过高时，

unordered_set

会自动进行 rehash 操作，增加桶的数量，以降低负载因子并提高性能。

unordered_set

相比于

set

的优势在于其平均时间复杂度为 O(1) 的查找、插入和删除操作，而

set

的时间复杂度为 O(log n)。但是，

unordered_set

不保证元素的顺序，而

set

则按照元素的排序顺序存储元素。

C++ unordered_set 的哈希函数是如何工作的？

unordered_set

使用一个哈希函数将元素映射到桶。默认情况下，

unordered_set

使用

std::hash

作为哈希函数。

std::hash

针对内置类型（如

int

、

float

、

string

等）提供了默认的哈希函数实现。

对于自定义类型，你需要提供自己的哈希函数。这可以通过以下两种方式实现：

重载
```
std::hash
```
模板：为你的自定义类型特化
```
std::hash
```
模板。
提供自定义的哈希函数对象：创建一个类或结构体，重载
```
operator()
```
，并将其作为
```
unordered_set
```
的模板参数传递。

示例：自定义类型的哈希函数

#include <iostream>
#include <unordered_set>

struct MyStruct {
  int x;
  int y;

  bool operator==(const MyStruct& other) const {
    return x == other.x && y == other.y;
  }
};

// 方法 1: 重载 std::hash 模板
namespace std {
  template <>
  struct hash<MyStruct> {
    size_t operator()(const MyStruct& s) const {
      // 一个简单的哈希函数，可以将 x 和 y 的值组合起来
      return ((hash<int>()(s.x) ^ (hash<int>()(s.y) << 1)) >> 1);
    }
  };
}

// 方法 2: 提供自定义的哈希函数对象
struct MyStructHash {
  size_t operator()(const MyStruct& s) const {
    return ((std::hash<int>()(s.x) ^ (std::hash<int>()(s.y) << 1)) >> 1);
  }
};

int main() {
  // 使用重载的 std::hash
  std::unordered_set<MyStruct> mySet1;
  mySet1.insert({1, 2});
  mySet1.insert({3, 4});

  // 使用自定义的哈希函数对象
  std::unordered_set<MyStruct, MyStructHash> mySet2;
  mySet2.insert({5, 6});
  mySet2.insert({7, 8});

  return 0;
}

哈希函数的设计原则：

均匀分布：哈希函数应该尽可能地将元素均匀地分布到不同的桶中，以减少哈希冲突。
高效性：哈希函数的计算应该尽可能地高效，以避免成为性能瓶颈。
避免碰撞：理想情况下，哈希函数应该为不同的元素生成不同的哈希值，但实际上这是不可能的。一个好的哈希函数应该尽可能地减少碰撞的概率。

选择合适的哈希函数对于

unordered_set

的性能至关重要。如果哈希函数设计不当，可能会导致大量的哈希冲突，从而降低

unordered_set

的性能，甚至使其退化为 O(n) 的时间复杂度。

C++ unordered_set 何时进行 rehash？

PIA

全面的AI聚合平台，一站式访问所有顶级AI模型

226 查看详情 PIA

unordered_set

会在以下情况下进行 rehash 操作：

当负载因子超过最大负载因子时：负载因子是指
```
unordered_set
```
中元素的数量与桶的数量的比率。最大负载因子是一个阈值，当负载因子超过该阈值时，
```
unordered_set
```
会自动进行 rehash 操作，增加桶的数量，以降低负载因子并提高性能。默认情况下，
```
unordered_set
```
的最大负载因子为 1.0。可以使用
```
max_load_factor()
```
方法获取或设置最大负载因子。
显式调用
```
rehash()
```
方法：可以手动调用
```
rehash()
```
方法来强制
```
unordered_set
```
进行 rehash 操作。这通常在你知道
```
unordered_set
```
将要存储大量的元素时使用，以避免在插入元素时频繁地进行 rehash 操作。

Rehash 的过程：

Rehash 的过程包括以下步骤：

分配新的桶：分配一个新的桶数组，其大小通常是当前桶数量的 2 倍或更大。
重新计算哈希值：遍历
```
unordered_set
```
中的所有元素，并使用新的桶数量重新计算它们的哈希值。
将元素移动到新的桶：将所有元素移动到新的桶中。
释放旧的桶：释放旧的桶数组。

Rehash 是一个耗时的操作，因为它需要遍历

unordered_set

中的所有元素并重新计算它们的哈希值。因此，应该尽量避免频繁地进行 rehash 操作。

示例：控制 rehash

#include <iostream>
#include <unordered_set>

int main() {
  std::unordered_set<int> mySet;

  // 设置最大负载因子
  mySet.max_load_factor(0.5);

  // 预留足够的空间，以减少 rehash 的次数
  mySet.reserve(1000);

  // 插入大量元素
  for (int i = 0; i < 1000; ++i) {
    mySet.insert(i);
  }

  std::cout << "Load factor: " << mySet.load_factor() << std::endl;
  std::cout << "Bucket count: " << mySet.bucket_count() << std::endl;

  return 0;
}

通过设置最大负载因子和预留足够的空间，可以有效地控制

unordered_set

的 rehash 行为，从而提高其性能。

C++ unordered_set 和 set 的区别是什么？

unordered_set

和

set

都是 C++ 标准库中用于存储唯一元素的容器，但它们在底层实现、元素顺序和性能方面存在显著差异。

底层实现：

```
unordered_set
```
: 基于哈希表实现。
```
set
```
: 基于红黑树（一种自平衡二叉搜索树）实现.

元素顺序：

```
unordered_set
```
: 不保证元素的任何特定顺序。元素在内存中的存储顺序取决于哈希函数和哈希冲突的解决策略。
```
set
```
: 元素按照排序顺序存储。默认情况下，使用
```
<
```
运算符进行排序，但也可以提供自定义的比较函数。

性能：

操作 @@######@@ (平均) @@######@@ (平均) 插入 (insert) O(1) O(log n) 查找 (find) O(1) O(log n) 删除 (erase) O(1) O(log n)

```
unordered_set
```
: 在平均情况下，插入、查找和删除操作的时间复杂度为 O(1)。但在最坏情况下（例如，所有元素都哈希到同一个桶中），时间复杂度可能退化为 O(n)。
```
set
```
: 插入、查找和删除操作的时间复杂度为 O(log n)。

内存占用：

```
unordered_set
```
: 通常比
```
set
```
占用更多的内存，因为它需要额外的空间来存储哈希表。
```
unordered_set
```
: 内存占用相对较少，因为它只需要存储元素和红黑树的节点信息。

使用场景：

```
set
```
: 适用于需要快速查找、插入和删除元素，并且不关心元素顺序的场景。例如，去重、统计元素出现次数等。
```
set
```
: 适用于需要按照排序顺序存储元素，并且需要进行范围查找等操作的场景。例如，维护一个有序的排行榜、实现一个字典等。

总结：

特性 @@######@@ @@######@@ 底层实现哈希表红黑树元素顺序无序有序查找、插入、删除 O(1) (平均) O(log n) 内存占用较高较低

选择

unordered_set

还是

set

取决于具体的应用场景和性能需求。如果需要快速的查找、插入和删除操作，并且不关心元素的顺序，那么

unordered_set

是一个更好的选择。如果需要按照排序顺序存储元素，并且需要进行范围查找等操作，那么

set

是一个更好的选择。

unordered_set

set

unordered_set

set

以上就是C++ unordered_set使用哈希集合实现的详细内容，更多请关注知识资源分享宝库其它相关文章！

相关标签： c++ ai ios 区别内存占用标准库 red String Float 运算符 count 结构体 int 数据结构 operator 对象大家都在看： C++如何使用模板实现迭代器类 C++如何处理复合对象中的嵌套元素 C++内存模型与编译器优化理解 C++如何使用ofstream和ifstream组合操作文件 C++循环与算法优化提高程序执行效率