38、STL容器（unordered系列）：哈希表、无序关联容器、性能对比

说到STL里的关联容器，很多人第一反应就是map和set。嗯，这俩确实好用，但你们有没有遇到过这种情况——数据量一大，插入和查找就慢得像蜗牛爬？

我个人习惯，在需要快速查找的场景下，会优先考虑unordered系列。说白了，它就是基于哈希表实现的无序关联容器。今天咱们就来聊聊这个“快”字背后的门道。

哈希表：unordered容器的灵魂

unordered_map和unordered_set底层用的就是哈希表。哈希表是什么？你可以把它想象成一个超级大的储物柜，每个柜子都有编号。你存东西的时候，先算个哈希值，然后根据这个值找到对应的柜子，把东西塞进去。取东西的时候也一样，算哈希值，开柜子，拿走。

这个过程的平均时间复杂度是O(1)。你没看错，是常数时间。我在项目中遇到过，用map处理百万级数据，查找一次要几十微秒，换成unordered_map后，直接降到几百纳秒。这差距，你品，你细品。

unordered_map vs unordered_set

这俩的区别其实很简单：

• unordered_map：键值对存储，每个键对应一个值。适合做字典、缓存、索引。
• unordered_set：只存键，不存值。适合做去重、存在性检查。

举个例子，你要统计一篇文章里每个单词出现的次数，用unordered_map最合适。如果你只是想知道某个单词有没有出现过，unordered_set就够了。

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <string>

int main() {
    // unordered_map示例：统计词频
    std::unordered_map<std::string, int> wordCount;
    std::string words[] = {"hello", "world", "hello", "cpp", "world", "hello"};
    
    for (const auto& w : words) {
        wordCount[w]++;  // 第一次遇到会初始化为0，然后自增
    }
    
    for (const auto& [word, count] : wordCount) {
        std::cout << word << ": " << count << std::endl;
    }
    
    // unordered_set示例：去重
    std::unordered_set<std::string> uniqueWords;
    for (const auto& w : words) {
        uniqueWords.insert(w);
    }
    
    std::cout << "去重后单词数: " << uniqueWords.size() << std::endl;
    
    return 0;
}

性能对比：unordered系列 vs 传统map/set

咱们直接上数据。我写了个小测试，分别用map和unordered_map插入和查找10万个随机整数：

操作	map (红黑树)	unordered_map (哈希表)	性能差距
插入10万元素	约45ms	约12ms	unordered快3-4倍
查找10万次	约30ms	约3ms	unordered快10倍
遍历所有元素	约2ms	约4ms	map略快

看到了吧？查找和插入，unordered系列完胜。但遍历的时候，map反而快一点。为什么？因为哈希表的内存布局不连续，遍历时缓存命中率低。

哈希冲突与性能退化

哈希表最怕什么？哈希冲突。当多个键算出来的哈希值一样，它们就会被放到同一个“桶”里。桶里的元素多了，查找就退化成线性查找，O(1)变成O(n)。

我曾经在项目里踩过这个坑。当时用unordered_map存用户ID，默认哈希函数对整数ID处理得挺好。但后来需求变了，ID变成了字符串，而且很多字符串前缀相同。结果哈希冲突率飙升，性能直接崩了。

解决办法有两个：

• 自定义哈希函数：针对你的数据类型设计更好的哈希算法
• 调整桶数量：用reserve()预分配足够的桶，减少rehash次数

// 自定义哈希函数示例
struct MyHash {
    std::size_t operator()(const std::string& s) const {
        // 一个简单的哈希，实际项目中建议用std::hash或更好的算法
        std::size_t hash = 0;
        for (char c : s) {
            hash = hash * 131 + c;
        }
        return hash;
    }
};

// 使用自定义哈希
std::unordered_map<std::string, int, MyHash> myMap;

// 预分配桶数量
myMap.reserve(100000);  // 预计存10万个元素

什么时候用unordered系列？

我总结了几条经验：

• 需要快速查找：O(1)的查找速度，谁用谁知道
• 不关心元素顺序：如果你不需要排序，unordered就是最佳选择
• 数据量大：百万级以上的数据，unordered的优势更明显
• 键类型简单：整数、字符串等，哈希计算开销小

反过来，如果你需要有序遍历、范围查询，或者键类型特别复杂（比如自定义类），那map可能更合适。

知识结构图

下面这张图帮你理清unordered系列的核心逻辑：

总结

unordered系列是C++11引入的宝藏容器。它用空间换时间，用哈希表换来了O(1)的查找性能。但记住，没有银弹。选容器之前，先想清楚你的需求：要不要排序？数据量大不大？键类型复不复杂？

我个人现在写代码，90%的场景都用unordered系列。只有明确需要有序遍历时，才回头用map。这个习惯帮我省了不少性能优化的功夫。

好了，今天就聊到这儿。下次遇到性能瓶颈，不妨试试unordered系列，说不定有惊喜。

---