浅谈哈希（包括二维哈希和哈希表）

Otachi · 2026-03-01 17:26:58 · 算法·理论

其实哈希说起来简单，就是把一个东西（包括且不限于序列、矩阵和字符串）映射成一个数字，从而方便地进行存储和比较。

限于本人能力没讲树哈希。

字符串哈希

这个属于是最常用的哈希。

最常用的哈希是多项式哈希。一般的，一个字符串 S 的哈希值用如下方法计算：

(\sum_{i=1}^{|s|}s_i \times b^{n-i}) \bmod m

其中 b 为比 s_i 值域范围大的质数，而 m 为 10^9 左右的大质数。对于字符串哈希，因为按照 ASCII 码存储，所以 b 取 > 128 的数。

不同的哈希方式

单哈希

这是最简单的哈希。它遵循上面的公式进行计算。

自然溢出哈希

这是理论效率最高并且最简短的哈希。它利用了 unsigned long long 的自然溢出性质代替取模。由于是自然溢出，效率比取模要快。其实本质上就是以 2^{64} 为模数的单哈希。

双哈希

这是考场最常用的哈希。它一般来说，是两个单哈希或者一个单哈希+一个自然溢出哈希。这里作者习惯使用后者。

出题人如何卡掉你的哈希

单哈希

根据生日悖论，若你的模数为 m，那么只需要 \sqrt{m} 个字符串，就会大概率碰撞。解决方法有两个：
1. 抛弃单哈希，使用双哈希。
2. 使用大模数让出题人不可能构造 sqrt{m} 个字符串。
如果模数不是一个质数，哈希的安全性将会大幅下降，非常容易被卡。
出题人一般会对常见的底数/模数（如 131、10^9+7 等）进行针对性打击。因此下面推荐几个底数和模数：
- 底数：131（最常见）、137、13331、1145141（没想到吧，其实它也是个质数）。
- 模数：10^9+7（最常见）、10^9+9、10^9+123、2^{61}-1（梅森素数，记得要开 __int128）。

自然溢出哈希

因为自然溢出哈希本质上就是模数为 2^{64} 的哈希，而对于模数为形如 2^k 的哈希，出题人会构造 Thue-Morse 序列进行降维打击。因此单独使用自然溢出哈希安全性极低。

双哈希

出题人可能会通过猜你使用的底数/模数进行针对性打击。但是如果出题人没法猜到你的底数/模数且出题人还把你的哈希卡掉了，请出题人出门左转至图灵奖官网。

如何不让出题人卡掉你的哈希

使用双哈希以及不常见的底数/模数。

滚动哈希

滚动哈希可以快速的计算子串的哈希值。一个子串 [l,r] 的哈希值可以用如下方法计算：

[\sum_{i=1}^{r} s_i \times b^{r-i}-b^{r-l+1}(\sum_{i=1}^{l-1} s_i \times b^{l-i-1})] \bmod m

可以通过预处理 s_i 的前缀和和 b 的幂做到 O(1) 计算。

字符串匹配

要啥 KMP 啊，直接 O(n) 匹配即可。

最长回文子串

预处理 s 和其反转串 t 的哈希值，分奇数和偶数两种情况。二分答案二分两边的长度，check 中枚举回文中心即可。时间复杂度 O(n\log n)。

LCP

预处理前缀哈希。然后二分一个 i 使得 hs_i=ht_i 且 hs_{i+1} \neq ht_{i+1} 即可。时间复杂度 O(\log n)。

例题

U461211 字符串 Hash（数据加强）

这题较原版数据较强，可以用于测试字符串哈希。

:::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ull> plu;
const ll BASE1=131,MOD1=19260817;
const ull BASE2=13331;
const int N=1e6+5;
int n;
plu a[N];
plu get_hash(string s)
{
    ll h1=0;
    ull h2=0;
    for(char c:s)
    {
        h1=(h1*BASE1+c)%MOD1;
        h2=h2*BASE2+c;
    }
    return {h1,h2};
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        string s;
        cin>>s;
        a[i]=get_hash(s);
    }
    sort(a+1,a+n+1);
    int ans=unique(a+1,a+n+1)-(a+1);
    cout<<ans<<endl;
    return 0;
}

