很久没遇到过hash的题了，今天来重新温故一下
@[toc]

序言

你有没有想过，字符串存储一大溜，比较时又麻烦又折腾，我当年oi时就想要是能转化成整数就好了，
诶，字符串hash其实就是把一个字符串转化成整数
你也可以把hash的过程理解成加密，但是不同字符串加密后的“密文”互不相同
说起来容易，我们怎么才能做到不冲突不重复呢？这里就开始讲解hash

常用的几个字符串hash方法：

S=s1s2s3s4......sn
idx(s[i]) = s[i] - 'a'

hash公式（自然溢出）

讲解

unsigned long long hash[N];
hash[i]=hash[i-1]*p + s[ i ] (自动取模)
p为质数(常取31)
unsigned long long的范围会自然一处，相当于自动对2^64^ 取獏

模板

char s[10010];
ull hashs(char s[])
{
    int len=strlen(s);
    ull base=131;
    ull ans=0;
    for (int i=1;i<=len;i++)
        ans=ans*base+(ull)s[i];

    return ans&0x7fffffff;//舍弃符号位
}

首位是符号位，& 0x7fffffff之后符号位固定为0（代表正数），后面保持不变（可以理解成取正）

单hash

讲解

hash [ i ] = ( hash [ i - 1 ] * p + idx ( s [ i ] ) ) % mod
其中p与mod均为质数
对了，p与mod越大，重复的概率越低

模板

char s[10010];
ull mod=101;
ull hashs(char s[])
{
    int len=strlen(s);
    ull base=13;
    ull ans=0;
    for (int i=1;i<=len;i++)
        ans=(ans*base+(ull)s[i])%mod;
    return ans;
}

双hash

讲解

如果单hash你不放心，可以用双hash，更保险
将一个字符串hash两次，生成一个二元组，来代表原字符串，两个都比配才可以（相当于两把锁）
hash1[i]=(hash1[i−1]) ∗ p + idx(s[i]) % mod1

hash2[i]=(hash2[i−1])∗p + idx (s[i]) % mod2

pair< hash1 , hash2 > 表示一个字符串！

代码

char s[100];
ull mod1=13;
ull mod2=17;
ull hash1(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod1;
    return ans;
}
ull hash2(char s[])
{
    int len=strlen(s);
    ull ans=0;
    for (int i=0;i<len;i++)
        ans=(ans*base+(ull)s[i])%mod2;
    return ans;
}

总结

对于一个字符串，我们可以预处理1~L的hash值，这样通过O（1）的方法递推出来