哈希表底层用vector存桶，推荐vector<forward_list<pair<K,V>>>而非vector<list<pair<K,V>>>，因forward_list内存紧凑、缓存友好、避免双向指针开销；桶数组大小宜取质数以减少哈希冲突。
哈希表底层用什么容器存桶？别直接用 std::vector<std::list<T>>
多数人一上来就写 std::vector<std::list<std::pair<K, V>>>，看似合理，但实际会带来两层间接访问开销：先查 vector 索引，再遍历链表。更关键的是，std::list 每个节点单独堆分配，缓存不友好，插入/查找慢。
推荐用 std::vector<std::vector<std::pair<K, V>>> 或更优的 std::vector<std::forward_list<std::pair<K, V>>> —— std::forward_list 无 size()、无反向迭代，但内存紧凑、单向遍历快，且避免了 std::list 的双向指针冗余。
- 桶数组大小建议用质数（如 13、31、97…），避开 2 的幂次，减少模运算后键分布偏斜
- 初始化时预留容量：
buckets.resize(prime_size)，避免后续反复 resize 导致迭代器失效 - 不要在桶内用
std::map替代链表——它引入红黑树开销，完全违背哈希表 O(1) 设计初衷
开放寻址法里 probe 序列怎么选？线性探测不是万能的
线性探测（hash(key) + i % capacity）实现最简，但容易引发“一次聚集”：连续被占的桶会让新元素被迫挤进更长的连续段，恶化性能。
二次探测（hash(key) + i*i % capacity）能缓解聚集，但要求容量为质数且负载因子 (hash1(key) + i * hash2(key)) % capacity）更均匀，但多一次哈希计算，且 hash2(key) 不能输出 0（通常取 1 + hash(key) % (capacity - 1)）。
立即学习“C++免费学习笔记（深入）”；
- 开放寻址必须支持“懒删除”：删元素不能真清空桶，得设为
DELETED状态，否则断开探测链 -
capacity至少比预期元素数大 2 倍，否则冲突概率陡增，平均查找步数快速上升 - 探测失败时要检查是否已满（或负载因子超限），及时触发 rehash，而非无限循环
std::unordered_map 的哈希函数和等价判断怎么自定义？别只重载 operator==
自定义类型用作 key 时，光写 bool operator==(const MyKey& a, const MyKey& b) 不够。必须同时提供哈希函数对象（仿函数或 lambda），且满足：若 a == b，则 hash(a) == hash(b)。否则 std::unordered_map 会把相等 key 分到不同桶，查不到。
正确做法是显式传入两个模板参数：std::unordered_map<MyKey, int, MyHash, MyEqual>，其中 MyHash 是 struct MyHash { size_t operator()(const MyKey& k) const; };，MyEqual 是 struct MyEqual { bool operator()(const MyKey& a, const MyKey& b) const; };。
- 哈希函数返回值用
size_t，别用int或unsigned long（平台差异大） - 避免在哈希函数里调用虚函数或做 I/O、内存分配等重操作
- 字符串类 key 别直接用
.c_str()哈希——若 string 移动后 c_str() 失效，哈希值突变导致查找失败
rehash 触发时机和迁移逻辑怎么写才安全？别在遍历中扩容
哈希表扩容不是简单把旧桶复制过去。必须重建整个结构：申请新桶数组 → 遍历旧表所有非空桶 → 对每个元素重新计算 hash → 插入新桶。过程中若允许并发读写，需加锁或用原子操作，但更常见的是“写时拷贝”或禁止迭代中修改。
标准库用负载因子（size() / bucket_count()）触发 rehash，默认阈值 1.0，但实际建议设为 0.75；超过后冲突概率指数上升。注意：调用 rehash(n) 是建议新桶数，reserve(n) 是保证至少容纳 n 个元素不触发 rehash。
- 迁移前先
clear()新桶数组，避免残留脏数据 - 旧桶里的
std::forward_list节点不能直接 move——节点内存布局不变，但链表指针需重连， safest 是逐个emplace - 如果 key 类型有异常构造，rehash 过程中抛异常会导致表处于中间态，需强异常安全保证（例如先建新表，成功后再 swap）
哈希函数质量、桶数量选择、冲突解决策略三者耦合极深，改其中一项常要同步调另外两个。线上服务里，哪怕只是把质数表从 101 换成 103，都可能让 P99 延迟波动几个毫秒——这东西没银弹，只有实测。
