unordered_map平均O(1)但最坏O(n)，map稳定O(log n)；前者需注意哈希冲突、迭代器失效和内存开销，后者支持有序遍历且迭代器更稳定。
unordered_map 插入和查找平均 O(1)，但 map 稳定 O(log n)
哈希表（unordered_map）在理想情况下插入、查找、删除都是平均时间复杂度 O(1)，而红黑树实现的 map 是严格 O(log n)。但这个“快”只在哈希函数分布均匀、冲突少、负载因子合理时成立。一旦哈希碰撞严重（比如大量键映射到同一桶），unordered_map 会退化成链表遍历，最坏到 O(n) —— 这种情况在自定义类型没写好 hash 或键本身有聚集性时很常见。
实操建议：
- 如果键是
int、string、long long等标准类型，且数据量大（>10⁴）、不关心顺序，优先用unordered_map - 若需按 key 排序遍历（比如 for-range 循环要有序），只能选
map——unordered_map不保证任何顺序 - 测试前先调用
reserve(n)预分配桶数，避免多次 rehash 导致的内存抖动和性能毛刺
map 的迭代器稳定，unordered_map 迭代器可能失效
map 的迭代器在插入/删除其他元素时基本不失效（仅删除当前指向节点时才失效）；而 unordered_map 在触发 rehash（如插入后 size > bucket_count × max_load_factor）时，所有迭代器、引用、指针全部失效。这在循环中边遍历边修改容器时极易出错。
常见错误现象：for (auto it = umap.begin(); it != umap.end(); ++it) 中调用 umap.erase(it++) 可能 crash —— 因为 erase 后 it 已无效，++it 是未定义行为。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 需要边遍历边删，
map更安全；unordered_map必须用erase(iterator)返回的下一个有效迭代器，或改用erase(key) - 避免在循环中反复 insert/erase 触发 rehash：提前
reserve，或批量操作后统一处理
哈希冲突和内存占用差异明显
unordered_map 底层是哈希桶 + 链表/红黑树（C++11 起，单桶节点数 > 8 时自动转树化），空间开销比 map 大不少：除了节点本身，还要维护桶数组（通常 > size）、指针、控制字段。实测 10⁵ 个 int→int 映射，unordered_map 内存占用常高出 30%~50%。
性能影响还体现在缓存友好性：map 的节点在内存中相对紧凑（红黑树父子/兄弟指针局部性尚可），而 unordered_map 的桶分散、链表节点堆上随机分配，cache miss 更高——尤其在小数据量（map 实际耗时反而更低。
实操建议：
- 数据量小（map，省心且未必慢
- 自定义 key 类型必须提供高质量
std::hash特化，否则默认调用std::hash<void></void>或退化为地址哈希，极易冲突 - 用
umap.max_load_factor(0.5)降低冲突率（代价是内存翻倍），适合对延迟敏感场景
实际性能要看 profile，不是看理论复杂度
很多项目盲目替换 map 为 unordered_map 后发现变慢了，原因往往是没测真实 workload。比如 key 是短字符串（std::hash<:string> 内部可能直接 memcpy + 位运算，极快；但若 key 是长字符串或结构体，哈希计算本身就成了瓶颈。
容易被忽略的点：
- 构造
unordered_map时传入自定义哈希或比较函数，模板参数顺序易错：unordered_map<k v hash keyequal></k>，漏掉KeyEqual会编译失败 - 调试时用
umap.bucket_count()和umap.load_factor()查看实际负载，比纯猜更有依据 - Release 模式下编译器对
map的迭代器优化（如 inlining）有时比unordered_map的虚函数调用（如桶访问）更高效
别信“哈希一定快”，先跑 perf 或 google-benchmark，测插入 10k 次、查 10k 次、混合操作的真实耗时。
