2.5、无序关联容器（unordered_map）

但它和map最大的区别是：

• • map内部是红黑树结构，元素自动按键排序，查找时间复杂度是O(log n)；
• • unordered_map内部是哈希表结构，元素无序，查找时间复杂度平均是O(1)，也就是说查找更快，但不保证顺序。

换句话说，unordered_map就是用哈希函数把键“映射”到一个桶里，通过哈希值直接定位，极大提升了查找速度。

设计哲学：为什么要有unordered_map？

C++98时代的map已经非常强大，但它的红黑树结构决定了查找速度是对数时间，面对海量数据时效率不够理想。哈希表的出现就是为了解决这个问题：

• • 速度优先：牺牲元素的顺序，换取查找、插入的平均常数时间复杂度。
• • 统一标准：之前各大编译器都有自己的hash_map实现，C++11将其纳入标准库，统一了接口和行为。
• • 灵活扩展：支持自定义哈希函数和相等比较，适应各种复杂键类型。

总结一句话：如果你不关心键的顺序，只想最快地查找和插入，unordered_map就是你的首选。

代码对比：map vs unordered_map

#include <iostream>
#include <map>
#include <unordered_map>

int main() {
    // 传统map，键自动排序
    std::map<std::string, int> orderedMap;
    orderedMap["apple"] = 3;
    orderedMap["banana"] = 2;
    orderedMap["orange"] = 5;

    std::cout << "map遍历（有序）:" << std::endl;
    for (const auto& pair : orderedMap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    // unordered_map，键无序
    std::unordered_map<std::string, int> unorderedMap;
    unorderedMap["apple"] = 3;
    unorderedMap["banana"] = 2;
    unorderedMap["orange"] = 5;

    std::cout << "unordered_map遍历（无序）:" << std::endl;
    for (const auto& pair : unorderedMap) {
        std::cout << pair.first << " : " << pair.second << std::endl;
    }

    return 0;
}

输出示例：

map遍历（有序）:
apple : 3
banana : 2
orange : 5
unordered_map遍历（无序）:
orange : 5
banana : 2
apple : 3

你看到没？map遍历时元素自动按字母顺序排列，而unordered_map遍历顺序杂乱无章，因为它是哈希桶存储的。

unordered_map底层原理简析

unordered_map内部维护一个“桶数组”，每个桶是一个链表（或链式哈希结构）：

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

哈希冲突时，多个键落在同一桶，链表负责串联这些元素。平均情况下，查找是O(1)，但最坏情况可能退化为O(n)。

设计哲学与最佳使用场景

设计哲学

以牺牲元素顺序为代价，换取极致的查找和插入性能。C++11标准采用链式哈希，避免了开放寻址带来的复杂问题，保证了稳定和效率。

最佳使用场景

• • 频繁查找、插入、删除，且不关心元素顺序。
• • 需要快速判断键是否存在。
• • 缓存、计数器、哈希索引等性能敏感场景。

不适合的场景

• • 需要按键排序遍历。
• • 需要稳定迭代顺序。
• • 键类型没有合适哈希函数或哈希冲突严重。

优缺点总结

常见误用及后果

1. 1. 误用operator[]访问不存在的键：unordered_map[key]如果键不存在，会插入一个默认值元素，导致容器膨胀，影响性能和逻辑正确性。正确做法：访问前用find()或count()判断键是否存在。
2. 2. 自定义键类型未提供哈希函数和相等比较：默认std::hash只支持部分内置类型，自定义类型必须重载operator==并提供哈希函数，否则编译失败或行为异常。
3. 3. 遍历时修改容器：插入元素可能触发rehash，导致迭代器失效，遍历时插入会导致异常或死循环。
4. 4. 误用insert插入重复键：insert不会替换已有键值，插入失败，需检查返回值或用operator[]赋值更新。

实战示例：用unordered_map统计元素出现次数

#include <iostream>
#include <unordered_map>
#include <vector>

int main() {
    std::vector<int> nums = {10, 20, 20, 10, 10, 30, 50, 10, 20};
    std::unordered_map<int, int> countMap;

    for (int num : nums) {
        countMap[num]++;  // operator[]自动插入默认值0后加1
    }

    std::cout << "元素计数：" << std::endl;
    for (const auto& p : countMap) {
        std::cout << p.first << " 出现了 " << p.second << " 次" << std::endl;
    }

    return 0;
}

这段代码简洁高效地完成了元素计数，体现了unordered_map的强大。

总结

在现代软件开发中，性能瓶颈往往来自频繁的查找和插入操作，unordered_map以其哈希表结构成为解决这类问题的利器。但它也提醒我们：设计哈希函数和理解底层机制，才是发挥其最大价值的关键。合理使用unordered_map，避免误用，才能让你的代码既高效又健壮。
本文首发于【讳疾忌医 - note】公众号，未经授权，不得转载。
（加入我的知识星球，免费获取账号，解锁所有文章。）