C++ | 无序集合（unordered set）

无序集合（unordered set）是 C++ STL 中的一种容器，用于存储唯一的元素，并且元素的顺序是无序的。它基于哈希表实现，具有快速的插入、查找和删除操作。

与有序集合（如 set）不同，无序集合不会对元素进行排序，而是根据元素的哈希值来决定存储位置。这样可以在平均情况下实现常数时间复杂度的插入、查找和删除操作。

无序集合的元素类型可以是任意可哈希的类型，包括内置类型（如整数、浮点数、字符串）和自定义类型（需要提供哈希函数）。

使用无序集合时，需要包含 <unordered_set> 头文件，并使用 std::unordered_set 来定义一个无序集合对象。以下是一个示例：

#include <unordered_set>
#include <iostream>

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

    // 插入元素
    mySet.insert(5);
    mySet.insert(2);
    mySet.insert(8);

    // 查找元素
    if (mySet.find(5) != mySet.end()) {
        std::cout << "元素 5 存在" << std::endl;
    }

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

    // 遍历元素
    for (int num : mySet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出结果为：

5 8

无序集合在处理需要快速查找、去重的场景中非常实用，例如查找不存在重复元素的最长子串、判断数组中是否存在重复元素等。但需要注意，无序集合并不保留元素的插入顺序，如果需要有序性，应该使用有序集合（如 set）。

当向无序集合中插入新元素时，无序集合会根据元素的哈希值确定它们的存储位置。如果两个元素具有相同的哈希值，则称它们为哈希冲突。为了解决冲突，无序集合使用了开链法（chaining）或开放寻址法（open addressing）。

• 开链法：每个哈希桶(bucket)维护一个链表或其他数据结构，将哈希冲突的元素链接在一起。当需要查找或删除元素时，首先通过哈希值找到对应的桶，然后在桶内搜索目标元素。
• 开放寻址法：当出现哈希冲突时，直接尝试在其他位置寻找空闲的槽位。常见的开放寻址法包括线性探测、二次探测和双重散列等。线性探测依次检查下一个槽位，二次探测则按照某种增量序列逐步尝试，双重散列则使用第二个哈希函数来计算新的位置。

无论使用哪种冲突解决方法，无序集合都会根据负载因子（load factor）进行动态扩容。负载因子是指存储元素数量与桶数量之比，当负载因子超过一定阈值时，无序集合会自动重新分配更大的桶数组，并将现有元素重新插入新的桶中，以保持较低的冲突率。

在使用无序集合时，需要注意以下几点：

1. 元素类型必须提供哈希函数：无序集合通过哈希函数将元素映射到桶中，因此元素类型必须提供能够计算哈希值的哈希函数。
2. 哈希函数的性能影响：高效的哈希函数能够减少冲突率，提高插入和查找操作的性能。较差的哈希函数可能导致冲突增多，从而降低性能。
3. 平衡负载因子和桶数量：适当调整负载因子可以平衡空间和时间的开销。较小的负载因子可以减少冲突，但会占用更多内存；较大的负载因子可以节省内存，但可能导致冲突增多。

unordered_set<char> lookup; 是一个创建了名为 lookup 的无序集合（unordered set），其中存储了 char 类型的元素。无序集合是一种容器，它可以高效地存储和查找唯一的元素，并且元素的顺序是不确定的。

使用 unordered_set，你可以执行以下操作：

1. 插入元素：使用 insert() 函数向无序集合中插入单个元素或一组元素。

   lookup.insert('a');
   lookup.insert('b');
   lookup.insert('c');

2. 删除元素：使用 erase() 函数删除指定的元素。

   lookup.erase('b');

3. 查找元素：使用 find() 函数查找指定的元素，如果元素存在，则返回指向该元素的迭代器；如果元素不存在，则返回指向集合末尾的迭代器。

   auto it = lookup.find('c');
   if (it != lookup.end()) {
       // 元素存在
   } else {
       // 元素不存在
   }

4. 迭代集合：使用迭代器遍历无序集合中的所有元素。

   for (auto it = lookup.begin(); it != lookup.end(); ++it) {
       // 使用 *it 访问每个元素
   }

5. 获取集合大小：使用 size() 函数获取无序集合中元素的数量。

   int size = lookup.size();

总之，无序集合是一种在常数时间内进行插入、查找和删除操作的容器。它适用于需要高效去重和快速查找的场景，但需要根据具体的需求选择合适的哈希函数和调整负载因子。