:::

#103. 子串查找

字符串匹配即可。

:::success[AC Code]

include<bits/stdc++.h>

using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<ll,ull> plu; const ll BASE1=131,MOD1=1e9+123; const ull BASE2=13331; const int N=1e6+5; int n,m; plu h1[N],pw1[N]; plu h2; string s1,s2; void into_hash() { pw1[0]={1,1}; for(int i=1;i<=n;i++) { h1[i]={(h1[i-1].firstBASE1%MOD1+s1[i])%MOD1,h1[i-1].secondBASE2+s1[i]}; pw1[i]={pw1[i-1].firstBASE1%MOD1,pw1[i-1].secondBASE2}; } for(int i=1;i<=m;i++)h2={(h2.firstBASE1%MOD1+s2[i])%MOD1,h2.secondBASE2+s2[i]}; } plu get_hash1(int l,int r) { return {(h1[r].first-h1[l-1].firstpw1[r-l+1].first%MOD1+MOD1)%MOD1,h1[r].second-h1[l-1].secondpw1[r-l+1].second}; } int main() { cin>>s1>>s2; n=s1.size(),m=s2.size(); s1=' '+s1,s2=' '+s2; into_hash(); int ans=0; for(int i=1;i+m-1<=n;i++) if(get_hash1(i,i+m-1)==h2) ans++; printf("%d\n",ans); return 0; } :::

P3805 【模板】Manacher

用上文所述的方法求可以拿到 54pts，但是理论上是能 AC 的。有无卡常好手给点建议。

:::warning[54pts Code]

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull BASE=13331;
const int N=1.1e7+5;
int n;
ull h1[N],h2[N],pw[N];
string s,t;
void into_hash()
{
    for(int i=1;i<=n;i++)h1[i]=h1[i-1]*BASE+s[i];
    for(int i=1;i<=n;i++)h2[i]=h2[i-1]*BASE+t[i];
    pw[0]=1;
    for(int i=1;i<=n;i++)pw[i]=pw[i-1]*BASE;
}
ull get_hash1(int l,int r)
{
    return h1[r]-h1[l-1]*pw[r-l+1];
}
ull get_hash2(int l,int r)
{
    return h2[r]-h2[l-1]*pw[r-l+1];
}
bool check1(int mid)
{
    for(int i=mid+1;i+mid-1<=n;i++)
    {
        int l=i-mid,r=i+mid;
        int tl=n-r+1,tr=n-l+1;
        if(get_hash1(l,r)==get_hash2(tl,tr))return true;
    }
    return false;
}
bool check2(int mid)
{
    for(int i=mid;i+mid<=n;i++)
    {
        int l=i-mid+1,r=i+mid;
        int tl=n-r+1,tr=n-l+1;
        if(get_hash1(l,r)==get_hash2(tl,tr))return true;
    }
    return false;
}
int main() 
{
    cin>>s;
    n=s.size();
    t=s;
    s=' '+s;
    reverse(t.begin(),t.end());
    t=' '+t;
    into_hash();
    int l=0,r=(n-1>>1),mid;
    int ans=0;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check1(mid))
        {
            ans=max(ans,(mid<<1)+1);
            l=mid+1;
        }
        else    r=mid-1;
    }
    l=1,r=(n>>1),mid;
    while(l<=r)
    {
        mid=l+r>>1;
        if(check2(mid))
        {
            ans=max(ans,(mid<<1));
            l=mid+1;
        }
        else    r=mid-1;
    }
    cout<<ans<<endl;
    return 0;
}

:::

二维哈希

:::info{open}

这个知识点考的很少，可以仅作为了解。

:::

相当于从一维的序列（字符串）扩展到了二维的矩阵。

二维哈希类似二维 ST 表和二维前缀和，有两种实现方法：一种是更为“正宗”的，即左+上-左上+自己=自己最终的方法，一种是先把行算出来，然后再合并列。

这里用第一种方法算子矩阵，第二种方法算整个矩阵。

考虑二位前缀和不难想到：

