c++的map和unordered_map有什么区别和实现原理

简要回答

map 是基于红黑树实现的有序关联容器，元素按 key 升序排列，查找、插入、删除复杂度为 O(logN)。

unordered_map 是基于哈希表实现的无序关联容器，元素无序存储，查找、插入、删除的平均复杂度为 O(1)，最坏 O(n)。

详细回答

特性	map	unordered_map
底层结构	红黑树（平衡二叉搜索树）	哈希表（通常是开放地址或链式哈希）
键值顺序	自动排序（升序）	无序
时间复杂度	O(logN) 查找、插入、删除	O(1) 平均，O(n) 最坏
是否支持自定义顺序	支持（自定义比较器）	不支持（但可自定义哈希函数）
内存使用	较紧凑	较大（因哈希表可能有空槽）

• 适用场景

map: 当需要排序遍历所有键值对时，用map容器，但是此时键值对不支持哈希

unordered_map：当某一个场景下，只关心快速查找、插入性能时，使用unordered_map，此时有很多元素频繁查找。

代码示例

#include <iostream>
#include <map>
#include <unordered_map>
using namespace std;

int main() {
    map<string, int> ordered_map;
    unordered_map<string, int> hash_map;

    ordered_map["apple"] = 1;
    ordered_map["banana"] = 2;
    ordered_map["orange"] = 3;

    hash_map["apple"] = 1;
    hash_map["banana"] = 2;
    hash_map["orange"] = 3;

    cout << "map（有序）遍历结果：" << endl;
    for (auto& p : ordered_map)
        cout << p.first << " => " << p.second << endl;

    cout << "\nunordered_map（无序）遍历结果：" << endl;
    for (auto& p : hash_map)
        cout << p.first << " => " << p.second << endl;

    return 0;
}

运行上述代码后会得到：map 总是按照字典序输出，而 unordered_map 输出顺序每次都可能不一样

知识拓展

• 多线程下的性能差异

unordered_map 插入查找快，但线程安全性差，需加锁或使用 concurrent_unordered_map（TBB）

map 插入较慢，但访问结构清晰，适合在多线程并发读的场景下做共享（读锁+写锁）

总之在多线程环境下，map 的结构更适合读多写少的场景，配合 shared_mutex 可以实现并发读。而 unordered_map 虽然查找快，但并不适合直接并发写操作，除非我们通过分桶加锁，或者使用像 TBB 提供的 concurrent_unordered_map 这样的专业并发容器

• 知识图解

B 表示黑色节点，R 表示红色节点（红黑树规则)

左子树所有键小于父节点，右子树所有键大于父节点

插入时保持二叉搜索树性质 + 红黑树平衡规则（旋转 + 变色）

访问：查找 pear：banana →orange→ pear (O(logN))

插入或删除时需要维护红黑树的平衡 → 旋转/染色 → 时间复杂度 O(logN)

哈希函数将 key 映射到桶索引（如 hash("apple") % 5 = 1)

多个 key 映射到相同桶时，使用链表或链式节点进行存储（如 pear 与 banana 哈希冲突）

插入时直接挂在链尾，查找遍历链表（冲突越多越慢）

访问：计算key的哈希值 → 得到桶号

查看该桶链表中是否已有 key → 有则更新，无则插入

若负载因子超过阈值 → 触发扩容 + 重新哈希（rehash）

• 面试官可能追问

  1.unordered_map 发生哈希冲突会怎么处理？

当 unordered_map 发生哈希冲突时，会将多个哈希值相同的元素存入同一个哈希桶中，通常通过链表（链式地址法）或开放寻址法来解决；

C++ STL 中一般采用链表方式，即发生冲突的元素会插入到该桶对应链表的末尾，查找时需要遍历该链表，冲突多时会降低查找性能。

2.为什么 unordered_map 最坏情况是 O(n)？

因为 unordered_map 底层是哈希表结构，理论上查找和插入都是 O(1)，但在最坏情况下，所有键的哈希值都一样（哈希冲突极端严重），所有元素都被插入到同一个桶中，退化成了链表结构，此时查找、插入、删除都变成了线性查找，时间复杂度退化为 O(n)。

3.map 和 unordered_map 的内存占用对比？

map 由于基于红黑树实现，每个节点需要存储指针（父节点、左右子节点）和颜色位，结构更紧凑且稳定；

而 unordered_map 基于哈希表实现，需要额外存储哈希桶数组（包含大量空位）、链表指针等结构，为了降低冲突还要预留扩容空间，因此在元素量相同时，unordered_map 的内存占用通常比 map 更高，但也换来了更快的查找效率（平均 O(1)）。

4.哈希表的负载因子是啥？扩容机制如何？

哈希表的负载因子（Load Factor）是元素个数（N）与桶个数（B）之比，公式为：α = N / B，表示哈希表的“拥挤程度”；

当负载因子超过某个阈值（例如 0.75），就会触发扩容机制，即重新分配更大的桶数组并对所有元素重新哈希（rehash），以减少冲突、保持插入和查找的效率；

但扩容过程代价较大，会导致性能瞬时下降。