哈希

哈希表

哈希表又称散列表，其主要思想是将字符串映射成一个 int 或是其他数据类型的数据，从而在比较的时候可以实现 O(1) 的复杂度。

通常我们采用的是多项式Hash的方法，其具体实现公式一般为：

[f(s) = sum s[i]*b^i (mod M) ]

由上式可知，哈希其实是有非常微小的概率出错的，所以我们要选取合适的b和M；其实现一般有两种方法：用unsigned long long自然取模 或是找一个足够大的质数取模。

下面为hash模板（其用于统计不同字符串的个数，注意 base 和 mod 的取值）：

#include<bits/stdc++.h>

using namespace std;
const int maxn=2e6+10;
char s[maxn];
int arr[maxn],base=131;
const int mod=1e9+7;
int fhash(char *s)
{
    long long res=0;
    int len=strlen(s);
    for(int i=0;i<len;++i)
        res=(res*base+s[i])%mod;
    return res;
}

int main()
{
    ios::sync_with_stdio(false);

    int n;
    cin>>n;
    for(int i=0;i<n;++i)
    {
        cin>>s;
        arr[i]=fhash(s);
    }
    sort(arr,arr+n);
    int ans=1;
    for(int i=1;i<n;++i)
        if(arr[i]!=arr[i-1])    ans++;
    cout<<ans<<endl;

    system("pause");
    return 0;
}