开放地址法需用伪删除标记避免查找断裂，负载因子超0.7必须扩容；链地址法推荐质数桶数、惰性初始化；自定义哈希须组合所有关键字段，避免负值与NaN未处理；除非明确瓶颈，否则不建议替换std::unordered_map。
开放地址法：用 std::vector 手写线性探测哈希表
开放地址法的核心是「冲突时找下一个空位」，不是挂链表。自己实现时最常踩的坑是没处理好删除逻辑——直接删掉元素会导致后续查找断裂。必须用「伪删除标记」（比如设为 DELETED 状态），让查找能继续探查。
典型场景：键值对数量稳定、内存敏感（比如嵌入式或游戏热更新缓存），且不希望指针/动态分配开销。
-
hash(key)后取模得初始位置，冲突就 +1 模数组长度，直到遇到EMPTY或匹配的 key - 插入时若遇到
DELETED，优先填进去（复用空位）；但查找时不能停在DELETED，必须继续 - 负载因子超过 0.7 就必须扩容+重哈希，否则性能断崖下跌——这不是建议，是硬限制
- 别用
int存哈希值再取模，要用size_t防溢出；模运算用位运算（如容量为 2 的幂）可提速，但得自己保证容量始终是 2 的幂
链地址法：用 std::vector<std::list<std::pair<K,V>>> 最简实现
标准库的 std::unordered_map 就是链地址法，但自己实现时容易忽略桶（bucket）的惰性初始化和迭代器失效问题。别一上来就给每个桶都 new 一个 std::list，空桶留 nullptr 或空 std::list 更省内存。
适用场景：插入/删除频繁、键分布不可控（比如用户输入的字符串）、允许少量指针间接访问开销。
立即学习“C++免费学习笔记（深入）”；
- 桶数组大小建议用质数（如 101、1009），比 2 的幂更能打散常见模式的哈希值，减少聚集
- 每次
insert前检查负载因子，超限就扩容——但注意：扩容后所有节点要重新hash % new_capacity，不能只 memcpy - 如果用
std::vector<std::forward_list<>>替代list，插入快但没法高效删中间节点；真要删，得遍历前驱，代价高 - 别把
operator[]实现成「找不到就 insert 默认构造 value」，这会隐式修改容器；显式提供find()和try_emplace()更可控
哈希函数怎么写才不出事
自己写的哈希函数如果只对 int 返回自身，对 std::string 返回 .size()，基本等于没哈希——全撞桶。C++11 起有 std::hash<T> 特化，但自定义类型必须显式提供，且不能只哈希部分成员。
- 结构体哈希必须组合所有关键字段，推荐用
std::hash<T>{}(x) ^ (std::hash<U>{}(y) << 1)再异或，别直接加（加法对小值不敏感） - 字符串哈希别手写 djb2，直接用
std::hash<std::string_view>{}(sv)，它在 libstdc++ 和 libc++ 上都是 SipHash 变种，抗碰撞 - 如果键是浮点数，
std::hash<float>对NaN行为未定义，务必先std::isnan()判断再哈希 - 自定义哈希对象传给
std::unordered_map构造函数时，类型必须满足CopyConstructible，Lambda 不行，得包一层 struct
为什么别轻易替换 std::unordered_map
除非你明确知道它的某处瓶颈（比如分配太碎、哈希不够快、或需要定制内存池），否则自己实现大概率更慢、更易崩。libstdc++ 的 unordered_map 在负载因子 1.0 下平均查找仍是 O(1)，且内部做了小容器优化（small buffer optimization）避免短字符串堆分配。
- 调试时看到
std::bad_alloc或segmentation fault在哈希表操作里，八成是自定义哈希返回了负值（size_t是无符号，负值会绕成极大正数，导致越界访问） - 用 AddressSanitizer 测自研哈希表，大概率暴露出越界读（probe 序列没判空桶就继续）或 UAF（伪删除位没清干净）
- 多线程读写必须加锁——但
std::unordered_map本身也不支持并发修改，这点没区别；真要并发，该上tbb::concurrent_hash_map或分段锁
哈希表最难的从来不是插入和查找，而是「删完之后，别人还能不能正确找到剩下的」。这个状态一致性，比算法本身更耗调试时间。
