哈希冲突严重时，std::unordered_map 的查找退化成 O(n) 量级；最坏情况下所有键落在同一桶中，退化为链表遍历，GCC/Clang 实现不自动转红黑树，实测性能可能比 std::map 差 2–3 倍。
哈希冲突严重时，std::unordered_map 的查找退化成什么量级？
最坏情况下，所有键都落在同一个桶里，std::unordered_map 会退化为链表遍历——查找、插入、删除全部变成 O(n)。这不是理论假设，只要哈希函数没打散、或故意构造碰撞输入（比如全用相同哈希值的字符串），就真会发生。
注意：C++ 标准只规定平均 O(1)，不保证最坏情况。GCC 和 Clang 的实现确实用链地址法（单向链表），没有自动转红黑树或跳表来兜底。
- 实测中，10 万个键哈希到 1 个桶，
find()耗时可能比std::map还高 2–3 倍 - 退化后内存占用反而更低（没额外平衡开销），但时间完全不可接受
- 这种退化和键类型强相关：比如自定义类型没重载
hash或用了恒定哈希值，立刻中招
max_load_factor() 和 rehash() 怎么配合防退化？
负载因子 = 当前元素数 / 桶数量。std::unordered_map 默认 max_load_factor() 是 1.0，但触发扩容的阈值不是“刚好等于”，而是“插入后将超过”。所以实际桶数往往比元素数多不少。
- 调用
reserve(n)可以预分配至少能装下n个元素的桶数（按当前max_load_factor推算），避免反复 rehash - 手动设低一点的负载因子，比如
umap.max_load_factor(0.5)，再umap.rehash(0)强制重建哈希表，能显著减少冲突概率 - 但别设太低：桶太多 → 缓存不友好 → 实际性能反而下降，尤其在小数据集上
哪些场景下 std::unordered_map 容易悄悄变慢？
不是只有哈希函数写错才出问题。真实项目里，这些更隐蔽：
立即学习“C++免费学习笔记（深入）”；
- 用
std::string做 key，但大量短字符串内容相似（如"user_1","user_2"...），某些标准库的字符串哈希对连续数字不敏感，容易聚集 - 自定义结构体做 key，只写了
operator==，忘了特化std::hash，结果走默认哈希（可能只哈希地址或返回 0） - 频繁
clear()后不rehash()：桶数组尺寸不变，但元素全空，负载因子骤降，后续插入仍可能因旧桶分布不均而冲突 - 多线程只读不加锁没事，但一边遍历一边
insert()—— 迭代器可能失效，且 rehash 期间整个表锁住（GCC 实现），卡顿明显
替代方案不是非换不可，但得知道边界在哪
std::unordered_map 不是万能高速路。当出现以下信号，该怀疑它了：
- profiler 显示
_M_insert_unique_node或_M_find_before_node占用大量 CPU - 用
bucket_count()和size()算出负载因子长期 > 0.8，且max_load_factor()没动过 - key 类型固定、范围有限（比如枚举值、小整数 ID），直接用
std::vector或std::array下标访问快一个数量级 - 需要稳定遍历顺序或范围查询，
std::map虽然慢点，但逻辑更可预测
哈希表的性能不只取决于算法，更取决于你喂给它的数据长什么样。写完 operator() 别急着跑，先扔几组边界数据进去看看 bucket_size() 分布。
