哈希
常用于需要 \(O(1)\) 比较两个 \(O(n)\) 的东西。可以采用双模数减少冲突概率。
哈希冲突率的粗略计算：可以看做 \(\frac{n}{\prod mod}\)。
字符串哈希
常用于需要 \(O(1)\) 比较两个字符串，可以代替一些字符串匹配的 KMP 题目。以及可以使用哈希 + 二分的技巧 \(\log\) 的时间比较两个字符串的大小。
一般求出每个前缀的哈希值，然后子串哈希值就可以通过差分得到。
比较字符串大小的技巧是，二分第一个出现不同的位置，每次比较使用哈希判断，因此时间复杂度是 \(O(\log len)\) 的。
哈希表
如果不卡 \(\log\) 和常数的话可以使用 map，如果 key 值是标准类型可以使用 unordered_map，如果不是标准类型需要手写哈希函数比较麻烦，而且 STL 常数太大，不如自己手写哈希表。
哈希表的工作原理是对于一个 val 值计算哈希函数，存在桶里，如果不同 val 值的哈希值冲突，则以某种方式换一个地方存储。可以有效处理哈希冲突。
不过由于哈希函数的计算时间取决于 val 的长度，所以如果你需要映射一个数组等很长的东西，可能需要先使用双哈希算出数组的哈希，再把双哈希插入哈希表。
因为出题人不一定可以卡到你的模数，所以哈希表的操作可以看做 \(O(1)\) 的。
哈希表常用模数有 \(1e7+103\)。
拉链法
对于每一个 key 开一个链式前向星结构来处理冲突。比较好理解而且不难写。
板子代码。
const int sz=1e7+103;
struct _hash{
int head[sz];
int f(pii key) {
return (key.fi+key.se)%sz;
}
struct _map {
pii val;
int key;
int num;
int ne;
}mp[N];
int cnt;
void clear() {
while(cnt) head[mp[cnt--].key]=0;
}
int find(pii key) {
int h=f(key);
for(int i=head[h];i;i=mp[i].ne) if(mp[i].val==key) return i;
return 0;
}
void insert(pii key) {
int h=f(key);
int it=find(key);
if(it) mp[it].num++;
else mp[++cnt]={key,h,1,head[h]},head[h]=cnt;
}
int operator [] (int it) const { return mp[it].num; }
}hashmp;