零基础字符串哈希：从入门到入门

DX3906_ourstar · 2025-04-07 13:51:07 · 题解

同步发表于博客园。

~~主播曾被这题卡了一下午，所以讲解一种最适合人类宝宝理解的哈希。~~

引入

考虑以下问题。

DX 给了你一个字符串 aadead，请你用自己的方式，将其表示为十进制数。

聪明的你很快想到，将原串拆分成六个字母，得到a，a，d，e，a，d。

然后考虑将每个字母分别转成十进制数。你选择最直观的方式——采用字母表中每个字母的编号，于是你得到了 1,1,4,5,1,4 这六个数字。

接下来，你把六个数字写到一起，得到了 114514，解决了问题。

从哈希的角度来看，你所做的操作，实际上就是求出了字符串 aadead 的 哈希值。

这中间有一些细节，我们接下来展开探讨。

基本概念

哈希值

通俗来讲，就是将一个字符串映射成整数后，得到的值。我们将其记为 \text{hashh}。

一般地，我们认为”两字符串相等”与“两字符串哈希值相等”互为充要条件。这就提供了一个机会，使得我们可以在预处理后以 O(1) 的复杂度判断两串是否相等。

这一结论的主要应用在于代替传统的字符串比较方式，即一位一位地判断。容易发现，后者的复杂度是线性的。

基数

我们回到你得到的六个数字：1,1,4,5,1,4。

你是如何从它们得到 114514 的呢？很简单，将已得到的值（初始为 0）乘以 10，再加上下一个数。

用文字可能不太直观，我们写成代码来看。

inline int calc(){
    int sum=0;
    int a[]={1,1,4,5,1,4};
    for(int i=0;i<6;++i)sum=sum*10+a[i];
    return sum;
}

相信你能够完全理解这一步骤了。但是，我们思考一个问题：为什么统计下一个数的贡献时，我们会将已有结果乘以 10，而不是别的数呢？

答案是显然的——我们要得到的是十进制数。

这就引出了哈希中的一个重要概念——基数。通俗来讲，它决定了你得到的哈希值的进制。我们记它为 \text{base}。

认识到这一点，我们就可以给 \text{base} 随意取值，以计算任意进制下字符串的哈希值。

容易发现，我们已经有了一个通用的公式。具体地，我们记 s 为任意字符串，n 为 s 的长度。于是有：

\text{hashh}=\sum\limits^n_{i=1}s_i\cdot\text{base}^{n-i}

其中 \forall s_i 在转为整数后参与运算。有了上面的解释，这个式子很好理解了。把它写成代码，就类似于这样：

inline int get(string s,int base){//给定以 1 为起始位置的长度为 n 的字符串，返回它在 base 进制下的哈希值。 
    int hashh=0;
    for(int i=1;i<=n;++i)hashh=hashh*base+(int)s[i]; 
    return hashh;
}

模数

注意到上面的代码有一个缺陷：我们得到的哈希值可能很大，可能炸 int，甚至达到任何一种数据类型都无法存储的地步。因此，我们需要指定一个模数，随时将得到的哈希值对它取模。我们记模数为 \text{p}，那么我们计算哈希值的公式就变成了：

\text{hashh}=(\sum\limits^n_{i=1}s_i\cdot\text{base}^{n-i})\bmod \text{p}

容易发现，必然有 \text{hashh} \in[0,\text{p})，也就是说，上面的式子只能生成 \text{p} 种不同的哈希值。这时候，可能出现 哈希冲突，也就是两个不同字符串的哈希值相同。~~这就是哈希身上玄学色彩的来源。~~

举个例子，现在 A 串的哈希值原本为 201，B 串的哈希值原本为 101。对 100 取模后，两串的哈希值都变成了 1，这就是哈希冲突。

为避免哈希冲突，我们显然希望 \text{p} 有以下特征：

大，这样区间更大，能生成的不同哈希值更多；
\text{p} \in \mathbb{P}，这样 \text{p} 的因子最少，取模后结果相等的可能性最小。

所以，我们一般选取 998244353,19491001,1145141 这样的数作为模数。

但是，我们可以偷个懒——用 ull 存储哈希值，不进行取模。这种写法被称为 自然溢出。

