一些不常见的关于哈希表的 trick
效率对比
一般 常见的四个 hash 表的效率比较如下:
map < unordered_map < cc_hash_table < gp_hash_table
map
map 是红黑树实现的，插入和查询的时间复杂度每次都稳定在 \(O(\log n)\)。
头文件及常用函数
头文件为<map>
常用的函数有：
- count(x) 返回指定元素的出现次数
- size() 返回元素个数
- empty() 返回是否为空，为空时返回 true
- find(x) 查找某个元素，返回的是迭代器
- insert(x) 插入某个元素
- clear() 清空 map
- map.erase(x / it) 删除某个值的迭代器/迭代器
- begin() 返回头部的迭代器
- end() 返回末尾的迭代器
注意事项
- map 也可以使用 [ ] 形式访问元素的出现次数，但是当使用这种方法访问了不存在的元素 x 时，会插入一个 新的元素 {x,0}。
设 map 的存储大小为 n，询问次数为 m。如果使用 [ ] 的方式查询元素的出现次数，时间复杂度将从 \(O(m\log n)\) 变为 \(O(m\log(n+m))\)。
虽然没有改变时间复杂度的数量级，但是会无声中增加一些可能导致 TLE 的常数，如果查询值的键值为 \(0\) 还有其他的意义，还会导致代码 WA 掉。如果不知道这件事的话，想必碰到的时候诸位一定调到心态爆炸吧。
unordered_map
unordered_map 的实现就是哈希表，也即散列表。
unordered_map 通过相关的映射函数来加快寻找速度，因此，如果数据随机，unordered_map 的插入和查询速度接近 \(O(1)\)。但是由于 hash 冲突的存在，能被一些特意构造的数据卡到 \(O(n)\) 的时间复杂度，当然，我们可以通过手写 hash 函数的形式来尽量规避此类问题。
头文件及常用函数
头文件为 <unordered_map>
常用函数与 map 基本相同。
注意事项
- 在 STL 中 map 和 unordered_map 在两个不同的头文件中，这也体现了它们的底层实现不同的特点。
- 在 cf 中 unorderd_map 经常会被卡崩导致 TLE，因此保险起见在复杂度正确的情况下还是用稳定的 unordered_map 比较好。
关于 map 和 unordered_map 的对比
- 在空间上，由于 map 的底层实现是红黑树，因此占用的空间比 unordered_map 大
- 稳定性上，map 的时间复杂度稳定在单次 \(O(\log n)\)，但是 unordered_map 可以被卡成单次 \(O(n)\) 导致 TLE(
梦回 spfa)。因此如果在 map 的时间复杂度正确的情况下请使用 map 实现，否则给 unordered_map 加一个自定义函数或者手写哈希表更好。 - 时间效率上，如果保证数据随机或者答案对单次询问的性能要求不是很高，可以考虑用 unordered_map 实现，否则最好用 map。
- 其他功能：map 在维护的过程中也同时保证了序列是有序的。
cc_hash_table /gp_hash_table
cc_hash_table 和 gp_hash_table 都属于 pb_ds 库中，又称“平板电视”。虽然是扩展库，但是两个的效率和实用性仍然很高。
二者查询和插入的时间效率都为均摊 \(O(1)\)。
使用及命名
需要引用头文件和命名空间：
#include<ext/pb_ds/hash.policy.hpp>
using namespace __gnu_pbds;
其中 cc_hash_table 是通过拉链法处理哈希冲突的，而gp_hash_table 是通过探测法处理哈希冲突的。二者时间效率相当，一般探测法更快一些。
二者的命名如下：
gp_hash_table<type,type>gp;
cc_hash_table<type,type>cc;
大多数函数与 map 相同，其中有一点特例就是 count(x) 函数，因此可以用 find(x)!=end()的方式查询。同样也会存在数组形式访问时插入无用元素的特点。
需要注意的是:
gp_hash_table 可能会被卡，处理措施是自定义哈希函数，cc_hash_table 一般不会被直接卡炸。这主要与二者的底层实现有关，具体可以参考这里。
如何防止 unordered_map 或 gp_hash_table 被 hack？
手写一个 hash 表或者给 unordered_map 或 hash_table 手写一个哈希函数
下面是一个防止卡 hash 的手写函数模板，来源请看结尾，主要作用就是防止 unordered_map 或 gp_hash_table 被卡。(侵删)
struct custom_hash //手写的 hash 函数
{
static uint64_t splitmix64(uint64_t x)
{
x+=0x9e3779b97f4a7c15;
x=(x^(x>>30))*0xbf58476d1ce4e5b9;
x=(x^(x>>27))*0x94d049bb133111eb;
return x^(x>>31);
}
size_t operator()(uint64_t x) const
{
static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
return splitmix64(x + FIXED_RANDOM);
}
};
unordered_map<long long, int, custom_hash> safe_map;
gp_hash_table<long long, int, custom_hash> safe_hash_table;
如果你想更加透彻的了解 pbds 的强大功能以及与 STL 时间效率的对比，我推荐这篇博客给您。
参考资料：
c++ 中的 map, unordered_map, cc_hash_table, gp_hash_table