[学习笔记]更全面的哈希总结

观前提示: 本篇博客主要是关于算法竞赛领域的哈希

哈希的思想

Hash 的核心思想在于，将输入映射到一个值域较小、可以方便比较的范围

对于字符串 , 可重集之类的需要 \(O(n)\) 比较的输入 , 如果能够将其映射为一个32位数或者64位数 , 就可以更方便地比较 , 这就是字符串哈希.

或者对于很大的值域 , 如果能够将每个值映射到一个较小的 , 计算机能够存的下的空间 , 就可以实现更大值域下标的存储 , 这就是哈希表 .

但是 , 哈希更接近于一种 "想法" , 以及衍生出的各种应用 .

哈希冲突

根据抽屉原理 , 哈希的操作必然会使得多个输入对应了同一个哈希值 . 这就是哈希冲突 .

这要求更合理的哈希函数 , 减少冲突的可能性 .

事实上 , 称原值为 \(val\) , 哈希值为 \(hsh\) , 那么 \(hsh_1=hsh_2\) 是 \(val_1=val_2\) 的必要不充分条件 .

但是只要 \(hsh_1=hsh_2 \wedge val_1 \ne val_2\) 是一个小概率事件 , 就可以姑且认为这是一个充分必要条件 .

哈希可以总结为用一种不严格对应的方法 , 强行减少了比较问题的规模 .

另一种方法是通过双哈希 , 给每一个原值用不同的构造方法构造两个哈希值.

假设原值的值域大小是 \(m\) , 哈希值的值域是 \(n\) , 通过双哈希就可以把哈希值值域扩展到 \(n^2\) , 大大减少了冲突的可能性 .

哈希函数

应该满足以下的要求 :

分散性 . 应该尽可能让原值值域经过映射之后 , 结果不会出现集中在某一个哈希值 .

值域足够大 . 根据抽屉原理 , 如果实际用到的哈希值数量大于值域 , 必然会出现冲突 . 因此要尽可能保证哈希的值域远大于实际应用到的个数 .

如果应用于加密 , 还应该做到不可逆或者难逆 .

相反 , 如果需要便利的合并等操作 , 就要求一定的可逆性 . ( 比如直接删除多重集的一个元素 )

对于不同的问题 , 还可能需要其他的性质 . 例如字符串哈希需要有序 , 而多重集哈希则要求无序.

虽然大多数哈希的应用有受一般认可的构造方式 , 构造哈希函数并不是一件一成不变的事 .

取模

用于把哈希值约束在较小值域 .

几乎所有的哈希方法都涉及到取模操作 . 双哈希最好采用不同的模数 .

模数最好取质数 ( 尤其在一些完全是多项式哈希函数中 ) , 或者选择 unsigned long long 自然溢出 ( 好处是速度快 ) .

和哈希 , 积哈希

用于将多个元素合并成一个整数 . 也可以把一个字符串/ \(n\) 位数的每一位看成一个元素而合并 .

加法 , 乘法操作具有交换律 . 简单地把权值相加 , 结果是无序的 . 即 1 2 3 和 2 1 3 是一样的 .

用加法 , 乘法构造多项式可以混合出我们想要的哈希函数 .

例如 , 字符串哈希要求有序 . 因此一般的方法是将其看成一个 \(k\) 进制数 . 而构造这个 \(k\) 进制数就是一个加 , 乘的过程 :

\[h_i=h_{i-1} \times k+a_i

\\ =\sum_{j=1}^{i} k^{i-j}a_i

\]

也就是给每个数位乘了一个 \(k^{\omega}\) 作区分 .

查表哈希

一种一般不可逆的哈希 . 直接给每个原值赋予一个权值 , 并记录下来 . 可以用 rand() 赋予权值 .

作用是打乱原来可能有某些性质的哈希 , 让哈希值变得混沌 ,随机. (让哈希变得难卡 )

例如 , 对于从 \(1\cdots n\) 中取的多重集 , 简单地应用和哈希会出现 1 2 3 和 2 2 2 冲突之类的情况 .

