std::unordered_map 是标准库实现的哈希表，已完备处理扩容、哈希、冲突解决等细节；手写易出错且性能不优，应优先使用它。
std::unordered_map 是什么，为什么别手写哈希表
除非你在写教学项目或嵌入式受限环境，否则直接用 std::unordered_map。它已处理好动态扩容、哈希函数、冲突链/开放寻址、迭代器失效边界等全部细节。手写容易在负载因子控制、内存对齐、移动语义支持上出错，且性能未必更好。
常见错误现象：std::unordered_map 查找变慢（O(n)）、插入卡顿——往往是因为没预估容量，导致频繁 rehash；或者自定义键没正确实现 operator== 和 std::hash 特化。
- 使用前调用
reserve(n)预分配桶数（不是元素数），尤其已知插入量时 - 自定义键类型必须同时提供：可比较性（
operator==）和哈希计算（特化std::hash<mykey></mykey>或传入哈希仿函数） - 避免用
std::string_view作键时指向临时字符串，生命周期管理一错就 UB
手动实现链地址法时，桶数组大小为什么要用质数
质数桶数能显著降低哈希值分布偏斜带来的冲突率，尤其当键的哈希值本身有规律（比如连续整数、指针地址低位重复）时。用合数（如 16、1024）会让模运算结果集中在少数桶中，退化成单链表遍历。
实际影响：非质数桶数下，find() 平均复杂度可能从 O(1+α) 恶化为 O(n)，α 是负载因子。C++ 标准库内部就用质数序列（如 5, 11, 23, 47…）做桶数增长步长。
立即学习“C++免费学习笔记（深入）”；
- 不要硬编码
bucket_count = 1000，改用std::vector<:list>> buckets(prime_above(n))</:list> - 可用静态查表或运行时小质数生成器，避免每次 insert 都算质数
- 若用开放寻址（线性探测），质数要求可放宽，但仍推荐用质数避免聚集
开放寻址法里，删除元素不能真删，得打“墓碑”标记
线性探测或二次探测中，若直接清除已删除槽位，后续查找会因中断探测链而找不到本应存在的元素。必须保留该位置，并标记为“已删除（tombstone）”，让查找继续探查，插入时才复用。
典型错误：实现 erase(key) 时只清空值，没设墓碑标志，导致之后 find(key) 返回 end() 即使键存在。
- 墓碑需与空槽、有效槽明确区分（例如用
enum SlotState { EMPTY, OCCUPIED, TOMBSTONE }） - 插入时优先复用
TOMBSTONE，其次才是EMPTY；查找跳过TOMBSTONE但不停止 - 墓碑过多会拖慢所有操作，需在负载因子过高或墓碑占比超阈值时触发整体 rehash
std::hash 对自定义类型的特化常被忽略的三件事
编译不报错不代表哈希行为正确：特化没生效、哈希值分布差、跨平台不一致都可能发生。
常见错误现象：std::unordered_map<mystruct int></mystruct> 插入后 find() 找不到，或不同编译器下 map 大小不一致。
- 特化必须在
std命名空间内，且模板参数严格匹配（struct MyStruct和class MyStruct视为不同类型） - 哈希组合不能简单异或字段（
h ^= std::hash<int>{}(a) ^ std::hash<int>{}(b)</int></int>），要用乘加或 std::hash_combine 模式防碰撞 - 避免依赖
sizeof(void*)或未定义行为（如对 padding 字节哈希），否则 x86_64 和 aarch64 结果不同
真正难的是让哈希值在各类输入下都尽量均匀——这没有银弹，但至少别用异或。
