两种哈希表容器的基本特性
有序性与存取语义
C++ 中的 map 与 unordered_map代表了两种截然不同的存储语义：map 提供有序遍历，按照键的升序输出，适合需要范围查询或排序输出的场景；unordered_map 提供无序访问，强调对单次查找和插入的快速性，但遍历顺序不可控。
在实现层面，map 的查找/插入复杂度为 O(log n)，而 unordered_map 的平均复杂度为 O(1)，极端情况下也可能退化到 O(n)；这意味着在大量数据和高频访问的场景下，平均性能往往更优于有序结构。
内部实现差异
map 采用自平衡的二叉搜索树实现（如红黑树），节点按键有序排列，遍历与范围查询天然支持。若键是自定义类型，需要提供严格弱序的比较器，确保树的平衡与正确性。
unordered_map 使用哈希桶 + 冲突处理（链表或探针法），键通过哈希函数映射到桶中，哈希分布决定性能，也因为桶的数量和负载因子影响，再哈希成本需要关注。
性能对比：时间复杂度、内存与遍历
时间复杂度要点
对于查找和插入操作，map 的平均复杂度为 O(log n)，最坏情况下也保持在 O(log n)；unordered_map 的平均复杂度为 O(1)，但在大量哈希冲突时可能退化为 O(n)。
在需要对数据进行有序遍历或范围查询时，map 的对数级复杂度通常是可接受的，但在数据量极大、查找频繁的场景中，unordered_map 的性能优势更明显。
内存与缓存友好性
unordered_map 往往需要更多的内存来维持桶数组和指针/链表结构，但在访问模式简单、查找密集时，常数因子通常较低，缓存命中率也可能更高。在内存受限的环境中，需要权衡桶数量与负载因子。
与之相比，map 的内存占用通常更紧凑，但随着数据量增加，树结构的高度会带来额外的比较开销，平衡树维护成本不可忽视。
选型要点：何时选 map、何时选 unordered_map
数据特征与访问模式
若需要键的排序、范围遍历或输出排序结果，更适合选用 map。它的有序性天然支持逐步遍历、分段查询等功能。
若数据量大、需要快速查找/插入、且对遍历顺序无关，优先考虑 unordered_map，通常能带来更高的单次操作吞吐量。
键类型与自定义哈希
对于内置键类型，unordered_map 的默认哈希实现往往已经足够；但对自定义类型，必须提供合适的哈希函数与等价比较，以确保哈希分布均匀和正确性。
哈希分布质量直接影响性能，不足的哈希函数会导致冲突急剧增多，从而降低 unordered_map 的优势；相对地，map 只需要一个严格弱序的比较器，实现复杂度较低。
常见实现细节与优化技巧
负载因子与再哈希
为提升 unordered_map 的性能，应关注 负载因子，并在必要时触发 再哈希，以降低冲突率和提高命中率。通常，默认设置的负载因子在实战中已经取得不错的折中。
在 map 场景下，虽然没有再哈希，但 树的高度和自平衡维护成本会随数据量增大而增加，故在极大规模数据集合上也需要关注性能预估。
哈希函数与自定义比较器
对于自定义键类型，应实现一个高质量的 哈希函数，可参考 标准库 std::hash 的组合策略，必要时引入混合哈希方法以提升分布。
自定义键的比较器应提供 严格弱序关系，确保在进行冲突分组时保持正确性，同时避免歧义键导致的错误匹配。
实际代码示例：如何在工程中使用并对比
简单使用场景示例
下面的示例展示了在单词统计任务中的两种容器用法，突出 map 的有序输出与 unordered_map 的高效计数之间的差异。
#include
#include 自定义键类型的示例
当键是自定义结构体时，需要定义哈希与等价性，以便正确使用 unordered_map。
struct Point {int x, y;bool operator==(const Point& other) const {return x == other.x && y == other.y;}
};struct PointHash {std::size_t operator()(const Point& p) const noexcept {// 简单哈希示例return std::hash()(p.x) ^ (std::hash()(p.y) << 1);}
};// 使用
#include
#include
int main2() {std::unordered_map mp;mp[{1,2}]++;
}
