unordered_map查找平均O(1)但最坏O(n)，因哈希冲突退化为链表；自定义类型需特化std::hash避免聚集；预设bucket数、合理哈希函数可优化性能；operator[]会默认构造value，insert/find则不会。
unordered_map 查找操作的实际时间复杂度不是 O(1)
平均情况是 O(1)，但最坏情况是 O(n)——当哈希冲突严重、所有键映射到同一个桶时，unordered_map 退化为链表遍历。这在自定义类型作 key 或哈希函数设计不良时极易发生。
实操建议：
- 默认
std::hash对int、std::string等内置/标准类型足够健壮；但对自定义 struct，必须显式特化std::hash或传入自定义哈希函数对象 - 避免用指针地址或未打乱的内存布局（如简单结构体字节拷贝）直接哈希，易导致聚集。例如：
struct Point { int x, y; };若直接用reinterpret_cast哈希前 8 字节，x=y 的点会大量碰撞 - 插入大量数据后可调用
rehash()或构造时预设 bucket 数（unordered_map<int int> m(1024);</int>），减少后续扩容重散列开销
和 map 查找性能对比：别只看“理论复杂度”
map 是红黑树，查找稳定 O(log n)；unordered_map 平均 O(1)，但有常数项开销：哈希计算、桶索引、可能的链表跳转、缓存不友好。
实际表现取决于数据规模和访问模式：
立即学习“C++免费学习笔记（深入）”；
- n map 往往更快——分支预测好、内存局部性强；
unordered_map的哈希和指针跳转反而拖慢 - n > 10⁴ 且 key 分布均匀时，
unordered_map查找优势明显，尤其随机访问场景 - 若反复查找同一组 key（如热点 key），
unordered_map的哈希结果可被 CPU 缓存，但map的树路径也可能被分支预测器优化 - 注意：
unordered_map::find()返回迭代器，解引用前务必检查是否等于end()；而map同理，但误用后果一样——越界解引用是未定义行为
insert 和 operator[] 的行为差异容易踩坑
operator[] 会在 key 不存在时**默认构造 value 并插入**，哪怕你只是想读取；insert() 和 find() 则不会触发构造。
例如：
struct HeavyObj {
HeavyObj() { std::cout << "constructed\n"; }
HeavyObj(const HeavyObj&) { std::cout << "copied\n"; }
};
std::unordered_map<int, HeavyObj> m;
m[42]; // 即使只写这一行，也会构造一个 HeavyObj！
m.insert({42, HeavyObj{}}); // 显式控制构造时机
更安全的只读习惯是：
- 用
auto it = m.find(key); if (it != m.end()) use it->second; - 需要插入逻辑时，用
try_emplace(key, args...)（C++17 起），它只在 key 不存在时才构造 value - 避免在循环中无条件写
m[key] = val;，除非确定 key 必然存在或接受默认构造开销
迭代器失效规则和线程安全边界
unordered_map 迭代器只在**重哈希（rehash）时整体失效**，即插入导致 bucket 数增长（如负载因子超 max_load_factor）。单次 insert 或 erase 不会使其他迭代器失效——这点和 vector 不同，但和 map 类似。
不过要注意：
-
erase(iterator)仅使该 iterator 失效，其余有效；但erase(key)不影响其他迭代器 - 没有任何成员函数是线程安全的：多线程读+写、或并发写，必须加锁；即使只读，若另一线程正在 rehash，也可能 crash
- 不要在遍历过程中用
operator[]插入新元素——它可能触发 rehash，让当前迭代器立即失效，引发未定义行为
m.load_factor() 和 m.bucket_count() 打印下当前状态，比盲猜有用得多。 
