手写拉链法哈希表应以 std::vector 桶数组 + std::unique_ptr 节点管理内存，避免拷贝与泄漏；迭代器需绑定实例并检查越界，扩容时重置；模板支持自定义 Hash 与 KeyEqual，结构体须特化 std::hash。
哈希表结构体怎么设计才不踩内存泄漏和迭代器失效的坑
手写拉链法哈希表，核心不是“怎么存”，而是“谁负责释放”。用 std::vector 存桶（bucket），每个桶是 std::list 或自定义链表节点指针；但若直接存 std::pair<const key value></const> 值，插入重复 key 时可能触发多次拷贝——尤其 value 是大对象时。更稳妥的是统一用 std::unique_ptr<node></node> 管理节点，构造时 new，析构时自动回收。
迭代器失效风险主要来自扩容：rehash 时所有旧节点被挪走，原迭代器指向已释放内存。所以手写迭代器必须绑定当前哈希表实例，并在 operator++ 中检查是否越界或桶空跳转；或者干脆不暴露原始迭代器，只提供 for_each 接口。
- 桶数组用
std::vector<:unique_ptr>></:unique_ptr>，不用裸指针数组 - 节点结构体里存
Key和Value的值（非引用），避免生命周期依赖外部 - 禁止在
insert中直接修改桶数组 size —— 必须先rehash再插入，否则后续find可能查错桶
哈希函数和 key 比较怎么适配自定义类型
模板参数里加 class Hash = std::hash<key></key> 和 class KeyEqual = std::equal_to<key></key>，这是标准做法。但注意：若传入自定义 struct，std::hash 默认不支持，必须特化或传入 lambda。例如：
struct Point { int x, y; };
namespace std {
template<> struct hash<Point> {
size_t operator()(const Point& p) const {
return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
}
};
}
比较函数同理：KeyEqual 用于判断两个 key 是否相等（冲突链中遍历时用），不能只比地址，必须比逻辑值。若用 std::equal_to 而没重载 operator==，编译失败。
立即学习“C++免费学习笔记（深入）”；
- 哈希函数输出应尽量均匀，避免
x ^ y这种低熵组合，可用std::hash组合多个字段 - key 类型必须支持拷贝（或移动），且哈希值在对象生命周期内不可变（比如含指针成员且指针会变，就危险）
- 不要在哈希函数里调用虚函数或抛异常，影响性能与异常安全
rehash 触发条件和扩容倍数怎么选才平衡时间与空间
负载因子（load factor）= 当前元素数 / 桶数。标准库通常设上限为 1.0，但手写可设 0.75 更稳：避免链表过长导致查找退化成 O(n)。扩容不是简单 new 两倍桶，必须重新计算每个已有元素的哈希值并插入新桶——因为桶数变了，hash(key) % old_bucket_size 和 hash(key) % new_bucket_size 结果不同。
扩容倍数建议用 2 的幂（如 2、4、8），方便用位运算替代取模：hash & (bucket_size - 1)，前提是 bucket_size 是 2 的幂且 hash 已打散。但首次初始化别设太小（如 1），否则频繁 rehash；推荐初始桶数为 8 或 16。
- rehash 前先分配新桶数组，再逐个迁移节点，迁移完再交换指针，避免中间态不一致
- 迁移过程不能复用旧节点的 next 指针——新桶是空的，必须新建节点或移动语义转移
- 若 value 类型不可移动（如含 const 成员），则必须拷贝；提前用
static_assert(std::is_move_constructible_v<value>)</value>检查
insert 和 emplace 的语义差异在哪，为什么 emplace 更高效
insert 接收一个已构造好的 value_type（即 std::pair<const key value></const>），意味着 key 和 value 都已完成构造；而 emplace 接收可变参数包，直接在桶内节点内存上调用 Node 的构造函数，绕过临时对象创建。对 value 是 string 或 vector 的场景，少一次拷贝/移动很关键。
但注意：emplace 仍需先查重——如果 key 已存在，刚构造的节点得立即销毁。所以实现里要先 find，命中则返回，未命中才 placement-new 构造。
- 不要在
emplace内部调用insert，会造成二次查找 - 若 key 类型构造成本高（如从字符串解析），
emplace的参数应设计为 key 的构造参数，而非整个 pair - 所有插入接口都应返回
std::pair<iterator bool></iterator>，bool 表示是否新插入，便于上层判断
最易被忽略的是异常安全：若 emplace 中 value 构造抛异常，已分配的节点内存必须保证释放，且哈希表状态回滚到插入前。用 RAII 包裹临时节点，或在构造后才挂入链表，是基本防线。
