What the Hash of String is?

· · 个人记录

核心思想

就是一个单向加密系统

字符串Hash其实有点类似于银行的2048位加密系统，唯一的区别应该是字符串Hash是单向加密。

具体思路

定义一个实数集f，

对于已知的每一个存在于字符集S的字符串S_i，

都有一个g(S_i)=f。

一般来说，我们定义\delta为S里出现的全部字符，那么可以以\delta为1~n的进制进行g(s)的编写

(感觉我好像说的有点模糊)

举个栗子：

有下列字符串：

a ab abc abcd abcde

那么字符集S就是上面那5个字符串，\delta=\{a,b,c,d,e\}

所以你可以写一个5进制转10进制的简单程序来充当g(s)

值得注意的是，由于g(s)的不同，不一定能够保证以下等式一定成立

对于\forall S_i,S_j \in S (i \neq j)

g(S_i) \neq g(S_j)

For Example

定义g(s)=\sum_1^{s.length()}{(int)s_i}

那么根据这个方程得出来的ab和ba两个字符串的f是一样的，但是显而易见的是这两个字符串是不一样的。

So，字符串Hash其实是有一定的错误率的

所以，选择一个相对较好的进制数base可以尽可能让你的错误率趋近于0

绝大多数情况下，不要选择一个10^9 级别的数，因为这样随机数据都会有Hash冲突，根据生日悖论，随便找上\sqrt{10^9} 个串就有大概率出现至少一对Hash 值相等的串（参见BZOJ 3098 Hash Killer II）。

最稳妥的办法是选择两个10^9 级别的质数，只有模这两个数都相等才判断相等，但常数略大，代码相对难写，目前暂时没有办法卡掉这种写法（除了卡时间让它超时）（参见BZOJ 3099 Hash Killer III）。

如果能背过或在考场上找出一个10^{18}级别的质数(Miller-Rabin)，也相对靠谱，主要用于前一种担心会超时，后一种担心被卡。

偷懒的写法就是直接使用unsigned long long，不手动进行取模，它溢出时会自动对2^{64}进行取模，如果出题人比较良心，这种做法也不会被卡，但这个是完全可以卡的，卡的方法参见(BZOJ 3097 Hash Killer I)。

最后放个代码纪念一下字符串专题的开始（我最最最起码还有KMP没学）

#include<bits/stdc++.h>
using namespace std;
int n,ans,base=19260817;
unsigned long long f[10001];
string s;
void Hash(string a,int p){
    for(int i=0;i<a.length();i++) f[p]=f[p]*base+int(s[i]);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>s;
        Hash(s,i);
    }
    sort(f+1,f+n+1);
    for(int i=0;i<n;i++)
        if(f[i]!=f[i+1]) ans++;
    cout<<ans<<endl;
}