博客

首先设一个进制数base，并设一个模数mod，而哈希其实就是把一个数转化为一个值，这个值是base进制的，储存在哈希表中，注意一下在存入的时候取模一下即可。

比如说现在有一个字符串orzc，枚举这个字符串的每一位，与base相乘得到ans，然后mod一下，就得到orzc的哈希值，但是哈希有一个很大的弊端：哈希冲突。

什么是哈希冲突呢？

就比如说orzc的哈希值是233，而orzhjw的哈希值也是233。

那么我们在查询的时候代码会认为这两个字符串是相同的，但显然这两个字符串是不同的。

减少哈希冲突的方法很多，自然溢出法，双哈希之类的。

单hash/自然溢出法

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
#define inf 1<<30
#define mt(x,y) memset(x,y,sizeof(x))
#define il inline 
#define ull unsigned long long
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il ll swap(ll x,ll y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
#define N 10001
#define base 233
ull mod=212370440130137957ll;
ll f[N],n;
char a[N];
//ull hash(char s[]){ ll ans=0,len=strlen(s); for(ll i=0;i<len;i++){ ans=((base*ans+(ull)s[i])+mod)%mod; } return ans; }
//这个是单hash+大质数mod，也是可以过的，但是会比较慢

ull hash(char s[]){//自然溢出
    ull ans=0,len=strlen(s);
    for(ll i=0;i<len;i++){
        ans=base*ans+(ull)s[i];
        //这里不使用mod让它自然溢出，定义为ull的数在超过2^32的时候会自然溢出
        //如果把这个换成上面的hash就会400ms+
        //所以说自然溢出大法好
    }
    return ans;
}
int main(){
    read(n);
    for(ll i=1;i<=n;i++){
        scanf("%s",a);
        f[i]=hash(a);
    }
    sort(f+1,f+n+1);ll ans=1;
    for(ll i=1;i<n;i++){
        if(f[i]!=f[i+1])ans++;
    }
    printf("%d\n",ans);
    return 0;
}

自然溢出法

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ll int
#define inf 1<<30
#define mt(x,y) memset(x,y,sizeof(x))
#define il inline 
#define ull unsigned long long
il ll max(ll x,ll y){return x>y?x:y;}
il ll min(ll x,ll y){return x<y?x:y;}
il ll abs(ll x){return x>0?x:-x;}
il ll swap(ll x,ll y){ll t=x;x=y;y=t;}
il void read(ll &x){
    x=0;ll f=1;char c=getchar();
    while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
using namespace std;
#define N 10001
#define base 233
ull mod1=212370440130137957ll;
ull mod2=inf;
ll n;
char a[N];
struct node{ll x,y;}f[N];
il ull hash1(char s[]){
    ll ans=0,len=strlen(s);
    for(ll i=0;i<len;i++){
        ans=(base*ans+(ull)s[i])%mod1;
    }
    return ans;
}
il ull hash2(char s[]){
    ll ans=0,len=strlen(s);
    for(ll i=0;i<len;i++){
        ans=(base*ans+(ull)s[i])%mod2;
    }
    return ans;
}
il bool cmp1(node a,node b){return a.x<b.x;}
il bool cmp2(node a,node b){return a.y<b.y;}
int main(){
    read(n);
    for(ll i=1;i<=n;i++){
        scanf("%s",a);
        f[i].x=hash1(a);
        f[i].y=hash2(a);
    }
    sort(f+1,f+n+1,cmp1);sort(f+1,f+n+1,cmp2);
    ll ans=1;
    for(ll i=1;i<n;i++){
        if(f[i].x!=f[i+1].x||f[i].y!=f[i+1].y)ans++;
    }
    printf("%d\n",ans);
    return 0;
}