h_{i,j}=h_{i-1,j} \times b2+h_{i,j-1} \times b1-h_{i-1,j-1} \times b1 \times b2+a_{i,j}

其中 b1 为行的模数，b2 是列的模数。

同样可以得到 (x1,y1) 到 (x2,y2) 的哈希值为：

h_{x2,y2}-h_{x1-1,y2} \times b2^{x2-x1+1}-h_{x2,y1-1} \times b1^{y2-y1+1}+h_{x1-1,y1-1} \times b1^{y2-y1+1} \times b2^{x2-x1+1}

156. 矩阵

考虑把所有的 a \times b 矩阵的哈希值存起来，然后看所求值是否存在。注意这道题 map 会 MLE！因此考虑把哈希值存到一个 vector 里面然后排序，然后二分一下询问矩阵的哈希值是否存在。

:::success[AC Code]

#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
const ull BASE1=131,BASE2=137;
const int N=1005;
int n,m,a,b,q;
char mp[N][N],tmp[N][N];
vector<ull>hs;
ull h[N][N],pw1[N],pw2[N];
void into_hash()
{
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            h[i][j]=h[i-1][j]*BASE2+h[i][j-1]*BASE1-h[i-1][j-1]*BASE1*BASE2+mp[i][j];
    pw1[0]=pw2[0]=1;
    for(int i=1;i<=m;i++)pw1[i]=pw1[i-1]*BASE1;
    for(int i=1;i<=n;i++)pw2[i]=pw2[i-1]*BASE2;
}
ull get_hash(ull h[][N],int x1,int y1,int x2,int y2)
{
    return h[x2][y2]-h[x1-1][y2]*pw2[x2-x1+1]-h[x2][y1-1]*pw1[y2-y1+1]+h[x1-1][y1-1]*pw1[y2-y1+1]*pw2[x2-x1+1];
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&a,&b);
    for(int i=1;i<=n;i++)
        scanf("%s",mp[i]+1);
    into_hash();
    for(int i=1;i+a-1<=n;i++)
        for(int j=1;j+b-1<=m;j++)
            hs.push_back(get_hash(h,i,j,i+a-1,j+b-1));
    sort(hs.begin(),hs.end());
    scanf("%d",&q);
    while(q--)
    {
        for(int i=1;i<=a;i++)
            scanf("%s",tmp[i]+1);
        ull nhs=0;
        for(int i=1;i<=a;i++)
        {
            ull rhs=0;
            for(int j=1;j<=b;j++)
                rhs=rhs*BASE1+tmp[i][j];
            nhs=nhs*BASE2+rhs;
        }
        puts(binary_search(hs.begin(),hs.end(),nhs)?"1":"0");
    }
    return 0;
}

:::

哈希表

哈希表说人话就是通过哈希函数映射。但是不同于前两个，它是为了存储，而不是比较。

探测法

探测法的原理可以这样解释：

你去上厕所。根据哈希函数找到的坑位被占了，你选择找下一个没有人的坑位。

“找下一个”的过程可以用暴力模拟。

pb_ds 中的 gp_hash_table 就是用它实现的。

拉链法

拉链法的原理可以这样解释：

你去上厕所。根据哈希函数找到的坑位被占了，你选择站在后面排队。

“站在后面排队”的过程可以用链表模拟。

pb_ds 中的 cc_hash_table 和 unordered_map 就是用它实现的。

探测法 vs 拉链法

gp_hash_table 因为是探测法，能更好的利用 Catch hit，因此常数较小。但是它一旦装载因子（Load Factor）超过 0.7，探测法的冲突就会剧增，性能断崖式下跌。所以 gp_hash_table 必须预留大量空位，这叫“以空间换时间”。cc_hash_table（拉链法）即使装载因子达到 1.0 甚至更高，也只是链表变长了一点，依然能跑。在同样的内存限制下，cc 可以把数据塞得更满，而不需要像 gp 那样提前扩容出一个巨大的空数组。

如何不让自己的哈希表被卡

因为三个哈希表用的都是恒等转化，所以可以通过增加随机扰动避免冲突：

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;

struct custom_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);
    }
};

// 安全且飞快的哈希表
gp_hash_table<long long, int, custom_hash> safe_table;