1. unordered_map 是什么？

std::unordered_map 是 C++ 标准模板库（STL）中的一个关联容器，它存储了由“键（Key）”和“值（Value）”组成的元素对（std::pair<const Key, Value>）。它的核心特点是：

  • 无序性：元素在容器内的存储顺序是无序的，遍历 unordered_map 时，得到的元素顺序与插入顺序无关，并且在不同编译环境下可能不同。
  • 基于哈希表：其内部实现是一个哈希表（Hash Table）。
  • 高效查询：由于使用了哈希表，它提供了非常快的平均时间复杂度的操作：
    • 插入、删除、查找：平均 O(1)
    • 最坏情况：O(N)，其中 N 是容器中元素的数量（当发生严重的哈希冲突时）。

核心概念：哈希表

为了理解 unordered_map，需要了解哈希表的工作原理：

  1. 哈希函数 (Hash Function)：当插入一个键值对时，unordered_map 会使用一个哈希函数将“键”转换成一个整数，这个整数被称为哈希值（Hash Code）。
  2. 桶 (Bucket)：unordered_map 内部维护一个数组，这个数组被称为“桶”。哈希值经过处理后会映射到其中一个桶的索引上。
  3. 存储：该键值对就被存放在这个索引对应的桶中。
  4. 哈希冲突 (Collision)：如果两个不同的键经过哈希函数计算后得到了相同的桶索引，就发生了“哈希冲突”。unordered_map 通常使用拉链法 (Chaining) 解决冲突，即在每个桶中维护一个链表（或其他数据结构），所有映射到该桶的元素都存储在这个链表中。

与 std::map 的关键区别

特性 std::unordered_map std::map
底层实现 哈希表 (Hash Table) 红黑树 (Red-Black Tree)
元素顺序 无序 按键自动排序 (升序)
查找复杂度 平均 O(1)，最坏 O(N) 严格 O(log N)
插入/删除复杂度 平均 O(1)，最坏 O(N) 严格 O(log N)
对键的要求 必须可哈希 (提供 std::hash) 且可比较相等 (operator==) 必须可比较大小 (operator<)
内存开销 通常更高，因为需要维护桶数组 相对较低
适用场景 追求极致的查找、插入、删除性能，且不关心元素顺序 需要按键排序或进行范围查找 (如查找所有大于某个值的键)

2. 何时使用 unordered_map？

优先选择 unordered_map，除非有以下需求：

  • 需要对键进行排序。
  • 需要根据键进行范围查找（例如，找到所有在 ‘a’ 和 ‘f’ 之间的键）。
  • 性能瓶颈在于最坏情况，无法接受偶尔 O(N) 的操作延迟（例如在硬实时系统中）。

在绝大多数场景下，unordered_map 的平均 O(1) 性能使其成为构建字典、缓存、频率计数等功能的首选。

3. 基本用法

包含头文件和声明

1
2
3
4
5
6
#include <iostream>
#include <string>
#include <unordered_map>

// 声明一个键为 string，值为 int 的 unordered_map
std::unordered_map<std::string, int> word_counts;

插入元素

有多种插入方式：

1. 使用 operator[]
这是最简单直观的方式。如果键已存在，则更新其值；如果不存在，则创建新元素并进行值初始化（对于 int 就是 0），然后再赋新值。

1
2
3
word_counts["apple"] = 5;      // 插入或更新
word_counts["banana"] = 2;
std::cout << word_counts["cherry"] << std::endl; // "cherry" 不存在，会先创建 word_counts["cherry"]=0，然后输出 0

2. 使用 insert()
insert() 更为灵活，它返回一个 std::pair<iterator, bool>。bool 值为 true 表示插入成功（键之前不存在），为 false 表示插入失败（键已存在）。

1
2
3
4
5
6
7
8
9
10
11
// 使用 std::make_pair
auto result1 = word_counts.insert(std::make_pair("apple", 10));
if (!result1.second) {
    std::cout << "'apple' already exists. Value: " << result1.first->second << std::endl;
}

// 使用 C++11 的列表初始化
auto result2 = word_counts.insert({"orange", 3});
if (result2.second) {
    std::cout << "'orange' inserted successfully." << std::endl;
}

3. 使用 emplace() (C++11, 推荐)
emplace() 可以就地构造元素，避免了创建临时对象，效率更高。

1
2
// 直接在容器内用 "grape" 和 7 构造键值对
word_counts.emplace("grape", 7);

访问元素