一来，ull 的存储范围很大，一定程度上可以提高正确率；另一方面，它溢出后直接从 0 重新开始，相当于我们将 \text{p} 设成了 ull 的上界。

~~题外话：敢在 CF 上写自然溢出的都是勇士。~~

容易发现，自然溢出的优点在于简单好写，但缺点在于容易被卡。~~其实不影响它能够通过此题。~~

另外，还有一种写法——双模数，可以看我的这篇题解进行了解。它正与自然溢出相反——难写，但正确率高。

代码实现

现在你已经对字符串哈希有了基本的了解，于是我们回到本题。

思路是显然的——计算每个串的哈希值，最后观察不同的哈希值的个数。

我们把重点放在后半部分。容易发现，对于一个有序的数列，相等的数必然相邻。于是我们考虑将哈希值存在一个单调递增（减）的数组中，再从前往后扫一遍；若当前位与前一位不同，则计入答案；否则，直接忽略。

于是代码就显然了。

#include<iostream>
#include<string>
#include<algorithm>
#define ull unsigned long long
#define p 212370440130137957ll//模数
#define base 191//基数
using namespace std;

const int N=1e7+5;

int n,ans=1;
ull a[N];//存储哈希值

namespace OIfast{

    inline int read(){//快读快写
        int n=0,f=1;
        char c=getchar();
        while(c<'0'||c>'9'){
            if(c=='-')f=-1;
            c=getchar();
        }
        while(c>='0'&&c<='9')n=(n*10+c-'0')%p,c=getchar();
        return n*f;
    }

    inline void print(int n){
        if(n<0)putchar('-'),n=-n;
        if(n>=10)print(n/10);
        putchar(n%10+'0');
        return ;
    }

    inline void write(int n,char c){
        print(n),putchar(c);
        return ;
    }

}using namespace OIfast;

inline ull hashh(string s){//计算给定字符串的哈希值。
    int l=s.size();
    ull x=0;
    for(int i=0;i<l;++i){
        x=(x*base+(ull)s[i])%p;
    }
    return x;
}

signed main(){
    n=read();
    for(int i=1;i<=n;++i){
        string s;
        cin>>s;
        a[i]=hashh(s);
    }
    sort(a+1,a+n+1);//排序，递增递减都可。
    for(int i=2;i<=n;++i)if(a[i]!=a[i-1])++ans;//如上。
    write(ans,'\n');
    return 0;
}

这个代码实现是主播不太喜欢的，因为它需要使用 cin 来读入字符串。主播不喜欢 cin，主播要用 getchar()。~~scanf() 是什么，能吃吗。~~

注意到我们使用代码（不是公式）计算哈希值时，每一轮计算都只与某一个字符有关，而与字符串长度无关。我们完全可以在输入的同时处理出哈希值，但却在 hashh() 函数中获取了字符串的长度用以遍历字符串。

所以，使用 getchar() 一个一个地读入字符并计入贡献，直到读取到非法字符（此时当前字符串输入完毕）。

我们再加上自然溢出，就得到了这份代码：

#include<iostream>
#include<string>
#include<algorithm>
#define ull unsigned long long
#define base 191
using namespace std;

const int N=1e7+5;

namespace OIfast{

    inline ull read(){
        ull n=0;
        char c=getchar();
        while(c<'0'||c>'9')c=getchar();
        while(c>='0'&&c<='9'){
            n=(n<<3)+(n<<1)+(c^48);
            c=getchar();
        }
        return n;
    }

    inline void print(ull n){
        if(n>=10)print(n/10);
        putchar(n%10^48);
        return ;
    }

    inline void write(ull n,char c){
        print(n),putchar(c);
        return ;
    }

}using namespace OIfast;

int n,ans=1;
ull a[N];

signed main(){
    n=read();
    for(int i=1;i<=n;++i){
        ull hashh=0;
        char c=getchar();
        while(!isdigit(c)&&!isalpha(c))c=getchar();//跳过乱七八糟的东西。
        while(isdigit(c)||isalpha(c)){//计算当前字符串的哈希值。循环结束就标志着当前字符串输入结束。
            hashh=hashh*base+(ull)c;
            c=getchar();
        }
        a[i]=hashh;
    }
    sort(a+1,a+n+1);
    for(int i=2;i<=n;++i)if(a[i]!=a[i-1])++ans;
    write(ans,'\n');
    return 0;
}