c++oding="utf-8" ?>
std::unordered_map 的 rehash 是桶数组重建与元素迁移过程，由负载因子超限触发；自定义 key 类型需确保哈希函数和 operator== 稳定、无副作用，且 reserve() 可优化性能。
std::unordered_map 的 rehash 不是手动触发的“重算哈希值”，而是整个桶数组重建+元素迁移的过程；你不能、也不该在运行时修改已有元素的哈希值，但必须理解它何时发生、怎么影响性能、以及为什么自定义类型容易踩坑。
rehash 触发条件：负载因子 > max_load_factor() 时才扩容
std::unordered_map 默认的 max_load_factor() 是 1.0，意味着平均每个桶最多存 1 个元素。一旦插入后导致 size() / bucket_count() > max_load_factor()，就会触发 rehash。
- 不是“满了才扩”，而是“快满就扩”——比如桶数为 8，插入第 9 个元素前，若此时已有 8 个元素，
8/8 == 1.0，再插一个就会超限，触发 rehash - rehash 后桶数通常翻倍（如从 8→16），但标准不强制要求；实际实现（如 libstdc++）会选下一个质数（如 8→11，16→17），避免模运算周期性冲突
- 调用
rehash(n)可主动建议最小桶数，但最终桶数仍由实现决定；reserve(n)更常用，它等价于rehash(ceil(n / max_load_factor()))
自定义类型做 key 时，rehash 期间 operator== 和 hash 函数必须稳定
rehash 要把所有旧桶里的元素重新映射到新桶中，这需要反复调用你的哈希函数和 operator==。如果这两者依赖外部状态或可变成员，迁移过程可能崩溃或逻辑错乱。
- 错误示例：
struct BadKey { mutable int cache; std::string s; size_t hash() const { if (cache == 0) cache = std::hash<:string>()(s); return cache; } };——mutable缓存会在多次哈希调用中被修改，导致同一 key 算出不同哈希值 - 正确做法：哈希函数必须是纯函数（无副作用、不读写对象状态），
operator==必须满足自反、对称、传递性 - 特化
std::hash时，确保它不捕获 this 或引用外部变量；推荐用std::hash()(x) ^ (std::hash ()(y) 这类无状态组合，而非 x ^ y（易碰撞）
链地址法下，rehash 不改变单个桶内元素顺序，但迭代器全部失效
std::unordered_map 使用链地址法（每个桶是链表或红黑树），rehash 本质是：分配新桶数组 → 遍历旧桶 → 对每个节点调用 hash(key) % new_bucket_count → 插入新桶对应链表头部。所以：
- 同一个桶内的元素，在新桶中可能被拆到不同位置，但各自在原链表中的相对顺序，在新链表中仍保持（因为是头插）
-
begin()/end()迭代器、所有现存指针/引用全部失效；operator[]、at()、find()等接口不受影响，它们内部重新计算位置 - 如果你在循环中边遍历边 insert，且未预留空间，极可能中途 rehash，导致迭代器失效并引发未定义行为（UB）——务必先
reserve()
性能关键点：避免高频 rehash，但也不要盲目 reserve 过大
rehash 是 O(n) 操作，涉及内存分配 + n 次哈希 + n 次比较 + 链表重建。一次 rehash 延迟可能达数百纳秒到微秒级，对实时性敏感场景不可忽视。
- 已知元素总数？直接
reserve(expected_n)，比默认从 1 个桶开始、反复翻倍更高效 - 动态增长但上限明确？例如日志缓存最多存 10000 条，
reserve(10000)可基本消除运行时 rehash - reserve 过大？浪费内存，且桶数组过大时，CPU 缓存局部性下降，反而降低查找速度；实测显示桶数在 2×~4× 预期 size 之间较均衡
- 注意：
reserve()不改变size()，只影响bucket_count()；rehash(0)会强制收缩（但标准库不保证收缩到多小）
真正难处理的不是 rehash 本身，而是当你的自定义 hash 函数在不同编译器或 STL 版本下输出不一致时——它不会报错，但会导致 map 行为诡异（如 find 失败、重复插入）。务必用固定种子的哈希算法（如 std::hash 的标准特化），别自己手写带随机性的混合逻辑。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