1. 使用 operator[]
简单直接，但有风险：如果键不存在，它会自动插入一个默认构造的值！这可能不是想要的行为。

1
2
std::cout << "Apples: " << word_counts["apple"] << std::endl; // OK
// std::cout << word_counts["pear"] << std::endl; // 危险！如果 "pear" 不存在，会创建一个新条目 word_counts["pear"] = 0

2. 使用 at()
更安全的方式。如果键存在，返回其值的引用；如果不存在，会抛出 std::out_of_range 异常。

1
2
3
4
5
6
try {
    std::cout << "Bananas: " << word_counts.at("banana") << std::endl;
    std::cout << "Pears: " << word_counts.at("pear") << std::endl; // 这行会抛出异常
} catch (const std::out_of_range& e) {
    std::cerr << "Error: " << e.what() << std::endl;
}

3. 使用 find() (最常用)
这是最标准的“检查并访问”模式。find() 返回一个指向元素的迭代器，如果键不存在，则返回 end() 迭代器。

1
2
3
4
5
6
7
8
9
auto it = word_counts.find("apple");
if (it != word_counts.end()) {
    // 找到了
    std::cout << "Found 'apple' with value: " << it->second << std::endl;
    // it->first 是键 "apple", it->second 是值 5
} else {
    // 没找到
    std::cout << "'apple' not found." << std::endl;
}

删除元素

1. 按键删除 erase(key)
返回被删除元素的数量（对于 unordered_map 总是 0 或 1）。

1
2
3
4
size_t num_erased = word_counts.erase("banana");
if (num_erased > 0) {
    std::cout << "'banana' was erased." << std::endl;
}

2. 按迭代器删除 erase(iterator)
如果已经有了一个有效的迭代器（例如从 find() 返回的），用它来删除效率更高。

1
2
3
4
5
auto it_grape = word_counts.find("grape");
if (it_grape != word_counts.end()) {
    word_counts.erase(it_grape);
    std::cout << "'grape' was erased using an iterator." << std::endl;
}

检查存在性

1. find() != end() (通用)
这是最传统、最通用的方法。

1
2
3
if (word_counts.find("orange") != word_counts.end()) {
    // 存在
}

2. count(key)
由于 unordered_map 的键是唯一的，count() 只会返回 0 或 1，可以直观地用于判断。

1
2
3
if (word_counts.count("orange")) { // count("orange") 返回 1，等效于 true
    // 存在
}

3. contains(key) (C++20)
C++20 引入了 contains() 成员函数，代码更简洁、意图更明确。

1
2
3
4
// 如果编译器支持 C++20
if (word_counts.contains("orange")) {
    // 存在
}

遍历

1. 使用 C++11 范围 for 循环 (推荐)

1
2
3
4
5
std::cout << "\n--- Current Map Contents ---" << std::endl;
for (const auto& pair : word_counts) {
    std::cout << pair.first << ": " << pair.second << std::endl;
}
// 注意：输出顺序是不确定的！

2. 使用迭代器

1
2
3
for (auto it = word_counts.begin(); it != word_counts.end(); ++it) {
    std::cout << it->first << ": " << it->second << std::endl;
}

获取大小和清空

1
2
3
4
5
std::cout << "Map size: " << word_counts.size() << std::endl;
if (!word_counts.empty()) {
    word_counts.clear(); // 删除所有元素
}
std::cout << "Map size after clear: " << word_counts.size() << std::endl;

4. 高级主题：自定义类型作为键 (Key)

如果想用自定义的 struct 或 class 作为键，必须告诉 unordered_map 两件事：

  1. 如何判断两个键相等？ -> 通过重载 operator==。
  2. 如何为键生成哈希值？ -> 通过特化 std::hash 模板。

示例：使用 struct Student 作为键

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <string>
#include <unordered_map>

struct Student {
    std::string first_name;
    std::string last_name;
    int id;

    // 1. 重载 operator==
    bool operator==(const Student& other) const {
        return first_name == other.first_name &&
               last_name == other.last_name &&
               id == other.id;
    }
};

// 2. 特化 std::hash
// 必须在 std 命名空间内
namespace std {
    template <>
    struct hash<Student> {
        size_t operator()(const Student& s) const {
            // 使用标准库为 string 和 int 提供的哈希函数
            // 将多个哈希值组合起来，一种常见的简单方法是使用异或(^)
            size_t h1 = std::hash<std::string>{}(s.first_name);
            size_t h2 = std::hash<std::string>{}(s.last_name);
            size_t h3 = std::hash<int>{}(s.id);

            // 简单的组合方式，更复杂的组合可以减少冲突
            return h1 ^ (h2 << 1) ^ (h3 << 2);
        }
    };
}

