结论：std::unordered_map查找平均O(1)但易退化至O(n)，因哈希碰撞、重哈希、低质哈希函数所致；自定义键须完备实现相等比较、哈希特化及一致性，否则编译失败或运行时UB。
直接说结论：用 std::unordered_map 做查找，平均 O(1)，但实际性能和键类型、哈希函数、负载因子强相关；别把它当“万能字典”硬套，否则查得慢、崩得快。
为什么 unordered_map 查找有时比 map 还慢？
底层是哈希表，但哈希碰撞多、重哈希频繁、或键类型哈希质量差时，单次 find() 可能退化到 O(n)。比如用 std::string 当键没问题，但用自定义结构体没写 std::hash 特化，编译直接报错；写了但哈希函数返回常量（如总 return 42），所有元素挤进一个桶，查找就变链表遍历。
- 检查是否触发了 rehash：插入后
load_factor() > max_load_factor()会扩容，此时迭代器全失效，且耗时突增 - 避免用指针地址、浮点数、未归一化的
std::string_view当键——哈希值不稳定 - 小数据量（std::map 的红黑树常比哈希表更稳，别迷信“O(1)”
find() 和 operator[] 查找行为差异
两者都做哈希查找，但语义完全不同：find() 只读不改，返回迭代器，查不到就是 end()；operator[] 会默认构造键对应值（哪怕你只读），可能意外插入脏数据，还触发哈希计算+内存分配。
- 只查不改 → 用
find()，配合!= end()判断 - 查到了要取值 → 解引用
find()返回的迭代器，别用operator[]再查一遍 - 确定键一定存在且想顺便插入默认值 → 才用
operator[]，否则大概率埋坑
示例：auto it = cache.find(key); if (it != cache.end()) return it->second; —— 安全、零副作用。
自定义类型当键时，必须搞定三件事
缺一不可，少一个编译失败或运行时 UB（未定义行为）。
- 提供相等比较：
bool operator==(const MyKey& a, const MyKey& b) - 提供哈希特化：在
std::hash命名空间内特化struct hash，重载operator() - 确保哈希一致性：若
a == b为 true，则hash(a) == hash(b)必须为 true（反过来不强制）
常见翻车点：哈希函数里漏掉某个成员变量，或用了 std::hash 直接哈希浮点数——NaN 和 -0.0 的哈希值可能不一致。
真正麻烦的从来不是怎么写 insert() 或 find()，而是哈希函数写对没、负载因子悄悄涨到 2.0 了没、迭代器还在用上次的地址却已被 rehash 失效了——这些细节不盯住，程序跑着跑着就慢，或者崩在深夜三点。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