可以给\(1\cdots n\) 分别赋权 \(rnd _i\) 再做和哈希 , 可以降低冲突的可能 .

位运算哈希

一种更高效的方式 ,主要用异或 ^ 操作和移位 >> << 操作 , 好处是打乱的同时 , 相比需要记录所有权值的查表哈希更高效 , 可以处理更大的值域 .

举个例子

ull xorshift(ull x) {

x ^= 12345678;

x ^= x << 11;

x ^= x >> 7;

x ^= x << 13;

x ^= 12345678;

return x;

}

注意不要单纯的用移位操作 , 这会导致哈希冲突 !!!

x >> = 3 \\ 错误示范 ! 这会导致除了后三位全部相同的哈希值冲突

此外 , 注意代码实现上不要用 hash作变量名 , 因为 std 占用了这一关键字 , 会导致包括 OI 比赛评测使用的 g++ 9.3.0 不过编译 .

字符串哈希

最基础的应用 . 用于比较字符串是否相等 .

构造方式

广为接受的方式就是视作 \(k\) 进制数 , 用一个多项式维护 :

\[h_i=\sum_{j=1}^{i} k^{i-j}a_i

\]

这种方式的好处是 , 能够快速计算子串的哈希值 .

缺点是 , 卡这种构造的方法还是存在的 . 出题人也许会对着常用的 \(k\) 值以及模数 \(modp\) 卡 . 更稳妥的方式是双哈希 .

常见应用

获取字串哈希值

\[hash(l,r)=h_r-h_{l-1}\times k^{r-l+1}

\]

这赋予了在 \(O(1)\) 内比较两个子串的可能性 .

二分+哈希

配合二分 , 就可以实现 :

\(O(n\log n)\) 统计回文子串 .

对字符串维护正向和反向的哈希 . 以每一个下标和每一个两个下标直接的空隙二分出最长的以当前位置为中心的回文子串 .

$O(\log n) $ 求两个串的 $\mathrm{LCP / LCS} $ (最长公共前缀/后缀 ) .

直接二分即可.

$O(n \log^2 n) $ 求 \(\mathrm{SA}\) 数组 .

利用 std::sort , 把比较函数定义成二分哈希求 \(\mathrm{LCP}\) .

哈希表

使用哈希思想的一种数据结构 . 一般是通过哈希把键值 \(key\) 映射到可存储的下标值域 ( 比如 \(10^6\) ) , 再用数组存储 .

构造方式

我们的目的是尽可能均匀地将键值分配到存储空间中 . 因此随意构造足够随机 , 分散的哈希函数防止被卡即可 .

处理冲突

哈希表的特殊性在于 , 因为内存限制 , 可接受的哈希值的值域较小 , 完全避免哈希冲突不太可能 , 这要求我们找出一种处理冲突的方式 .

拉链法

在每一个下标位置上维护一个链表 , 把哈希值相同的所有值存进链表 .

探测法

一旦当前位置被占据 , 就查看向后一个位置是否有值 , 直到有一个空位 .

C++自带哈希表

std

在 ::std 中 , unordered_set ,unordered_multiset, unordered_map都是使用哈希实现的 , 单次操作都是 \(O(1)\) .

其中 unordered_map 比较常用 , 用法和 map 相同 .

注意这些数据结构和不带 "unordered" 的对应数据结构相比 , 在用迭代器迭代时 , 元素是无序的 .

注意 unordered_map 常数偏大 , 有可能被卡

pbds

::__gnu_pbds 下提供了相对更高效的哈希表.

#include

#define pd __gnu_pbds

pd::gp_hash_table mp1; // 探测法

pd::cc_hash_table mp2; // 拉链法

和 std 的 unordered_map 类似 , 支持 .find() 以及 [] 的重载运算符 , 但是没有 .count.

其中 gp_hash_table 相对而言更快一小点 , 在卡常上很有用 .

其他常见应用

树哈希

用于构造一棵有根无标号树的方式 .

一种写法是 :

\[h_u=k , k是常数 , u是叶子

\\h_u=k+\sum_v\mathrm{shift}(h_v)\ ,u不是叶子

\]

