是，但仅平均情况下为O(1)；最坏因哈希冲突退化为O(n)，且依赖高质量哈希函数、合理负载因子及正确自定义类型特化。
std::unordered_set 查找时间复杂度真是 O(1) 吗？
是，但只在平均情况下成立。它依赖哈希函数把 key 映射到桶（bucket）中，理想状态下每个桶只存一个元素，查找就是一次哈希 + 一次比较。一旦发生哈希冲突（多个 key 落到同一桶），就得遍历桶内链表或树（C++11 起部分实现用红黑树处理严重冲突），退化为 O(n)。
- 哈希质量差（比如所有
key哈希值都一样）会直接让性能崩塌 - 元素数量增长时，
unordered_set会自动 rehash，触发内存重分配和全部元素重散列——这瞬间开销不小 - 如果你用自定义类型做 key，必须提供满足要求的
std::hash特化和operator==，否则编译失败
怎么查？别用 operator[]，改用 find() 或 count()
unordered_set 没有 operator[]（那是 unordered_map 的）。查是否存在只能靠：
-
find()：返回iterator，查不到是end()，适合需要取值或后续操作的场景 -
count()：返回size_t（0 或 1），语义清晰，适合纯判断
std::unordered_set<int> s = {1, 3, 5, 7};
if (s.find(5) != s.end()) { /* 存在 */ }
if (s.count(9)) { /* 非零即存在，但这里为 false */ }
- 别写
s.find(x) == s.end() ? ... : ...这种三元嵌套，可读性差且容易漏掉括号 -
count()看似多一次调用，但编译器通常能优化成和find()一样快；优先选语义更直白的那个
自定义类型作 key 时最容易卡在哪？
卡在三件事上：没写 operator==、哈希函数返回值恒定、哈希函数没考虑成员全貌。
C++ Code Review Master
下载
组合式C++代码评审方案，融合静态分析、AI推理、多轮迭代评审和C++专项检查，适用于PR审查、增量代码审查、全项目评审和代码质量评分，触发词包括review cpp、cpp代码评审、C++review、代码审查。
struct Point {
int x, y;
bool operator==(const Point& p) const { return x == p.x && y == p.y; }
};
namespace std {
template<> struct hash<Point> {
size_t operator()(const Point& p) const {
// ❌ 错误：只哈希 x，y 被忽略 → 不同点可能哈希相同
// return hash<int>{}(p.x);
// ✅ 正确：混入 y，避免碰撞
return hash<int>{}(p.x) ^ (hash<int>{}(p.y) << 1);
}
};
}
- 必须同时定义
operator==和hash，缺一不可 - 哈希函数里别用
rand()、time(nullptr)等运行期随机值，哈希值必须稳定 - 对浮点成员做哈希要格外小心：NaN、-0.0、+0.0 的位表示不同，但
==可能为 true，容易不一致
查找快，但初始化和插入慢？注意 load factor 和 bucket_count
默认负载因子上限是 1.0（即平均每个桶最多 1 个元素）。当 size() / bucket_count() > max_load_factor() 时触发 rehash。频繁插入小数据集时，rehash 开销占比很高。
立即学习“C++免费学习笔记（深入）”；
- 插入前预估容量，用
reserve(n)直接分配足够桶数，避免多次 rehash -
rehash(n)强制调整桶数量，n是新桶数，不是元素数 -
max_load_factor(0.75)可设更低值换空间换稳定性，但桶数变多，内存占用上升
std::unordered_set<std::string> s; s.reserve(1000); // 插入前调用，比边插边扩快得多 for (const auto& str : huge_list) s.insert(str);
真正影响查找速度的，往往不是算法本身，而是哈希质量、内存局部性、以及你有没有在插入阶段就埋下 rehash 隐患。别只盯着 find() 那一行代码看。
