C++ map和unordered_map有什么区别红黑树与哈希表实现对比-C++-PHP中文网

C++ map和unordered_map有什么区别红黑树与哈希表实现对比

P粉602998670

发布： 2025-07-19 12:34:01

原创

419人浏览过

map基于红黑树实现，元素按键顺序存储，插入查找时间复杂度稳定o(log n)；unordered_map基于哈希表实现，无序存储，理想情况操作时间复杂度o(1)，但受哈希冲突影响可能退化为o(n)。1.底层结构：map使用红黑树保证有序，默认升序排列；unordered_map使用哈希表实现，依赖哈希函数映射键值。2.性能对比：map插入查找效率稳定，适合数据量小或频繁变动场景；unordered_map平均更快，但性能依赖哈希函数质量。3.内存与扩容：map内存分配稳定，无明显扩容行为；unordered_map插入可能触发rehash，导致偶尔延迟尖峰，可通过reserve()预留空间避免。4.自定义类型支持：map需提供比较函数或重载<运算符；unordered_map需自定义哈希函数和相等判断函数。选择依据在于是否需要有序遍历、稳定性要求以及对查找速度的需求。

C++ map和unordered_map有什么区别红黑树与哈希表实现对比

C++ 中的 map 和 unordered_map 都是用来存储键值对的数据结构，但它们底层实现不同，也导致了在使用场景和性能上有一些明显区别。

1. 底层结构：红黑树 vs 哈希表

map 是基于红黑树实现的，而 unordered_map 则是用哈希表来实现的。

红黑树是一种自平衡的二叉搜索树，这意味着插入、查找、删除的时间复杂度都是 O(log n)。它能保证元素按照键的顺序存储，默认是升序排列。

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

哈希表则是通过哈希函数将键映射到特定的位置，理想情况下这些操作的时间复杂度可以达到 O(1)，但在冲突严重时会退化为 O(n)（比如所有键都哈希到同一个桶中）。

所以如果你需要有序遍历键值对，就选 map；如果更在意访问速度且不需要顺序，那 unordered_map 更合适。

2. 插入与查找性能对比

map 的插入和查找：

Calliper 文档对比神器
文档内容对比神器

28

查看详情
- 插入一个元素需要找到合适位置并调整树结构以维持平衡，时间稳定在 O(log n)。
- 查找也是通过比较进行，效率稳定，适合数据量不大或变化频繁的情况。
unordered_map 的插入和查找：
- 插入和查找依赖哈希函数，理想情况非常快，O(1)，但如果哈希冲突多就会变慢。
- 所以它的性能受哈希函数质量影响较大，写一个合理的哈希函数很关键。

举个例子：如果你要频繁查找几万个字符串键，unordered_map 可能比 map 快很多；但如果键类型是 int，而且范围集中，简单的哈希可能反而造成大量冲突，这时候 map 反倒更稳。

3. 内存占用与扩容机制

map 的内存分配相对稳定，每个节点单独申请空间，不会有明显的“扩容”行为。
unordered_map 在插入过程中可能会触发 rehash，也就是重新分配整个哈希表的空间，并把旧数据迁移过去，这会导致某些插入操作耗时突然增加。

所以如果你的应用对响应时间敏感，或者不希望偶尔出现延迟尖峰，那就要注意 unordered_map 的 rehash 行为。可以通过 reserve() 提前预留足够空间来避免这个问题。

4. 是否支持自定义类型直接使用

map 要求键类型支持比较操作，通常默认是 < 运算符。如果是自定义类型，你需要提供一个比较函数或重载 <。
unordered_map 需要提供一个哈希函数和相等判断函数（==），否则编译会报错。

例如：

struct MyKey {
    int x, y;
};

// 要让 unordered_map 支持这个类型，你得写一个 hash 函数对象
namespace std {
    template<>
    struct hash<MyKey> {
        size_t operator()(const MyKey& k) const {
            return hash<int>()(k.x) ^ hash<int>()(k.y);
        }
    };
}

登录后复制

相比之下，map 对自定义类型的使用更简单些，只要能比较大小就行。

基本上就这些。选择 map 还是 unordered_map，主要看你是更在意顺序、稳定性，还是追求平均更快的查找速度。

以上就是C++ map和unordered_map有什么区别红黑树与哈希表实现对比的详细内容，更多请关注php中文网其它相关文章！