C++ unordered_set使用哈希集合实现-C++-PHP中文网

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）中。

基本操作：

立即学习“C++免费学习笔记（深入）”；

插入 (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？

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;
}

登录后复制

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