首页 > 代码库 > Hash的应用

Hash的应用

2024-09-17 10:27:48   215人阅读

重新整理了一下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 }

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

Hash的应用


联系
我们