C++ unordered_set用法 哈希集合实现详解

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

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

1. 重载 std::hash 模板： 为你的自定义类型特化 std::hash 模板。
2. 提供自定义的哈希函数对象： 创建一个类或结构体，重载 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 的过程包括以下步骤：

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

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: 元素按照排序顺序存储。默认情况下，使用 < 运算符进行排序，但也可以提供自定义的比较函数。

性能：

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

内存占用：

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

使用场景：

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

总结：

选择 unordered_set 还是 set 取决于具体的应用场景和性能需求。如果需要快速的查找、插入和删除操作，并且不关心元素的顺序，那么 unordered_set 是一个更好的选择。如果需要按照排序顺序存储元素，并且需要进行范围查找等操作，那么 set 是一个更好的选择。