\(\mathrm{shift}\) 操作一般用位运算哈希操作 .

简单研究一下正确性 :

首先 , 单节点树对应 \(k\) .

对于每个多节点树 , 相当于用和哈希合并了所有儿子的哈希值 . 这保证了只要树形态相同 , 子树直接可以任意互换而哈希值不变 .

\(\mathrm{shift}\) 操作一般用位运算哈希 , 这保证了哈希值的分散性 .

这种写法的另一种优势是在根节点处存的哈希值是单纯的子树的和哈希 . 这非常方便换根 .

可重集哈希

最简单的一种应用 . 相对于字符串哈希 , 没有用额外的操作标记顺序 , 直接上和哈希 .

但是偏偏是这种很简单的应用,在做题时常常容易忽略 .

具体操作很简单 , 查表或者位运算哈希都能提供足够随机的哈希函数 , 再用和哈希合并.

例题

为了前面思路连贯 , 把题全放在这里 . 主要是字符串和哈希表之外的哈希应用 .

[NOI2024] 集合

题意

给定两个序列 \(A_n\) , \(B_n\) , 他们的元素是一个无序三元集合 \({x,y,z}\) . 进行 \(q\) 次询问 , 每次询问是否有一个置换 \(p_i\) , 使得 \(A_l \cdots A_r\) 中所有三元集合的元素经过这个置换处理后 , 等于 $B_l \cdots B_r $ .

注意两个元素相同顺序不同的三元组视为相等 , 但是序列 \(A_l \cdots A_r\) 与 $B_l \cdots B_r $ 顺序不同则视为不相等 .

$n=2e5 , x,y,z\le m , m=6e5 , q=1e6 $

题解

Trick :

序列 \(a\) 经过置换后与 \(b\) 相等 , 那么置换前的值 \(x_i\) 在序列 \(a\) 中出现的位置应该等于置换后的值 \(y_i\) 在 \(b\) 中出现的位置 .

也就是判定由每一个值 \(x_i\) 出现位置构成的集合是否相等 .

用一个01串就可以标记单个值出现位置 , 把这个01串用字符串哈希构造出哈希值 , 再把值域内所有元素视为一个集合合并出一个哈希值即可 .

这道题虽然每个位置是三元组 , 但是与上述问题并没有区别 , 可以用哈希的方法判断一个区间是否满足 .

如何处理多次询问 ?

发现一个区间合法的必要条件是所有子集都合法 , 那么可以预处理出每个右端点 \(r\) 对应的最大合法 \(l_m\) , 查询时直接把 $l $ 与 \(l_m\) 比较 .

因为这道题哈希的构造比较复杂 , 是一个集合哈希套字符串哈希 , 似乎很难快速计算一个区间的哈希值 . 那就退而求其次 , 发现随着 \(r\) 增大 , \(l_m\) 是不减的 .

而可以容易地在一个区间基础上加上或者减去一个元素 , 具体地 :

\[h(l,r)=\sum_{i=1}^{m}\mathrm{shift}(\sum_{j=l}^{r}k^{j}\times[i\in A_j])

\]

每次增加一个位置 , 可以发现只有新增加的三元组内 \(3\) 个元素的哈希值会发生变化 , 那就只更新这三个元素 , 进而更新总的哈希值就可以了 .

这样就可以维护一个指针指向 \(l_m\) , 随着右端点 \(r\) 移动 , \(l_m\) 右移直到区间合法 , 就可以解决这道题 .

点击查看代码

#include

#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)

#define ll long long

#define ull unsigned long long

#define INF 0x3f3f3f3f

#define INF64 1e18

using namespace std;

constexpr int N=6e5+5;

ull shift (ull x){

x^=1145141919810;

x^=x<<13;

x^=x>>3;

x^=x<<7;

x^=1145141919810;

return x;

}

ull bas[N];

