2.6、无序关联容器（unordered_set）

• • 传统的set是基于红黑树，元素自动排序，查找、插入时间复杂度是O(log n)；
• • unordered_set是基于哈希表，元素无序，查找、插入平均时间复杂度是O(1)，也就是说速度更快。

简单来说，如果你不关心元素的顺序，只想快速判断一个元素是否存在，unordered_set就是理想选择。

设计哲学：为什么C++11要引入unordered_set？

C++98时代，set已经很好用，但它的红黑树结构决定了操作速度受限于对数级别。面对海量数据，性能瓶颈明显。哈希表的出现，正是为了解决这个问题：

• • 速度优先：放弃元素的自动排序，换取查找和插入的常数时间复杂度。
• • 统一标准：之前各家编译器有自己的hash_set实现，C++11统一标准接口，方便跨平台使用。
• • 灵活扩展：支持自定义哈希函数，适应各种复杂类型。

一句话总结：当你只想快速判断元素是否存在，不关心顺序时，unordered_set是你的利器。

代码对比：set vs unordered_set

#include <iostream>
#include <set>
#include <unordered_set>

int main() {
    // 传统set，自动排序
    std::set<int> orderedSet = {4, 2, 5, 1, 3};
    std::cout << "set（有序）元素：";
    for (int num : orderedSet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    // unordered_set，无序存储
    std::unordered_set<int> unorderedSet = {4, 2, 5, 1, 3};
    std::cout << "unordered_set（无序）元素：";
    for (int num : unorderedSet) {
        std::cout << num << " ";
    }
    std::cout << std::endl;

    return 0;
}

输出示例：

set（有序）元素：1 2 3 4 5 
unordered_set（无序）元素：3 2 5 1 4 

你可以看到，set遍历时元素自动排序，而unordered_set遍历顺序杂乱无章，因为它是基于哈希桶存储的。

unordered_set底层原理简述

unordered_set内部维护一个桶数组（bucket），每个桶是一个链表或类似结构：

1. 1. 通过哈希函数（默认是std::hash）计算元素的哈希值。
2. 2. 根据哈希值对桶数取模，定位到具体桶。
3. 3. 在桶中查找元素（通过operator==比较）。
4. 4. 找到则返回，找不到则插入。

当哈希冲突发生（不同元素哈希值相同），它们会被存储在同一个桶的链表中。为了保证性能，unordered_set会根据装载因子（元素数/桶数）自动扩容和重哈希。

设计哲学与最佳使用场景

设计哲学

牺牲元素顺序，换取快速的查找和插入性能。采用链地址法解决冲突，保证平均常数时间复杂度。

最佳使用场景

• • 需要存储唯一元素集合，频繁查找是否存在某元素。
• • 不关心元素顺序。
• • 大量数据去重和快速访问。

不适合

• • 需要有序遍历或范围查询。
• • 键类型没有合适的哈希函数。
• • 对内存占用敏感且数据量较小。

优缺点总结

常见误用及后果

1. 1. 误用insert插入重复元素：unordered_set不允许重复元素，重复插入会失败且不报错，需检查返回值确认是否插入成功。
2. 2. 自定义类型未提供哈希函数和相等比较：默认std::hash只支持部分内置类型，自定义类型必须重载operator==并提供哈希函数，否则编译失败或运行异常。
3. 3. 遍历时修改容器：插入元素可能触发重哈希，导致迭代器失效，遍历过程中插入或删除会引发未定义行为。
4. 4. 错误理解无序性：误以为unordered_set元素顺序固定，依赖遍历顺序会导致程序不稳定。

实战示例：用unordered_set快速去重

#include <iostream>
#include <unordered_set>
#include <vector>

int main() {
    std::vector<int> nums = {1, 2, 3, 2, 4, 1, 5, 3};
    std::unordered_set<int> uniqueSet;

    for (int num : nums) {
        uniqueSet.insert(num);
    }

    std::cout << "去重后的元素有：";
    for (int elem : uniqueSet) {
        std::cout << elem << " ";
    }
    std::cout << std::endl;

    return 0;
}

这段代码高效地实现了从一个含重复元素的数组中提取唯一元素，体现了unordered_set的实用价值。

unordered_set的引入不仅仅是性能的提升，更是C++标准库设计哲学的体现——用最合适的数据结构解决最实际的问题。它提醒我们，容器的选择应基于具体需求，而非盲目追求“有序”。

在现代软件开发中，频繁的查找和去重操作极易成为性能瓶颈，unordered_set以其哈希表结构成为解决这类问题的利器。但真正发挥其价值的关键，是理解哈希函数设计和底层机制，避免盲目使用。

合理选用unordered_set，结合自定义哈希策略，才能写出既高效又健壮的代码。
本文首发于【讳疾忌医-note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）