双值Hash

简单介绍

Hash的应用：Hash其实就像一个加密过程，很多加密算法都会用到Hash，像GitHub中生成的token值也是Hash的结果。
Hash冲突：简单来说就是不同的数映射到了同一个值，防止碰撞的最有效方法就是扩大Hash值的取值空间，也就是最好选用一个大质数（具体原因参考生日悖论/生日攻击：生日攻击是一个计算机密码学中的术语）。
数学原型生日问题：一个班需要多少人，能保证有两个人的生日是一样的。鸽笼原理可能会得出366人，但是实际情况远少于366。这意味着Hash碰撞的可能性远比想象的高，实际上有一个近似的公式\(\sqrt{\frac{\pi}{2}N}\)可以算出50%Hash碰撞所需要的计算次数。这个公式告诉我们Hash碰撞所需耗费的计算次数，和取值空间的平方根是一个数量级。

进入正题

双值Hash就是用两个不同的mod值来计算Hash，如果两个Hash值都相等才认为是同一个字符串，Hash冲突概率降低了很多，但是常数大，容易被卡。时间上：自然溢出法<单Hash+大质数<双Hash+大质数。

Hash的几个常用公式：(虽然说本题不需要用到)

Hash递推：

Hash[0]=0;

Hash[i]=(Hash[i-1]*p+s[i]-'a'+1)%mod;

区间Hash值：

Hash[L...R]=(Hash[R]-Hash[L]*p^(R-L+1)+mod)%mod;这里减法可能会溢出

使用Hash的几个需要注意的地方

在复杂度允许的情况下，尽量采用多Hash（不过一般双值Hash就够）
比赛时能不用自然溢出就不要（平时刷题如果用自然溢出被卡可以及时换掉，但是比赛时如果用自然溢出，OI赛制就GG了）
模数用大质数这个不用说了
并且进制数不要选太简单的，比如 233和 13131 这样的，尽量大一点，比如1313131和233333，太小容易被卡。
以及要合理应对各种卡hash方法的最好方法就是自己去卡一遍hash，详情请参考BZOJ hash killer系列。（各位巨佬可以尝试一下hash killer 3啊233333）

例题

题目链接：

给出N个字符串，输出不同字符串的个数。

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

typedef unsigned long long ull;

const ull mod1=212370440130137957ll;

const ull mod2=(1<<30);

const int maxn=10001;

const int base=233333;

char a[maxn];

int n;

struct node{ull x,y;

    bool operator < (const node& a)const{

        return a.x==x?a.y<y:a.x<x;

    }

}f[maxn];

inline ull hash1(char s[]){

    ull ans=0,len=strlen(s);

    for(int i=0;i<len;++i)ans=(ans*base+(ull)s[i])%mod1;

    return ans;

}

inline ull hash2(char s[]){

    ull ans=0,len=strlen(s);

    for(int i=0;i<len;++i)ans=(ans*base+(ull)s[i])%mod2;

    return ans;

}

int main(){

    scanf("%d",&n);

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

        scanf("%s",a);

        f[i].x=hash1(a);

        f[i].y=hash2(a);

        //cout<<f[i].x<<" "<<f[i].y<<endl;

    }

    sort(f+1,f+1+n);

    int ans=0;

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

        if(f[i].x!=f[i+1].x||f[i].y!=f[i+1].y)ans++;//非相同字符串两个Hash值同时相等的概率非常小

    }

    printf("%d\n",ans);

    return 0;

}

巴特西

# 双值Hash

双值Hash

简单介绍

进入正题

使用Hash的几个需要注意的地方

例题

最新文章

热门文章