哈希

ACM

如何辨别哈希题?大概就通过一句话:

当需要用 $O(1)$ 的时间快速比较两个 $O(n)$ 的东西时.

哈希提供一种映射关系,能够把字符串或者树通过某种加密关系换算成一个数,从而进行比较或者直接排序.

自然,撞哈希的概率几乎是哈希算法的核心.

生日悖论

大概意思就是,任意约 $\sqrt n$ 个元素的时候元素相同的概率就会很高(n是值域).为了防止撞哈希,我们要让值域尽可能大(也就是选择1e16-1e18级别的质数).

二维哈希

矩阵哈希,要求 $O(1)$ 求出相同大小的子矩阵的哈希值.

我们要从矩阵中提取一个大小为(y,x)的矩阵,咋办?
首先要预处理阶乘(处理到矩阵行列最大值就可以了).二位哈希采取双进制的操作,一个是行之间的进制位(1299709),另一个是列之间乘再加的进制位(1e9+7).

然后要建立哈希表.由于二维哈希是前缀式的,所以要乘上一位再加这一位的数据.然后再前缀和一样的乘,每一位乘列的进制位.参考代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
p1[0]=p2[0]=1;
for(int i=1;i<=n;i++){
    p1[i]=p1[i-1]*dom;
    p2[i]=p2[i-1]*mod;
}
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        x[i][j]=x[i][j-1]*dom+read();
for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
        y[i][j]=y[i][j-1]*dom+read();
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        x[i][j]+=x[i-1][j]*mod;
        y[i][j]+=y[i-1][j]*mod;
    }
}

公式:

参考代码:

1
2
rp=y[i][j]-y[i-k][j]*p2[k]-y[i][j-k]*p1[k]+y[i-k][j-k]*p2[k]*p1[k];
//p2是1e9+7,p1是小的行之间的质数,k是子矩阵长度

好像子矩阵都可以O(1)求.

字符串哈希

字符串哈希,就是把一段字符串哈希变成一个数(双哈希是变成一对数),然后可以进行排序,然后直接检测有多少哈希值就行了(也就是多少种不同的字符串).

字符串哈希一般都是进制哈希.主要分为三种实现方法:自然溢出法(也就是模 $2^{64}$),单模哈希法(一个很大的质数),双模哈希(返回一对哈希值).

例题

  1. 矩阵哈希:给你两个矩阵,问两个矩阵中最大的重合子矩阵的大小(边长)是多少.

    我们发现边长是单调的,于是考虑二分.设 $k$ 是当前查验的边长.我们把两个矩阵的所有子矩阵直接哈希加到哈希表里面,然后排个序,直接比较(采用umap可以再掉一个log).时间复杂度是 $O(n^2\log^2n)$ .

  2. (小技巧:5倍幂哈希)元素模糊匹配问题:给两个数列ab,b可能是有a打乱得到,也可能不是由a打乱得到,你需要判断(预处理复杂度可以放宽至O(nlogn),但是比较必须O(1))

    首先,我们要使用支持交换律的哈希,比如乘法,加法.直接维护这样的双模会被hack(先不考虑0的情况,直接特判)

    1
    2
    1 9 2 2 2 2 2 2 2 2
    3 3 1 4 1 4 1 4 1 4

    以上数据和积相同.此时我们需要让这些数5倍自己,然后再维护(小技巧)即可.

树哈希

求出一个树的哈希值.考虑一下式子

首先求出所有根节点的哈希值 $f(x)$ ,设g表示以y为 根 的哈希,有 $g(y)=f(y)+h(x)$ 根据定义有

于是

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void dfs(int num,int ko){
    sz[num]=1;
    f[num]=1;
    for(auto i:edge[num]){
        if(i==ko)continue;
        dfs(i,num);
        sz[num]+=sz[i];
        f[num]=(f[num]+f[i]*prime[sz[i]])%mod;
    }
}
void dfs2(int num,int ko,i64 val){
    ff[num]=(f[num]+val*prime[n-sz[num]]%mod)%mod;
    for(auto i:edge[num]){
        if(i==ko)continue;
        dfs2(i,num,((ff[num]-f[i]*prime[sz[i]])%mod+mod)%mod);
    }
}

字典序

0 < 0 < A < a

按照 ASCII 码,数字的值最小,其次是大写字母,然后是小写字母.

比较分为两种情况:长度一样和不一样.
对于长度一样的情况,我们对短的补 0 .(注意是 0 不是0)
然后直接从头开始比较,谁 ASCII 码小字典序就小.

手写哈希表

一般而言有两种方式:拉链法和顺次法.

我们开一段连续空间,然后在空间内提供哈希算法,模上空间大小,大概就是实际的存储位置.
拉链法:每个单点是一个链表,存储的时候如果哈希冲突就链表加一个节点,访问的时候遍历链表.
顺次法:存储的时候如果哈希冲突,直接顺次访问(n+1),(n+2)等元素.