unordered容器：哈希表的三重门

说实话，我刚接触STL那会儿，对unordered系列是有点偏见的。那时候觉得map和set多好啊，有序、稳定、看着就舒服。直到有一次我在一个实时数据处理系统里，用map做查找，结果性能死活上不去——数据量一过百万，插入和查询都慢得像蜗牛。后来换成unordered_map，速度直接提升了两个数量级。嗯，从那以后，我再也不敢小看哈希表了。

今天咱们就来聊聊unordered_set、unordered_map，以及它们背后的哈希冲突处理，还有自定义哈希函数怎么写。说白了，这些容器就是「用空间换时间」的典型代表。

1. unordered_set 和 unordered_map 的基本用法

这两个容器，底层都是哈希表。unordered_set存的是不重复的键，unordered_map存的是键值对。它们最大的特点就是：平均常数时间的查找、插入和删除。

先看个简单的例子：

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

int main() {
    // unordered_set 示例
    std::unordered_set<std::string> uset;
    uset.insert("apple");
    uset.insert("banana");
    uset.insert("orange");
    uset.insert("apple");  // 重复插入，不会生效
    
    std::cout << "unordered_set size: " << uset.size() << "\n";
    // 输出: 3
    
    // unordered_map 示例
    std::unordered_map<std::string, int> umap;
    umap["apple"] = 5;
    umap["banana"] = 3;
    umap["orange"] = 8;
    
    // 查找
    auto it = umap.find("banana");
    if (it != umap.end()) {
        std::cout << "banana count: " << it->second << "\n";
    }
    
    return 0;
}

我个人习惯在需要快速查找、但不关心元素顺序的场景下，优先用unordered系列。比如缓存系统、去重检查、词频统计等等。

小提示：unordered容器的迭代器是前向迭代器，不支持随机访问。你不能像vector那样用it + 5来跳转。

2. 哈希冲突处理：链地址法

哈希表的核心思想，就是把键通过哈希函数映射到一个数组索引上。但不同的键可能映射到同一个索引，这就是哈希冲突。

STL的unordered容器采用链地址法来处理冲突。说白了，就是每个桶（bucket）里挂一个链表。当多个键映射到同一个桶时，它们就串在这个链表上。

我画了一张图，帮你理解这个过程：

哈希表链地址法示意图 桶 0 桶 1 桶 2 桶 3 桶 4 "apple" "grape" "banana" "orange" "pear" 哈希函数: hash(key) % bucket_count "apple" 和 "grape" 冲突 → 挂在同一链表 查找时先定位桶，再遍历链表 负载因子 = 元素数 / 桶数 负载因子 > 1.0 时自动 rehash

当链表太长时，查找效率会下降。STL内部会在负载因子超过阈值（默认1.0）时自动rehash——也就是扩大桶数组，重新分配所有元素。这个过程是O(n)的，但均摊下来还是常数时间。

注意：rehash会导致所有迭代器失效！如果你在遍历unordered容器时插入了大量元素，迭代器可能会突然失效。我建议在批量插入前，先用reserve()预留足够的桶数。

3. 自定义哈希函数

STL为基本类型（int、string、double等）都提供了默认的哈希函数。但如果你用自定义类型做键，就得自己写哈希函数了。

举个例子，假设我们有一个Person结构体，想用它做unordered_map的键：

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

struct Person {
    std::string name;
    int age;
    
    bool operator==(const Person& other) const {
        return name == other.name && age == other.age;
    }
};

// 自定义哈希函数
struct PersonHash {
    std::size_t operator()(const Person& p) const {
        // 组合哈希：把name的哈希和age的哈希混合
        std::size_t h1 = std::hash<std::string>{}(p.name);
        std::size_t h2 = std::hash<int>{}(p.age);
        // 用移位和异或混合，减少冲突
        return h1 ^ (h2 << 1);
    }
};

int main() {
    std::unordered_map<Person, std::string, PersonHash> people;
    
    people[{"Alice", 30}] = "Engineer";
    people[{"Bob", 25}] = "Designer";
    
    Person key{"Alice", 30};
    auto it = people.find(key);
    if (it != people.end()) {
        std::cout << it->first.name << " is " << it->second << "\n";
    }
    
    return 0;
}

