每日算法 - 字符串哈希

今天是为算法写博客的第一天,~在此暂且原谅我今天挑选的算法过于简单~

为什么要哈希

因为字符串有时候会很长,如果出现什么特别长的字符串比如说qwqwqwqwq...(在此省略一万字)...qwqwqwq,如果只是为了查找它有没有出现过,为了它开一个十分大的字符串数组不仅浪费查找的时间还浪费空间。so哈希为此而生。

哈希是干嘛的

简而言之,哈希函数是一个压缩函数,通过将一个大的数字通过模一个质数压缩成一个小的数字,来达到能在数组里开的下的,并且可以用long long而不用自己写高精度来检查是否相等的函数。
也就是说,原来的数据范围可能是10^100,但其实里面可能没什么东西,哈希了一次后,数据范围就降到了10^10或更少,这样我们就可以将它用long long甚至int把它储存起来。

但或许你会问,这样的压缩后的数又有什么用呢?
要注意到,虽然我们不能将一个哈希后的数恢复到原来的内容,但同一内容无论何时哈希,得到的结果都是一样的。这样,当我们判断这个数曾经有没有出现过时,我们可以用少的多的空间管理同样多的东西。
1. 数组开的下:一般来说,一个用来判断一个10^100以内一个数是否出现过的bool数组是开不下的,但一个用来判断10^6个哈希数有没有出现的bool数组一般都能开的下。
2. 压缩数据:如果要直接储存一个大数你要自己写相关的高精度,但如果仅用来看看有没有出现而且数据量又很少,你完全可以用哈希。
3. 方便比较:不仅是一串数字,一个字符串,甚至是一张图,你都可以用一定的手段(比如说把它变成一个X进制数然后哈希)把它变成更容易储存和比较的哈希数。

接下来就是一个用哈希解决问题的题目。

P3370 【模板】字符串哈希

洛谷的题面

这题是一道经典的模板题。在处理的时候,我们可以将每一个字符串化成一个N进制数(最后用十进制数表示)后哈希。在比较的时候,我们就可以将哈希值排序,若前后两个字符串哈希值不同,就说明是两个不同的字符串。(这样远比一个个比较字符串字符简单的多)

#include<bits/stdc++.h>
#define base 150
#define mod 2145786907
#define MAXN 20000
//base用于解决字符串进位时的进制问题
//mod是用于哈希的模数
//MAXN表示数据范围
using namespace std;
int ni[MAXN];
int n;
//用于判断哈希值是否出现的函数,事实上在发现可以用排序解决问题时他就没啥用了
inline bool query(int hashed){
    for(int i=1;i<n;i++){
        if(hashed == ni[i]){
            return true;
        }
    }
    return false;
}
//用于生成哈希的函数
inline int hash1(string hs){
    int x=0;
    for(int i=0;i<hs.size();i++){
        x=(x*base+hs[i])%mod;
        //这里是哈希的核心算法,将字符串转化为一个base进制的数
        //注意边乘边模以防止字符串的哈希超过int的数据范围
    }
    return x;
}
int main(){
    string s;int ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        cin>>s;
        //printf("%d\n",i);
        ni[i]=hash1(s);
    }
    sort(ni+1,ni+1+n);
    for(int i=1;i<n;i++){
        if(ni[i]!=ni[i+1]){
            ans++;
        }
    }
    printf("%d",ans+1);
    return 0;
}

哈希带来的一些问题

首先,因为哈希数量有限(毕竟你的模数定在那里),所以如果真的碰上一大堆数据的时候哈希要谨慎
其次,即使数据数量可能没那么多,你也要考虑到生日悖论和卡常。

生日悖论,指如果一个房间里有23个或23个以上的人,那么至少有两个人的生日相同的概率要大于50%。这就意味着在一个典型的标准小学班级(30人)中,存在两人生日相同的可能性更高。对于60或者更多的人,这种概率要大于99%。从引起逻辑矛盾的角度来说生日悖论并不是一种悖论,从这个数学事实与一般直觉相抵触的意义上,它才称得上是一个悖论。大多数人会认为,23人中有2人生日相同的概率应该远远小于50%。

根据生日悖论,即使你的数据并不多,你的哈希也有可能出现重复的情况。用哈希时,重复在所难免。

解决方案1 拉链法

⽤链表或其他数据结构将同⼀hash值的若⼲元素串联,如果遇到某个hash值就去链表上遍历,

解决方案2 开放寻址法

若某元素插⼊的散列地址已有元素占⽤,则使⽤⼀定⽅法(比如说:加上一个质数)寻找下⼀个可⽤地址

解决方案3 多重哈希

没错,你可以哈希好几次,就是把哈希函数以不同的质数多写几遍,比较的时候多次比较都相同后再说它们是一样的!

解决方案4 随机的防卡常/HACK的哈希

有时候,像CF之类的比赛,可能会有人故意看你的质数来卡常。
没错,你准备一个哈希质数表,这样的话每次程序运行随机取一个!

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注