struct hsh{

ull h[N],val;

void insert(int x,int y , int z,int pos){

val-=shift(h[x]); val-=shift(h[y]); val-=shift(h[z]);

h[x]+=bas[pos]; h[y]+=bas[pos]; h[z]+=bas[pos];

val+=shift(h[x]); val+=shift(h[y]); val+=shift(h[z]);

}

void del(int x,int y , int z,int pos){

val-=shift(h[x]); val-=shift(h[y]); val-=shift(h[z]);

h[x]-=bas[pos]; h[y]-=bas[pos]; h[z]-=bas[pos];

val+=shift(h[x]); val+=shift(h[y]); val+=shift(h[z]);

}

}ha,hb;

int n,m,qq;

int res[N];

struct aaa{int x,y,z;} a[N],b[N];

int main(){

ios::sync_with_stdio(false);

cin.tie(0);cout.tie(0);

cin>>n>>m>>qq;

bas[0]=1;

for(int i=1;i<=n;i++) bas[i]=bas[i-1]*67;

for(int i=1;i<=n;i++) cin>>a[i].x>>a[i].y>>a[i].z;

for(int i=1;i<=n;i++) cin>>b[i].x>>b[i].y>>b[i].z;

int lm=1;

for(int i=1;i<=n;i++){

ha.insert(a[i].x,a[i].y,a[i].z,i);

hb.insert(b[i].x,b[i].y,b[i].z,i);

while(ha.val!=hb.val&&lm!=i)

ha.del(a[lm].x,a[lm].y,a[lm].z,lm),

hb.del(b[lm].x,b[lm].y,b[lm].z,lm),lm++;

if(ha.val==hb.val) res[i]=lm;

else res[i]=i+1;

}

while(qq--){

int l,r;cin>>l>>r;

if(res[r]<=l) cout<<"Yes\n";

else cout<<"No\n";

}

}

总结

从整体视角考虑 , 使得原来神秘的问题不再神秘 .

抓住置换前后序列的联系 , 发现 Trick , 随后发现可以转化为集合之间的比较问题 .

比较经典的离线和预处理想法 .

混合方法构造出想要的哈希函数 , 使之支持快速修改 .

独特的树叶

题意

