C++如何实现哈希表并处理哈希冲突-C++-PHP中文网

哈希表底层用vector存桶，推荐vector而非vector，因forward_list内存紧凑、缓存友好、避免双向指针开销；桶数组大小宜取质数以减少哈希冲突。

c++如何实现哈希表并处理哈希冲突

哈希表底层用什么容器存桶？别直接用 `std::vector<:list>></:list>`

多数人一上来就写 std::vector<:list v>>></:list>，看似合理，但实际会带来两层间接访问开销：先查 vector 索引，再遍历链表。更关键的是，std::list 每个节点单独堆分配，缓存不友好，插入/查找慢。

推荐用 std::vector<:vector v>>></:vector> 或更优的 std::vector<:forward_list v>>></:forward_list> —— 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)）。

开放寻址必须支持“懒删除”：删元素不能真清空桶，得设为 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 分到不同桶，查不到。

C++ 算法竞赛自动化测试数据生成与校验框架

根据原题生成新题面、验证器及完整测试数据，自动套用 testlib 模板，用于用户要求生成测试数据时。

下载

正确做法是显式传入两个模板参数：std::unordered_map<mykey int myhash myequal></mykey>，其中 MyHash 是 struct MyHash { size_t operator()(const MyKey& k) const; };，MyEqual 是 struct MyEqual { bool operator()(const MyKey& a, const MyKey& b) const; };。