11. std::unordered_map / std::unordered_multimap 详解：哈希映射的实现、与 map 的对比、性能调优

说实话，很多 C++ 开发者对 map 情有独钟，觉得它稳定、好用。但一旦数据量上来，你就会发现 map 的查找速度开始拖后腿。这时候，unordered_map 就该登场了。

我个人习惯把 unordered_map 叫做「哈希表」，因为它底层就是哈希表实现的。而 map 是红黑树。两者虽然接口长得像，但骨子里完全是两套东西。今天我就带你彻底搞懂它们。

11.1 哈希映射的核心原理

说白了，哈希映射就是「通过一个函数，把 key 直接映射到内存位置」。这个函数叫哈希函数。理想情况下，你给一个 key，它 O(1) 就能找到对应的 value。

但现实没那么完美。不同的 key 可能映射到同一个位置，这就叫「哈希冲突」。STL 用的是链地址法——每个桶（bucket）后面挂一个链表，冲突的元素就链在后面。

核心结构：

  • 桶（bucket）：哈希表的基本存储单元
  • 哈希函数：将 key 转为桶索引
  • 负载因子（load factor）：元素总数 / 桶数，控制扩容时机

嗯，这里要注意：当负载因子超过阈值（默认 1.0），哈希表就会自动扩容——重新分配桶数组，把所有元素重新哈希一遍。这个操作很重，我曾在项目中遇到过因为频繁扩容导致性能抖动的问题。

unordered_map 哈希表结构示意图 桶数组（buckets） 桶 0 桶 1 桶 2 桶 3 桶 4 桶 5 桶 6 key1 key2 key3 key4 key5 ↓ 哈希函数：hash(key) % bucket_count 输入 key 哈希计算 → 桶索引 O(1) 查找

11.2 unordered_map 与 map 的对比

你可能会问：「那我到底该用哪个？」我直接给你一张对比表，看完就明白了。

对比维度 map（红黑树） unordered_map（哈希表）
底层结构 红黑树（平衡二叉搜索树） 哈希表（桶 + 链表）
查找时间复杂度 O(log n) 平均 O(1)，最坏 O(n)
插入时间复杂度 O(log n) 平均 O(1)，最坏 O(n)
元素顺序 按键升序排列 无序
内存占用 较低（每个节点存左右指针） 较高（桶数组 + 链表节点）
迭代器稳定性 插入/删除不影响其他迭代器 rehash 会使所有迭代器失效
适用场景 需要有序遍历、范围查询 大量查找、不关心顺序

我的经验：如果数据量在几百以内，两者差别不大。但一旦超过 10 万级别，unordered_map 的查找速度能快 10 倍以上。不过，如果你需要频繁遍历并保持有序，map 更合适。

11.3 基本用法与代码示例

先看一个最简单的例子。我习惯用 emplace 而不是 insert，因为 emplace 可以直接构造，少一次拷贝。

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

int main() {
    std::unordered_map<std::string, int> scores;
    
    // 插入方式一：emplace（推荐）
    scores.emplace("Alice", 95);
    scores.emplace("Bob", 87);
    
    // 插入方式二：insert
    scores.insert({"Charlie", 92});
    
    // 插入方式三：下标操作
    scores["David"] = 78;  // 如果 key 不存在，会默认构造一个
    
    // 查找
    auto it = scores.find("Alice");
    if (it != scores.end()) {
        std::cout << "Alice's score: " << it->second << "\n";
    }
    
    // 遍历（注意：顺序不确定）
    for (const auto& [name, score] : scores) {
        std::cout << name << ": " << score << "\n";
    }
    
    return 0;
}

注意：使用 operator[] 时要小心。如果 key 不存在，它会自动插入一个默认构造的值。我曾经在项目中因为这个特性，不小心往 map 里塞了一堆空数据，排查了半天才发现。

11.4 unordered_multimap：允许重复 key

有时候你需要一个 key 对应多个 value。比如一个学生可以参加多个社团。这时候 unordered_multimap 就派上用场了。

它和 unordered_map 的区别就一点：允许重复 key。但代价是——不能用 operator[]，因为不知道返回哪个 value。

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

int main() {
    std::unordered_multimap<std::string, std::string> members;
    
    members.emplace("篮球社", "张三");
    members.emplace("篮球社", "李四");
    members.emplace("音乐社", "王五");
    
    // 查找某个 key 的所有 value
    auto range = members.equal_range("篮球社");
    for (auto it = range.first; it != range.second; ++it) {
        std::cout << it->second << "\n";
    }
    
    // 统计某个 key 的数量
    std::cout << "篮球社人数: " << members.count("篮球社") << "\n";
    
    return 0;
}

