哈希表底层用vector+list实现拉链法，关键在于哈希函数设计、质数桶数、自定义类型需特化std::hash和重载==，扩容时需rehash且迭代器失效。
哈希表底层用 vector + list 实现拉链法
拉链法本质就是数组里每个槽位存一个链表，冲突的键值对全塞进同一个链表里。C++ 里最直接的做法是 std::vector 存 std::list，或者更灵活点用 std::vector 存 std::forward_list（单向、轻量）。别一上来就手写链表——std::list 已经够用，除非你明确要控制内存布局或迭代器稳定性。
关键不是“怎么造轮子”，而是“怎么让哈希函数和桶数量配合好”。比如桶数取质数（如 101、1009），能显著降低同余冲突；用 size_t hash = key % bucket_count 前必须确保 bucket_count 是正数，否则取模行为未定义。
- 桶数组大小建议初始化为质数，避免因 2 的幂次导致低位哈希位被忽略
-
std::hash<T>对内置类型可靠，但自定义结构体必须显式特化，否则编译报错error: call to implicitly-deleted default constructor - 插入时先算哈希再遍历链表查重，不查重会允许重复 key（除非业务允许）
自定义类型做 key 必须提供 hash 和 == 运算符
这是最容易卡住的地方：哪怕你只写了 struct Person { std::string name; int id; };，往 std::unordered_map<Person, int> 里塞，也会编译失败。因为 std::hash<Person> 没定义，operator== 也没定义（即使成员都可比，C++17 也不自动合成）。
解决方法只有两个：要么全写在类里（C++20 operator<=> 可简化比较，但 hash 还得自己写），要么在外面特化。推荐后者，更解耦：
立即学习“C++免费学习笔记（深入）”；
namespace std {
template<> struct hash<Person> {
size_t operator()(const Person& p) const {
return hash<string>{}(p.name) ^ (hash<int>{}(p.id) << 1);
}
};
}
bool operator==(const Person& a, const Person& b) {
return a.name == b.name && a.id == b.id;
}
- 异或（
^）不是好哈希组合方式，容易抵消；更稳妥用hash<string>{}(p.name) * 31 + p.id - 特化
std::hash必须在std命名空间，且不能在头文件里多次定义（否则 ODR 违规） - 如果 key 类型带指针或浮点字段，
==和hash必须语义一致，否则查找永远失败
resize 时机和 rehash 的开销很实在
拉链法不怕冲突多，怕的是某条链太长。当平均链长超过某个阈值（比如 8），查找退化成 O(n)，就得扩容。C++ 标准库的 std::unordered_map 默认负载因子上限是 1.0，达到就自动 rehash；但你自己实现时，这个逻辑得手动写——而且不能只扩 vector 大小，还得把所有旧节点重新哈希、插入新桶。
- 每次
rehash都是 O(N) 时间，且会 invalidate 所有迭代器（包括begin()返回的） - 扩容倍数建议用 2x 或 1.5x，别用 1.1x——小步慢跑反而触发频繁 rehash
- 如果已知元素总数，构造时用
reserve(n)预分配桶数，能省掉前几次扩容
迭代器失效只发生在 rehash 时，不是每次 insert
很多人误以为“拉链法 insert 就会让其他迭代器失效”，其实不会。只要没触发 rehash，往某条链末尾 push_back，不影响其他链上的节点地址，原有迭代器照常可用。这点和 std::vector 完全不同。
但要注意：如果你在遍历 map 的同时插入新元素，且恰好触发了 rehash，那当前迭代器立刻变成悬垂指针——这种“边遍历边改”逻辑本身就有风险，标准库也不保证安全。
- 安全做法是：先收集要插入的键值对，等遍历完再批量 insert
-
std::unordered_map::insert返回的pair<iterator, bool>中的 iterator，在本次 insert 不触发 rehash 时有效；若触发，则返回新桶里的位置，旧迭代器全部失效 - 调试时遇到
Segmentation fault且堆栈停在operator*或->，八成是迭代器用了已失效的
实际写的时候，真正麻烦的从来不是链表怎么连，而是哈希函数怎么写不撞车、扩容边界怎么控不抖动、自定义类型怎么塞进去不崩。这些地方错一点，表现出来就是查不到值、反复插入、甚至 core dump。
