C++基础面试题, C++ 中 map 和 unordered_map 的区别?分别在什么场景下使用?

QA

Step 1

Q:: C++ 中 map 和 unordered_map 的区别？

A:: C++ 中，map 是一种基于红黑树（Red-Black Tree）实现的有序关联容器，它会按照键的顺序自动排序。而 unordered_map 是一种基于哈希表（Hash Table）实现的无序关联容器，它不会自动排序。由于 map 维护了键的顺序，因此在插入、删除和查找操作时，它的时间复杂度是 O(log n)。而 unordered_map 则可以在平均情况下提供 O(1) 的查找、插入和删除操作，但在最坏情况下，它的时间复杂度可以退化到 O(n)。

Step 2

Q:: map 和 unordered_map 分别在什么场景下使用？

A:: map 适用于需要按键值排序或需要有序遍历的场景，如按字典顺序排序的单词频率统计。unordered_map 适用于对性能要求较高且不需要有序遍历的场景，如快速查找、插入和删除元素的场景，例如频繁的哈希查找操作。

用途

面试中会考察 map 和 unordered_map 的区别及其使用场景，主要是为了评估候选人对 C`++` 容器的熟悉程度以及在不同场景下选择合适数据结构的能力。在实际生产环境中，使用 map 还是 unordered_map 取决于特定需求，例如数据是否需要排序、性能要求如何等。理解两者的区别对于编写高效的代码至关重要，特别是在对性能敏感的应用中，如游戏开发、实时系统或需要处理大量数据的服务端程序中。\n

相关问题

🦆

C++ 中 map 和 set 的区别?▷

map 是一种关联容器，存储键值对（key-value pairs），而 set 是一种集合容器，只存储键（key）。map 中的键值对是唯一的，键不能重复；set 中的每个元素都是唯一的，元素不能重复。map 允许通过键来查找对应的值，而 set 只用于存储和查询键的存在性。

🦆

为什么 unordered_map 在最坏情况下的时间复杂度是 On?▷

unordered_map 使用哈希表来实现，在哈希冲突严重的情况下，不同键值对会被分配到相同的哈希桶中，从而导致链表长度增加，退化为线性查找。这时，插入、删除和查找的时间复杂度会从平均情况下的 O(1) 增加到最坏情况下的 O(n)。为了避免这种情况，选择一个良好的哈希函数并保持哈希表负载因子较低是非常重要的。

🦆

如何选择合适的哈希函数?▷

选择合适的哈希函数时，应确保哈希函数能够均匀地分布键，以尽量减少哈希冲突。一个好的哈希函数应具备：1. 快速计算哈希值的能力；2. 对不同输入生成不同哈希值的能力（避免冲突）；3. 简单易实现。例如，C++ 标准库中提供了一些常用类型的默认哈希函数，如 std::hash<std::string>，但对于自定义类型，可能需要自定义哈希函数。

🦆

C++ 中如何自定义哈希函数?▷

在 C++ 中，可以通过重载 std::hash 模板或创建一个新的函数对象来自定义哈希函数。例如，对于一个自定义结构体，可以定义一个专门的哈希函数类，并在 unordered_map 中作为模板参数传入，以实现自定义哈希。

🦆

map 和 unordered_map 的遍历方式有何不同?▷

由于 map 是有序的，其遍历结果会按键值顺序进行，而 unordered_map 是无序的，遍历结果则没有特定顺序。在需要有序输出时，map 是更好的选择；而在只需要无序访问的情况下，unordered_map 更高效。

什么是C++的列表初始化？C++模板