11.5 性能调优实战

说实话，很多人用 unordered_map 就是图省事，但用不好反而比 map 还慢。我总结了几个调优要点。

11.5.1 预分配桶数量

如果你知道大概要存多少元素，提前用 reserve 分配好桶。这样可以避免多次 rehash。

std::unordered_map<int, std::string> map;
map.reserve(10000);  // 提前分配 10000 个桶
// 后续插入不会触发 rehash，直到超过负载因子

我在项目中遇到过一个问题：一个服务启动时要加载 50 万条配置，没加 reserve，结果启动时 rehash 了十几次，每次都要重新分配内存、重新计算哈希，启动时间从 0.5 秒变成了 3 秒。加上 reserve 后，瞬间回到 0.5 秒。

11.5.2 选择合适的哈希函数

STL 默认的 std::hash 对大多数类型已经够用。但如果你用自定义类型，一定要提供一个好的哈希函数。

struct Point {
    int x, y;
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
};

// 自定义哈希函数
struct PointHash {
    std::size_t operator()(const Point& p) const {
        // 使用 boost::hash_combine 的思想
        return std::hash<int>()(p.x) ^ (std::hash<int>()(p.y) << 1);
    }
};

std::unordered_map<Point, std::string, PointHash> pointMap;

避坑指南：我曾经写过一个很烂的哈希函数，把所有点都映射到同一个桶里。结果查找变成了 O(n)，比 map 还慢。好的哈希函数应该让数据均匀分布。

11.5.3 调整负载因子

默认负载因子是 1.0。如果你对内存不敏感，但对速度敏感，可以降低负载因子，减少冲突。

std::unordered_map<int, std::string> map;
map.max_load_factor(0.5);  // 降低负载因子，减少冲突
map.reserve(10000);        // 配合 reserve 使用

降低负载因子意味着桶更多、冲突更少，但内存占用更大。这是一个 trade-off。

11.5.4 遍历时不要插入/删除

这一点和 map 不同。在遍历 unordered_map 时插入或删除，可能会导致 rehash，使迭代器失效。

// 错误做法
for (auto it = map.begin(); it != map.end(); ++it) {
    if (condition) {
        map.erase(it);  // 迭代器失效！
    }
}

// 正确做法
for (auto it = map.begin(); it != map.end(); ) {
    if (condition) {
        it = map.erase(it);  // erase 返回下一个迭代器
    } else {
        ++it;
    }
}

11.6 性能对比实测

我写了一个简单的测试程序，对比 map 和 unordered_map 在不同数据量下的查找性能。

#include <iostream>
#include <map>
#include <unordered_map>
#include <chrono>
#include <random>

int main() {
    const int N = 100000;
    std::map<int, int> m;
    std::unordered_map<int, int> um;
    um.reserve(N);
    
    // 插入数据
    for (int i = 0; i < N; ++i) {
        m[i] = i;
        um[i] = i;
    }
    
    // 随机查找
    std::mt19937 rng(42);
    std::uniform_int_distribution<int> dist(0, N - 1);
    
    auto start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; ++i) {
        m.find(dist(rng));
    }
    auto end = std::chrono::high_resolution_clock::now();
    auto mapTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    start = std::chrono::high_resolution_clock::now();
    for (int i = 0; i < 100000; ++i) {
        um.find(dist(rng));
    }
    end = std::chrono::high_resolution_clock::now();
    auto umapTime = std::chrono::duration_cast<std::chrono::microseconds>(end - start);
    
    std::cout << "map: " << mapTime.count() << " us\n";
    std::cout << "unordered_map: " << umapTime.count() << " us\n";
    std::cout << "unordered_map 快 " << mapTime.count() / umapTime.count() << " 倍\n";
    
    return 0;
}

在我的机器上，unordered_map 比 map 快了大约 5-8 倍。数据量越大，差距越明显。

11.7 总结与选择建议

  • 需要有序遍历、范围查询 → 用 map
  • 大量查找、不关心顺序 → 用 unordered_map
  • 允许重复 key → 用 unordered_multimap
  • 数据量小（几百以内） → 两者皆可，看个人习惯
  • 自定义类型做 key → 记得提供哈希函数和 operator==

嗯，最后说一句：没有银弹。选哪个容器，取决于你的具体场景。我个人的习惯是：默认用 unordered_map，除非我需要有序遍历。但如果你不确定，先用 map 也没问题，后期再优化也来得及。

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

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