手写拉链法哈希表成功的关键是配齐hash函数、bucket_count取值、operator==和std::hash特化；底层容器首选std::vector存桶指针，扩容需完整rehash而非简单resize。
直接说结论：手写拉链法哈希表，核心不是链表怎么写，而是 hash 函数、bucket_count 取值、operator== 和 std::hash 特化这四件事没配齐，编译都过不了，更别说查得对不对。
为什么 std::vector<:list>> 是最稳妥的底层容器选择
不用自己实现链表节点或管理内存，std::list 提供稳定的迭代器（插入/删除不使其他迭代器失效），std::forward_list 虽轻量但不支持 size() 和反向遍历，调试时反而更难定位问题。用 std::vector 存桶指针（如 std::vector<:list>></:list>）能保证 O(1) 桶索引，且扩容时只需重新分配 vector，内部 list 不受影响。
常见错误现象：
- 用
std::vector<:unique_ptr>>></:unique_ptr>—— 多一层间接，无必要，且resize()时 unique_ptr 移动开销白增 - 桶数组大小设为 2 的幂（如 16、256）—— 导致
key % bucket_count实际只依赖 key 低几位，哈希位被浪费，冲突陡增 - 初始化
bucket_count = 0或负数 ——%运算行为未定义，运行时可能 SIGFPE
自定义类型当 key 时，必须显式提供 hash 和 ==
哪怕 struct Point { int x, y; }; 所有成员都可比较、可哈希，std::unordered_map<point int></point> 仍会编译失败：C++ 不自动合成 std::hash<point></point>，也不隐式定义 operator==（C++20 operator 仅管比较，不管哈希）。
立即学习“C++免费学习笔记（深入）”；
实操建议：
- 特化
std::hash必须在namespace std内，且只能定义一次（头文件里加#pragma once或 include guard） - 组合哈希值别用异或（
^）：hash(x) ^ hash(y)在 x/y 互换时结果相同，且易因零值抵消；推荐hash(x) * 31 + hash(y)或hash(x) ^ (hash(y) -
operator==必须和std::hash语义一致：若两个对象==为 true，它们的 hash 值必须相等；反之不强制，但不满足会导致查找失败
扩容（rehash）时最容易忽略的三件事
拉链法不怕冲突多，怕的是某条链长度超过阈值（如平均 > 8）后查找退化成 O(n)。触发扩容不能只 table.resize(new_size)，否则所有旧数据就丢了。
关键步骤：
- 新
table分配后，必须遍历每个旧桶、再遍历每条链表，对每个节点重新计算hash(key) % new_bucket_count，然后插入新桶 —— 这就是 rehash，不是复制 - 旧
table释放前，要确保所有节点已迁移完毕；若用裸指针，此处极易 double-free；用std::list则由其析构自动清理 - 迭代器全部失效：rehash 后所有现存迭代器（包括
begin()/end()返回的）都不能再用，这是标准行为，不是 bug
负载因子控制和质数桶数的实际影响
标准库 std::unordered_map 默认最大负载因子是 1.0，即平均每个桶 ≤ 1 个元素。你自己实现时若设成 2.0，虽然节省空间，但链长方差变大，最坏桶可能有 10+ 节点，查找性能毛刺明显。
桶数取质数（如 101、1009、10007）的真实作用：
- 避免哈希函数低位集中时，
%运算把大量 key 映射到连续几个桶（比如用key & 0xFF当 hash，桶数=256 就全挤在前 256 个桶） - 质数与任意整数互质概率高，能更均匀“打散”余数分布
- 不要迷信“越大越好”：桶数从 101 扩到 1009，rehash 开销增长 10 倍，但冲突减少有限；业务数据量级决定初始桶数，10³ 量级用 101，10⁵ 量级用 1009 更合理
真正容易被忽略的点：哈希函数输出本身是否均匀，比桶数是不是质数影响更大。如果 std::hash<t></t> 对你的 key 类型输出集中在某段区间，换再大的质数桶也白搭 —— 此时得换哈希算法，或者加扰动（如 (hash_val * 2654435761U) >> 24）。
