详细地介绍一下 C++ 中 std::unordered_map，包括基本概念、实现原理、常用操作、性能特点、注意事项等等。

1. 什么是 unordered_map？

• std::unordered_map 是 C++11 引入的哈希表（Hash Table）实现的关联容器。

• 它存储的是键值对（key-value pair），每个 key 是唯一的，value 可以是任意类型。

• 它基于哈希函数进行快速查找，查找、插入、删除的平均时间复杂度是 O(1)。

2. 头文件和定义

#include <unordered_map>

std::unordered_map<KeyType, ValueType> mapName;

示例：

#include <iostream>
#include <unordered_map>

int main() {
    std::unordered_map<std::string, int> age;
    age["Alice"] = 30;
    age["Bob"] = 25;
    
    std::cout << age["Alice"] << std::endl; // 输出 30
}

3. unordered_map 的内部实现原理

• 底层是一个哈希表，使用桶（bucket）存储元素。

• 哈希函数（比如 std::hash<Key>) 将 key 映射到一个桶的索引。

• 如果多个 key 映射到了同一个桶，会使用链表（或红黑树，在某些优化版本中）解决冲突（碰撞）。

• 当元素太多，负载因子（load factor）过高时，会rehash，即扩容并重新分配元素。

4. 常用成员函数

5. 示例代码

基本插入和查找：

std::unordered_map<int, std::string> umap;
umap[1] = "One";
umap[2] = "Two";

// 查找
if (umap.find(1) != umap.end()) {
    std::cout << "Key 1 found: " << umap[1] << std::endl;
}

// 遍历
for (auto& pair : umap) {
    std::cout << pair.first << " -> " << pair.second << std::endl;
}

使用 emplace（原地构造更快）：

umap.emplace(3, "Three");

删除元素：

umap.erase(2); // 删除 key=2 的元素

6. 负载因子（Load Factor）与 Rehash

• 负载因子 = 元素数量 / 桶数量

• 默认的负载因子阈值是大约 1.0，超过之后会自动扩容（rehash）。

• 你也可以手动设置或触发 rehash，比如：

umap.rehash(100); // 提前扩容到至少100个桶
umap.reserve(500); // 预留空间，减少扩容次数

这在需要插入大量元素时非常重要，可以显著提高性能。

7. 性能特点

• 查找/插入/删除：平均 O(1)，最坏 O(n)（如果哈希冲突严重）。

• 元素无序：元素在桶中按 hash 排列，不保证插入顺序。

• 内存开销：比 std::map（基于红黑树）要大，但速度更快。

• 适合场景：需要快速插入/查找/删除，不关心元素顺序的地方。

8. 注意事项 ⚡

• unordered_map 依赖于 哈希函数 和 等值比较函数，你可以自定义（比如对于自定义类型的 key）。

• 键（key）需要可哈希（Hashable），比如内置类型、std::string 等。

• 如果使用自定义类型作为 key，需要提供：

• 一个 std::hash 特化

• 一个 operator== 重载

例如：

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

namespace std {
template <>
struct hash<Point> {
    size_t operator()(const Point& p) const {
        return hash<int>()(p.x) ^ hash<int>()(p.y << 1);
    }
};
}

9. unordered_map 和 map 的比较

10. unordered_map 的内部结构图？