C++中的unordered_map和map有什么区别？C++哈希表性能分析【STL进阶】

unordered_map是哈希表，平均O(1)查找但无序；map是红黑树，稳定O(log n)且按键有序、支持范围查找；前者要求key可哈希，后者要求key可比较；适用场景取决于是否需顺序、范围查询及性能敏感度。

unordered_map 是哈希表，map 是红黑树；前者平均 O(1) 查找，后者稳定 O(log n)；前者不排序、无序遍历，后者按键有序、支持范围查找。

底层实现与时间复杂度

unordered_map 基于哈希表（开放寻址或链地址法），插入、查找、删除的平均时间复杂度是 O(1)，最坏情况（大量哈希冲突）退化为 O(n)。实际中只要哈希函数合理、负载因子控制得当，性能非常接近常数。

map 基于自平衡红黑树，所有操作严格保证 O(log n) 时间复杂度，没有“最坏退化”风险，适合对最坏性能有强要求的场景。

常见操作对比：

立即学习“C++免费学习笔记（深入）”；

• 查找元素：unordered_map 平均快很多，尤其数据量大时；map 稳定但稍慢
• 遍历全部元素：两者都是 O(n)，但 unordered_map 遍历顺序完全随机，map 按 key 升序
• 按范围遍历（如 [k1, k2]）：map 支持 lower_bound + upper_bound 高效完成；unordered_map 只能全表扫描

键值约束与哈希要求

map 要求 key 支持 operator

unordered_map 要求 key 可哈希：必须提供 hash 函数（std::hash 的特化）和 == 比较。内置类型（int、string 等）已自带；自定义类需手动特化 std::hash 或传入自定义哈希仿函数。

例如，若用 pair 作 key：

标签： ai c++ 区别 内存占用 red