int main() {
    std::unordered_map<Student, double> student_grades;

    Student alice = {"Alice", "Wonderland", 101};
    student_grades[alice] = 95.5;

    Student bob = {"Bob", "Builder", 102};
    student_grades.emplace(bob, 88.0);

    // 查找 Alice
    auto it = student_grades.find(alice);
    if (it != student_grades.end()) {
        std::cout << it->first.first_name << "'s grade: " << it->second << std::endl;
    }

    return 0;
}

关键点：当 find 或 insert 一个 Student 对象时，unordered_map 首先调用 std::hash<Student> 计算其哈希值，找到对应的桶。如果桶中有多个元素（发生冲突），它会再使用 operator== 来精确匹配提供的 Student 对象。

5. 性能考量与调优

负载因子 (Load Factor)

  • 定义：负载因子 = 容器中的元素数 / 桶数 (size() / bucket_count())。
  • 意义：它衡量了哈希表的“拥挤”程度。负载因子越高，哈希冲突的概率越大，性能越可能下降。
  • 自动调整：当负载因子超过一个阈值（默认为 1.0），unordered_map 会自动进行重哈希 (rehash)：它会创建一个更大的桶数组，并把所有现有元素重新计算哈希值并放入新桶中。这是一个非常耗时的 O(N) 操作。

可以通过以下函数来管理它：

  • load_factor(): 获取当前负载因子。
  • max_load_factor(): 获取或设置触发重哈希的负载因子阈值。
1
2
// 将阈值设为 0.75，减少冲突，但会更频繁地重哈希
word_counts.max_load_factor(0.75f);

哈希冲突 (Hash Collision)

选择一个好的哈希函数至关重要。一个好的哈希函数应该让键尽可能均匀地分布到所有桶中，以减少冲突。对于自定义类型，组合哈希值时要避免简单的加法，因为像 {a, b} 和 {b, a} 这样的组合会产生相同的哈希值。使用位移和异或是更稳妥的方式。

桶 (Bucket) 接口

unordered_map 提供了一些接口用来观察其内部状态：

  • bucket_count(): 获取桶的总数。
  • bucket_size(n): 获取第 n 个桶中的元素数量。
  • bucket(key): 获取某个键所在的桶的索引。

这些接口主要用于调试和性能分析。

预分配空间 (reserve)

如果预先知道大概要存储多少个元素，使用 reserve() 可以避免多次耗时的自动重哈希过程。

1
2
3
4
5
6
7
8
// 假设我们知道要存储约 1000 个单词
std::unordered_map<std::string, int> large_word_counts;
large_word_counts.reserve(1000); // 分配足够容纳 1000 个元素的桶

for (int i = 0; i < 1000; ++i) {
    // 插入操作将不会触发重哈希
    large_word_counts.emplace("word" + std::to_string(i), i);
}

6. 完整的综合示例

任务：统计一篇文章中每个单词出现的次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <string>
#include <unordered_map>
#include <sstream>
#include <algorithm> // for std::transform
#include <cctype>    // for ::tolower

int main() {
    std::string text = "Hello world! This is a test. Hello again, world.";

    // 预处理：转为小写，移除标点
    std::transform(text.begin(), text.end(), text.begin(), ::tolower);
    std::string punctuation = "!,.?";
    for (char c : punctuation) {
        text.erase(std::remove(text.begin(), text.end(), c), text.end());
    }

    std::unordered_map<std::string, int> word_freq;
    std::stringstream ss(text);
    std::string word;

    // 使用 operator[] 方便地进行计数
    while (ss >> word) {
        word_freq[word]++;
    }

    // 打印结果
    std::cout << "Word Frequency Report:" << std::endl;
    for (const auto& pair : word_freq) {
        std::cout << "'" << pair.first << "': " << pair.second << " times" << std::endl;
    }

    // 检查特定单词
    std::string search_word = "hello";
    if (word_freq.count(search_word)) {
        std::cout << "\nThe word '" << search_word << "' appeared " << word_freq.at(search_word) << " times." << std::endl;
    }

    return 0;
}

输出:

1
2
3
4
5
6
7
8
9
10
Word Frequency Report:
'world': 2 times
'again': 1 times
'test': 1 times
'a': 1 times
'is': 1 times
'this': 1 times
'hello': 2 times

The word 'hello' appeared 2 times.