这里有几个要点：

  • 必须提供operator==：哈希表需要判断两个键是否相等。默认的==是按位比较，对于结构体可能不对，所以最好自己实现。
  • 哈希函数必须是可调用对象：可以是函数对象（像上面那样），也可以是lambda表达式。
  • 好的哈希函数应该分布均匀：尽量避免不同的键映射到同一个桶。
我的经验：组合多个字段的哈希时，我常用 h1 ^ (h2 << 1) 这种模式。直接异或的话，如果两个字段相同，结果就是0，容易冲突。左移一位再异或，能有效打散。

4. 自定义哈希的另一种写法：特化std::hash

如果你不想每次声明unordered_map时都带上哈希函数，可以特化std::hash：

namespace std {
    template<>
    struct hash<Person> {
        std::size_t operator()(const Person& p) const {
            std::size_t h1 = hash<string>{}(p.name);
            std::size_t h2 = hash<int>{}(p.age);
            return h1 ^ (h2 << 1);
        }
    };
}

// 现在可以直接用默认的哈希了
std::unordered_map<Person, std::string> people;

这样写的好处是，所有用到Person做键的unordered容器，都会自动使用这个哈希函数。我个人比较喜欢这种方式，代码更干净。

5. 性能调优：桶数和负载因子

unordered容器提供了一些接口来调优性能：

方法 作用
bucket_count() 返回当前桶的数量
max_load_factor() 获取/设置最大负载因子
load_factor() 返回当前负载因子
reserve(n) 预留空间，避免多次rehash
rehash(n) 将桶数设置为至少n，并重新分配

举个例子，如果你知道要插入100万个元素，可以先reserve：

std::unordered_map<int, std::string> umap;
umap.reserve(1000000);  // 提前分配足够的桶
// 然后批量插入，不会触发rehash
避坑指南：我曾经在一个高并发场景下，忘了reserve，结果插入过程中频繁rehash，导致性能抖动严重，还引发了迭代器失效的bug。后来加上reserve，问题就解决了。记住：批量插入前先reserve。

6. 什么时候用unordered，什么时候用有序容器？

我列个对比表，帮你快速决策：

场景 推荐容器 原因
需要有序遍历 map / set unordered不保证顺序
需要范围查询（如查找[10, 20]之间的元素） map / set 支持lower_bound/upper_bound
只需要快速查找/插入 unordered_map / unordered_set 平均O(1)，比红黑树的O(log n)快
数据量小（几十个元素） 都可以 性能差异不大，看需求
自定义类型做键 unordered（需提供哈希）或 map（需提供比较器） 看哪个更容易实现

说白了，如果你不关心顺序，就无脑上unordered。但如果你需要「按顺序遍历」或者「找某个范围内的元素」，那就老老实实用map/set。

7. 一个完整的实战例子：词频统计

最后，我写一个完整的例子，展示unordered_map在词频统计中的威力：

#include <unordered_map>
#include <iostream>
#include <sstream>
#include <string>

int main() {
    std::string text = "apple banana apple orange banana apple grape";
    std::istringstream iss(text);
    std::string word;
    
    std::unordered_map<std::string, int> freq;
    
    while (iss >> word) {
        freq[word]++;  // 如果word不存在，会默认初始化为0，然后++
    }
    
    // 输出结果
    for (const auto& [w, count] : freq) {
        std::cout << w << ": " << count << "\n";
    }
    
    return 0;
}

输出结果（顺序可能不同，因为unordered不保证顺序）：

grape: 1
banana: 2
orange: 1
apple: 3

你看，代码非常简洁。freq[word]++这一行，就完成了「如果不存在就插入，存在就自增」的操作。这就是unordered_map的魅力。

核心总结：
  • unordered_set和unordered_map底层是哈希表，平均O(1)操作
  • 哈希冲突用链地址法解决，链表太长时自动rehash
  • 自定义类型做键，需要提供哈希函数和operator==
  • 批量插入前用reserve()避免rehash性能抖动
  • 不关心顺序就用unordered，需要顺序就用map/set

好了，关于unordered容器的内容就聊到这儿。记住，哈希表是C++工具箱里的一把快刀，但用之前得先磨好——也就是设计好你的哈希函数。下次遇到需要快速查找的场景，不妨试试unordered系列，说不定会有惊喜。

公众号:蓝海资料掘金营，微信deep3321

← 上一章 📖 返回目录 下一章 →