std::unordered_map 本质使用链地址法，每个桶存储单向链表，冲突键值对挂于链表中；平均时间复杂度 O(1)，最坏 O(n)；rehash 会重建桶数组并使所有迭代器失效；自定义 key 需同时提供一致的 hash 和 operator==。
std::unordered_map 本质是开放寻址还是链地址法？
它用的是链地址法（chaining），不是开放寻址。底层每个桶（bucket）存一个 std::forward_list 或类似单向链表结构，冲突的键值对就挂在这个链表上。
这意味着：插入、查找、删除的平均时间复杂度是 O(1)，但最坏情况（所有键哈希到同一个桶）会退化成 O(n)——尤其是当哈希函数质量差或负载因子过高时。
- 标准不强制要求具体链表实现，但所有主流实现（libstdc++、libc++、MSVC STL）都用链地址，没用开放寻址
- 你可以用
bucket_count()查当前桶数量，bucket_size(n)查第 n 个桶里链表长度，用来诊断是否严重冲突 - 别手动写哈希函数返回固定值（比如
size_t hash(...) { return 0; }），那会让所有元素挤进第一个桶，性能直接崩
为什么 rehash 会触发整个表重建？
因为 std::unordered_map 的桶数组是连续分配的固定大小数组，不能像 vector 那样在尾部追加。一旦负载因子（size() / bucket_count()）超过 max_load_factor()（默认 1.0），就必须分配新桶数组、重新计算每个元素的哈希值、再逐个插入新桶——这就是 rehash() 干的事。
- rehash 是 O(n) 操作，且会使所有迭代器失效（不只是指向被删元素的那些）
- 如果知道最终大概容量，构造时用
std::unordered_map<int int> m(1024);</int>预分配桶数，比让其反复自动 rehash 更高效 -
m.reserve(1024)效果等同于m.rehash(1024)，都是确保至少有 1024 个桶；但reserve()更语义清晰，推荐用它
自定义类型作 key 时，operator== 和 hash 为什么必须配套？
哈希表查 key 分两步：先算 hash 值定位桶，再在桶内链表中用 operator== 逐个比较。如果 hash 值相同但 operator== 返回 false，就会漏匹配；反过来，如果两个逻辑相等的对象 hash 值不同，根本进不了同一个桶，永远找不到。
立即学习“C++免费学习笔记（深入）”；
- 必须同时提供满足一致性的
std::hash<T>特化和operator==，缺一不可 - 常见错误：只重载了
operator==，忘了写std::hash；或者 hash 里用了浮点字段（精度问题导致相等对象 hash 不同） - 示例：对
struct Point { int x, y; };，正确 hash 应类似return std::hash<int>{}(p.x) ^ (std::hash<int>{}(p.y) << 16);，而不是直接p.x + p.y（易冲突）
迭代器失效规则和指针稳定性很特殊
不同于 std::map，std::unordered_map 的迭代器只在发生 rehash 时批量失效；单次 insert/erase 不会让其他元素的迭代器失效。但更关键的是：**元素指针/引用长期有效**——只要没被删，哪怕中间经历多次 rehash，指向原元素的指针仍可用。
- 这是链地址法带来的特性：元素内存块本身不移动，只是链表指针在桶之间重连
- 可以安全地把
&m[key]存起来后续用，但不能假设m.begin()永远指向同一位置 - 注意 erase 迭代器后，该迭代器立即失效，但其他迭代器不受影响；而 insert 可能触发 rehash，从而让所有现存迭代器失效
哈希冲突本身不可怕，可怕的是没意识到它会导致局部链表过长，或者误以为 rehash 是轻量操作。真正难调的往往是哈希函数和自定义相等逻辑之间的隐式耦合——这里出错，调试时现象就是“明明该找到却返回 end()”，而且毫无报错。
