Hash的应用

重新整理了一下Hash表的应用：

首先，常用的整数哈希：

取模法
取乘法

取模顾名思义就是%p为hash值：

1 #define hash(i) (i%p)

取模顾名思义就是*p取一部分（此处用自然溢出）为hash值：

1 #define hash(i) (((unsigned int)i*p)>>p_)

接着，字符串取模：

1 #define hash(i,j) mo(f[j]-f[i-1]*fp[j-i+1],Q)
2 for (int i=1;i<=n;i++) f[i]=mo(f[i-1]*P+a[i],Q);//P为a[i]的种类数。
3 for (int i=1;i<=n;i++) fp[i]=mo(fp[i-1]*P,Q);

最后，厉害的排列hash出现了！！！

我们利用变进制数来把他存下，Ai为Pi右边比他小的数。

 1 int h(int a[]){ 
 2     int k=1,ans=0; 
 3     for (int i=7;i>=0;i--){ 
 4         int num=0; 
 5         for (int j=i+1;j<9;j++) 
 6             if (a[j]<a[i]) num++; 
 7         ans+=num*k;
 8         k*=(9-i); 
 9     } 
10     return ans; 
11 }

最近，我发现hash后放到map里及可以节省时间还能节省空间，不过STL会慢点，map<unsign long long,int>M;

最后放上大神的PPT镇楼：http://files.cnblogs.com/files/SXia/李羽修.ppt