unordered_map是哈希表实现，map是红黑树实现；前者平均o(1)查找但无序、有rehash开销，后者稳定o(log n)且键有序、内存更紧凑。
unordered_map 是哈希表实现，map 是红黑树实现。核心区别在于底层数据结构不同，导致时间复杂度、有序性、内存占用和适用场景都不同。
查找、插入、删除的时间复杂度不同
unordered_map 平均情况下是 O(1)，最坏情况（哈希冲突严重时）退化为 O(n)；map 稳定为 O(log n)，因为基于平衡二叉搜索树。
- 如果频繁按 key 查找且不关心顺序，unordered_map 更快
- 若需稳定性能保障（如实时系统），map 更可预测
- 大量重复插入/删除时，unordered_map 可能因 rehash 触发瞬时延迟
元素是否有序
map 中的键值对按键自动升序排列（支持 lower_bound、upper_bound、范围遍历等）；unordered_map 无序，遍历顺序取决于哈希值和桶分布，每次运行可能不同。
- 需要迭代时保持逻辑顺序（如打印配置项、按字典序处理）→ 选 map
- 只做“存在性检查”或“随机访问”，不依赖顺序 → unordered_map 更合适
哈希表是怎么工作的（unordered_map 底层原理）
unordered_map 使用开放寻址或链地址法解决冲突（GCC 默认用链地址：每个桶是一个链表头指针）。流程如下：
- 用 hash 函数将 key 映射为 size_t 类型的哈希值
- 对哈希值取模（
hash % bucket_count）得到桶索引 - 在对应桶中线性查找匹配的 key（调用 == 操作符）
- 当负载因子（元素数 / 桶数）超过阈值（默认约 1.0），触发 rehash：分配新桶数组、重新散列所有元素
注意：自定义类型作 key 时，必须提供特化的 std::hash<t></t> 和重载 operator==。
内存与构造开销差异
unordered_map 需要额外空间维护哈希桶和链表指针，初始桶数量通常为质数（如 11、23…），空容器也占一定内存；map 是紧凑的树节点结构，每个节点存 key、value、颜色、左右子节点指针，总内存更可控但每节点指针开销固定。
- 小数据量（
- 大数据量 + 高频增删 → unordered_map 吞吐更高，但要注意控制最大负载因子避免频繁 rehash
- map 更适合内存受限或对缓存友好性要求高的场景（树结构局部性更好）
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