给出 \(n\) 个节点的树 \(T\) , 和 \(n+1\) 个节点的树 \(T'\) .其中 \(T'\) 是将 \(T\) 的序号打乱 , 再加上一个叶子节点构成的 . 求新加入的节点在 \(T'\)上的编号 .

\(n=1e5\)

(bzoj4754)

题解

树哈希维护的是有根树的形态 , 通过换根可以处理无根树 .

对于树 \(T\) , 可以把每个节点作为根的哈希值都扔到 map 里 .

对于树 \(T'\) , 同理地 , 计算哈希值 , 在叶子节点处用哈希值在 map 里查询即可.

点击查看代码

#include

#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)

#define ll long long

#define ull unsigned long long

#define INF 0x7fffffff

#define INF64 1e18

using namespace std;

constexpr int N=1e5+5;

ull h[N],mask=1145141919810;

ull shift(ull x){

x^=mask;

x^=x<<13;

x^=x>>11;

x^=x<<7;

x^=mask;

return x;

}

vector e[N];

int n;

void dfs1(int u,int fa){

h[u]=1;

for(auto v:e[u]){

if(v==fa) continue;

dfs1(v,u);

h[u]+=shift(h[v]);

}

}

map mp;

void dfs2(int u,int fa){

mp[h[u]]=1;

for(auto v:e[u]){

if(v==fa) continue;

h[u]-=shift(h[v]);

h[v]+=shift(h[u]);

dfs2(v,u);

h[v]-=shift(h[u]);

h[u]+=shift(h[v]);

}

}

int res;

void dfs3(int u,int fa){

for(auto v:e[u]){

if(e[v].size()==1){

if(mp.count(h[u]-shift(h[v]))) res=min(res,v);

}

if(v==fa) continue;

h[u]-=shift(h[v]);

h[v]+=shift(h[u]);

dfs3(v,u);

h[v]-=shift(h[u]);

h[u]+=shift(h[v]);

}

}

int main(){

ios::sync_with_stdio(false);

cin.tie(0);cout.tie(0);

cin>>n;

for(int i=1;i

int u,v;cin>>u>>v;

e[u].push_back(v);

e[v].push_back(u);

}

dfs1(1,1);

dfs2(1,1);

for(int i=1;i<=n;i++) e[i].clear();

for(int i=1;i<=n;i++){

int u,v;cin>>u>>v;

e[u].push_back(v);

e[v].push_back(u);

}

dfs1(1,1);

res=INF;

dfs3(1,1);

cout<

}

总结

经典的树哈希应用 , 通过换根维护无根树 .

网络攻防

题意

给出一个点数为 \(n\) 边数 \(m\) 无向图 , 求去掉 \(k\) 条边使得原图不连通的方案数 .

注意 : \(k\le 2\) .

\(n,m\le1e6\) .

题解

首先考虑 \(k=1\) 时的情况 , 很显然 , 只有去掉原图的割边才能使原图不连通 .

\(k=2\) 时 , 去除割边仍然可行 , 除此之外只需再去除一条任意边 .

考虑同时去除两条非割边 , 使原图联通的方案 . 这可以放在 tarjan 流程中研究 , 可以发现一些容易看出的性质 :

去掉其中一条边之后另一条边必须是割边 .

必须去除树边 , 否则必然联通 .

综合后就可以得到一些足够强的结论 :

如果去除一条树边 , 一条返祖边 . 那么这条割边必然只能被一条返祖边跨越 . 证明显然 .

如果去除两条树边 , 那么跨越它们的返祖边集合应该相等 .

证明 : 这相当于去除一条树边 , 而希望另一条树边成为割边 .

去除一条树边的最直接的影响就是任意一条跨过它的返祖边成为了新的树边 , 而所有返祖边的交集因为dfs序的变化 , 恰好变为了割边 .

简单画图手玩就可以比较显然地发现这一点 .

前一种情况 , 直接在 tarjan的同时树上查分统计有几条返祖边即可 .

后一种情况 , 需要判断集合是否相等 , 这完全可以使用哈希 , 简单的多重集哈希即可 .

点击查看代码

#include

#define file(x) freopen(#x ".in","r",stdin),freopen(#x ".out","w",stdout)

#define int long long

#define INF 0x3f3f3f3f

#define INF64 1e18

using namespace std;

constexpr int N=2e5+5;

constexpr int p=1e9+7;

int n,m,k;

vector e[N];

int dfn[N],tot,w[N],fa[N];

int cnt1,cnt2;

map ,int> mp,cnt3;

int pn;

set st;

pair h[N];

vector del[N];

void dfs(int u){

dfn[u]=++tot;

for(auto v:e[u]){

if(v==fa[u]){ fa[u]=0; continue;}

if(dfn[v]&&dfn[v]

w[u]++;w[v]--;

pair tmp={min(u,v),max(u,v)};

if(!mp.count(tmp)) mp[tmp]=++pn;

int x=mp[tmp];

h[u].first=(x*x*18+7+h[u].first)%p;

h[u].second=((x^((x>>3)<<5))*(x^((x>>1)<<2))%p+h[u].second)%p;

del[v].push_back(pn);

}

else if(!dfn[v]){

fa[v]=u;

dfs(v);

w[u]+=w[v];

h[u].first+=h[v].first;

h[u].second+=h[v].second;

}

}

for(auto x:del[u]) {

h[u].first=(h[u].first-x*x*18%p-7+2*p)%p;

h[u].second=(h[u].second-((x^((x>>3)<<5))*(x^((x>>1)<<2)))%p+2*p)%p;

}

if(u!=1){

if(w[u]==0) cnt1++;

else if(w[u]==1) {

cnt2++;

}

}

if(w[u]){

if(!cnt3[h[u]]) cnt3[h[u]]=1;

else cnt3[h[u]]++;

}

}

signed main(){

file(attack);

ios::sync_with_stdio(false);

cin.tie(0);cout.tie(0);

cin>>n>>m>>k;

for(int i=1;i<=m;i++){

int u,v;cin>>u>>v;

e[u].push_back(v);

e[v].push_back(u);

}

dfs(1);

int res=0;

if(k==1){

cout<

}

if(cnt1>=2) res=cnt1*(cnt1-1)/2;

res=res+cnt1+cnt2+cnt1*(m-cnt1);

for(auto x:cnt3)

res=(res+x.second*(x.second-1)/2);

cout<

}

总结

连通性问题 , 从 tarjan 切入思考 .

通过实际手玩研究性质 , 再用性质找到能解决问题的结论 .

结论中的集合判断 , 联想到哈希.

[CSP-S2022] 星战

题意

给一个有向图 , 有四种操作 :

删除一条边 .

删除一个节点的所有入度 .

恢复原来存在的一条边 .

恢复一个节点原来存在的所有入度 .

每次操作后问是否能做到 :

每个点只有一个出度 .

从每个点出发可以走出无限长度的路径 .

题解

首先 , 只要基本图论常识就可以发现第一个条件满足的就是构成内向基环森林 , 此时第二个条件自然满足 .

于是我们需要保证每一个点的出度为 \(1\) , 然而 , 题中的大部分操作均与入度相关 .

我们发现我们并没有特别好的数据结构去更新一个点周围的所有点 . 着眼于单点维护并不可行 , 这迫使我们从整体的角度考虑 .

如果把所有的边视为一个集合 , 要判断的就是这些边的起点是否 \(1 \cdots n\) 恰好每个出现一次 . 抓住关键点 : 每个点的起点 , 可以直接研究当前存在的边的起点集合 . 此时问题变成了 :

在集合中加入或删除一个起点 .

把可以到达当前节点的所有点从集合中删除 .

把能通过原来被删除的边到达当前节点的点加入集合 .

查询当前集合是否 $={1 \cdots n} $ .

涉及可重集维护 , 而且还有比较操作 . 启发我们用哈希来维护 , 具体地 :

为了方便更新对点所有入度的操作 , 再维护一下连向这个点的起点有哪些在集合中 , 哪些不在 .

加入/删除一条边时 , 在整体集合和这条边的出发点集合分别操作 .

对一个点所有入度操作时 , 直接整体合并整体集合和这个点维护的集合 .

哈希方式可以采取简单的和哈希 , 对每个点随机一个哈希值就行 .

点击查看代码

#include

#define ll long long

using namespace std;

const int INF=0x7fffffff;//const ll INF=1e18;

const int N=500005;

const int p=10000007;

int n,m;

ll g[N],r[N],w[N],sum,tmp;

int main(){

cin>>n>>m;

for(int i=1;i<=n;i++){

w[i]=rand()%p;

sum+=w[i];

}

for(int i=1;i<=m;i++){

int u,v;

cin>>u>>v;

g[v]+=w[u];

r[v]=g[v];

tmp+=w[u];

}

int q;cin>>q;

while(q--){

int tag;

cin>>tag;

if(tag==1){

int u,v;cin>>u>>v;

tmp-=w[u];

r[v]-=w[u];

}

else if(tag==2){

int v;cin>>v;

tmp-=r[v];

r[v]=0;

}

else if(tag==3){

int u,v;cin>>u>>v;

tmp+=w[u];

r[v]+=w[u];

}

else{

int v;cin>>v;

tmp+=g[v]-r[v];

r[v]=g[v];

}

if(tmp==sum) cout<<"YES";

else cout<<"NO";

cout<

}

}

总结

考察对于基环树的基本认识 .

从只考虑一个点周围更新的思路中跳出来 , 看到问题整体 .

维护可重集 , 想到用哈希 .

总结

哈希常常在字符串 , 哈希表相关的问题中出现 . 但是不要忘记哈希在涉及到集合维护以及判断是否相等时有很强的通用性 , 难的并不是哈希本身 , 而是将题目转化向一个集合维护问题 , 并且想起哈希可以高效地维护这种信息 .

这类问题的另一个共同点是 : 大多需要从整体上考虑问题 . 如果在局部看问题很神秘 ( 即很难分解成更局部的小问题 ) , 不妨从更宏观的视角考虑 .

...