std::map 和 std::unordered_map 的区别是什么？ - 面试题面试题 | 播面

基于本文回答

0

评论

知识点图片

在 C++ 标准模板库 (STL) 中，std::map 和 std::unordered_map 都是用于存储键值对 (Key-Value) 的关联容器，并且都要求键 (Key) 是唯一的。

它们的核心区别在于底层实现，这直接决定了它们在时间复杂度、元素顺序、内存占用以及对 Key 的要求上的差异。

以下是详细的对比：

1. 核心对比总结表

特性	`std::map`	`std::unordered_map` (C++11引入)
底层数据结构	红黑树 (平衡二叉搜索树)	哈希表 (Hash Table)
时间复杂度 (平均)	查找/插入/删除： $O(\log n)$	查找/插入/删除： $O(1)$
时间复杂度 (最坏)	查找/插入/删除： $O(\log n)$	查找/插入/删除： $O(n)$ (发生严重哈希冲突时)
元素顺序	有序 (按 Key 自动升序排序)	无序 (随机，取决于哈希函数)
对 Key 的要求	必须重载 `<` 运算符 (或提供比较器)	必须提供 `std::hash` 函数，且重载 `==` 运算符
内存占用	较高 (每个节点需要存父/子节点指针和颜色)	相对较高 (需要维护哈希桶数组和链表指针)
迭代器失效	删除当前节点只失效当前迭代器	`rehash` (扩容) 时，所有迭代器可能失效

2. 详细区别解析

(1) 底层数据结构

std::map：底层通常是一棵红黑树。红黑树是一种自平衡二叉查找树，它保证了树的高度始终保持在 $\log n$ 级别，因此所有的操作都能在对数时间内完成。
std::unordered_map：底层是一个哈希表（通常采用“链地址法”解决哈希冲突）。它通过哈希函数将 Key 映射到一个桶 (bucket) 中。如果多个 Key 映射到同一个桶，就会形成链表。

(2) 时间复杂度与性能

std::map：性能极其稳定。无论数据是什么样，查找、插入、删除的时间复杂度严格保证为 $O(\log n)$ 。
std::unordered_map：大多数情况下极快，平均时间复杂度为 $O(1)$ 。但是，如果哈希函数设计得很差，或者数据极其特殊导致大量哈希冲突（所有元素挤在一个桶里），最坏时间复杂度会退化成 $O(n)$ 。此外，当元素数量超过负载因子时，哈希表会触发扩容 (rehash)，这是一个耗时 $O(n)$ 的操作。

(3) 元素的顺序

std::map：当你遍历 map 时，输出的元素是严格按照 Key 排序（默认升序）的。它支持 lower_bound 和 upper_bound 等范围查找操作。
std::unordered_map：内部毫无顺序可言。遍历输出的顺序和插入顺序无关，并且在发生 rehash 之后，原本的顺序可能会完全被打乱。

(4) 对 Key 类型（自定义类型）的要求

std::map：如果是自定义的结构体或类作为 Key，你必须重载 operator<，或者在模板参数中传入一个自定义的比较函数。因为它需要比较大小来建树。
cpp
```
struct Point { int x, y; };
bool operator<(const Point& a, const Point& b) {
    return a.x < b.x || (a.x == b.x && a.y < b.y);
}
std::map<Point, int> myMap; // OK
```
std::unordered_map：如果是自定义类型作为 Key，你必须为其提供一个哈希函数 (std::hash)，并且重载 operator==（因为要在同一个桶内的链表中寻找完全相同的元素）。这比 map 的要求繁琐得多。

3. 如何选择？（使用场景建议）

优先选择 std::unordered_map，除非你有特殊需求。

选择 std::unordered_map 的场景：
- 你只需要纯粹的键值对映射（查找、插入、删除）。
- 速度是第一优先级（尤其是处理海量数据且不需要排序时）。
- 绝大多数刷算法题（如 LeetCode 中的 Two Sum）、业务代码中的缓存、字典查找等场景，默认都应该用它。
选择 std::map 的场景：
- 你需要按顺序遍历元素（例如：输出排行榜、按时间戳顺序处理事件）。
- 你需要查找某个范围的元素（例如：查找大于且最接近 X 的元素，使用 map.lower_bound(X)）。
- 你希望性能具有绝对的稳定性，不能容忍 unordered_map 扩容 (rehash) 带来的偶尔卡顿（在严苛的实时系统中）。
- 你的 Key 是复杂的自定义结构体，写一个 < 运算符比写一个极其复杂的哈希函数要简单和安全得多。

00:00

00:00