字符串hash,康托展开总结

发布于 2018-12-06  58 次阅读


 

 

字符串hash,康托展开总结

各种字符串hash函数:

ELF HashBKDRHashAPHashDJBHashJSHashRSHashSDBMHashPJWHashELFHash

字符串hash之BKDRhash函数

有研究表明BKDRhash函数冲突率较低,且变成复杂度低,所以可以用来作为常用hash函数

Hash函数 数据1 数据2 数据3 数据4 数据1得分 数据2得分 数据3得分 数据4得分 平均分
BKDRHash 2 0 4774 481 96.55 100 90.95 82.05 92.64
APHash 2 3 4754 493 96.55 88.46 100 51.28 86.28
DJBHash 2 2 4975 474 96.55 92.31 0 100 83.43
JSHash 1 4 4761 506 100 84.62 96.83 17.95 81.94
RSHash 1 0 4861 505 100 100 51.58 20.51 75.96
SDBMHash 3 2 4849 504 93.1 92.31 57.01 23.08 72.41
PJWHash 30 26 4878 513 0 0 43.89 0 21.95
ELFHash 30 26 4878 513 0 0 43.89 0 21.95

 

 

unsigned int bkdr_hash(const char* str)

{            

      unsignedint seed = 31; // 31 131 1313 13131 131313 etc.. 37(最好是质数)

      unsignedint hash = 0;

      while(str) hash = (hash * seed + (str++))%P;//P是一个较大质数

      returnhash;

}

各种证明:

http://www.it165.net/pro/html/201410/24949.html

 

 

 

双hash优化:

在hash表中想要用线性探查的方式处理hash表的冲突,那么每次比对要查找的元素与当前元素是否相等就显得十分麻烦,特别是两个数据是字符串的时候,strcmp超级耗时,此时我们就可以在存储新元素时通过另一hash算法算出两者的hash值,将这两个hash存入结构体,并且排序,用二分查找第一个hash值,并比较第二个hash值,若符合则相同

 

另外本人想到一个貌似还可以的做法,目前都AC了所做的所有Hash题目

做法:用两种截然不同的hash算法,hash1算出取模压缩后的值,而hash2算出BKDRhash算法,其中P(较大质数)为10^9+7,算出字符串完整的hash2值,把hash1当作地址,hash2当作数据:HashTable[hash1]=hash2;

当然有冲突时先比较hash2值是否相同,不相同则继续探查直到所在地址数据为空,hash2相同时就基本可以说明两个字符串是相等的。。。。

康托展开

叙述:有一个数字序列,所有数都是[1,n]的,且任意两者互异,此时我们用一一对应的方式存储这些数据就有n!种可能,康托算法对处理这种序列提供了完美的解决方法。称为康托展开。我们把这个数列看作全排列,数字所对hash值就为全排列的大小(第几大)。

 

公式:hash(key)=a[n](n-1)!+a[n-1](n-2)!+…+a[2](2-1)!+a[1](1-1)!

其中,a[n]所存的值为在第n个数(从小到大的顺序)之前比n小的数的个数

Hash值完全可以通过循环在n次内算出,且数列与hash完全一一对应,可谓完美算法。

 

康托逆展开:

由于康托展开的一一对应性,我们同样可以算出原来的全排列。

n为康托展开式,k为总阶乘

第一位:(n-1)/(k-1)余n’

第二位:n’/(k-2)余n’’

以此类推。。。

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Poj1200

描述

许多人喜欢解决难题。一个这样的难题是在一个给定的文本中找到一个隐藏的素数。这个数字是所给字符串中不同子串的个数。当你很快会发现,你真的需要一台计算机和一个很好的算法来解决这样的难题。

你的任务是编写一个程序,文本中不同字符的数量不超过NC,给出这样的字符串,求长度为n的不同的子串有多少个。

举一个例子,当n = 3,NC = 4,字符串为“daababac”。可以在字符串中到到符合条件的子串为:"daa";"aab"; "aba"; "bab"; "bac"。因此,答案应该是5。

输入:

第一行:两个数:n,nc

第二行:要搜索的字符串;

你可以假设,最后你所搜索出来符合要求的子串个数不大于16000000;

输出

不同子串的个数

样例输入

3 4

daababac

样例输出

5

提示

输入数据巨大,不用cin

数据巨大,seed不宜太大,看了poj题解,有一个很棒的方法,seed就是当前字符在整个字符串出现过的个数,刚好可以做到一一对应

#include
#include
#include
using namespace std;
const int Z1=1000000007;
bool hashtable[Z1+100];
int n,nc,ans=0,asc[300],num,len,sum;
char str[8000000];
int main(){
//   freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&nc);
    scanf("%s",str);
    len=strlen(str);
    for(int i=0;iif(!asc[str[i]])
            asc[str[i]]=++num;
    for(int i=0;i1;i++){
        sum=0;
        for(int j=i;j//该字符的个数作为seed 
        if(!hashtable[sum])
            hashtable[sum]=1,ans++;
    }
    printf("%d",ans);
    
    return 0;
}

POJ2503-Babelfish

描述:

你刚从滑铁卢搬到一个大城市,但是你却不懂他们的语言,还好你有一本词典可以帮助你。

 

输入格式

输入包括高达10万词条,之后是一个空行,然后是长达10万个单词查询。每个字典条目是包含一个英文单词,后面跟一个空格和一个当地语言。没有当地语言在字典中出现超过一次。每行一个词,输入中的每个词至多10小写字母。

输出格式

输出翻译成英语的消息,每行一个单词。没有在字典中的外来词应该被译为“en”。

样例输入

dog ogday

cat atcay

pig igpay

froot ootfray

loops oopslay

atcay

ittenkay

oopslay

样例输出

cat

eh

loops

这里读入就是个问题,我是这样的:先读入s1,在getchar(),如果get到空格就继续读s2

否则就进行翻译步骤

这里我使用的方式是双哈希,将字符串的第一个hash作为地址,第二个hash作为数据,线性探查相应单词就会省时省力

#include
#include
#include
using namespace std;
const int MAX=1000000;
char data[MAX+20][11],s1[11],s2[11];
unsigned int hashtable[MAX+20];
unsigned int Hash1(const char* str){ 
    unsigned int h=0;
    unsigned int seed=31;
    while(*str) h+=(h*seed+(*str++))%MAX;
    return (h%MAX+h+1311)%MAX;
}

unsigned int Hash2(const char* str){
    unsigned int h=0;
    unsigned int seed=131;
    while(*str) h+=(h*seed+(*str++))%(MAX+3);
    return h%MAX;
}


int main(){
//   freopen("in.txt","r",stdin);
    unsigned int h1,h2;
    while(scanf("%s",s1)!=EOF){
        if(getchar()!=' ') break;
        scanf("%s",s2);
        h1=Hash1(s2);
        h2=Hash2(s2);
        while(data[h1][0]!=0){
            if(h2==hashtable[h1]) break;
            h1+=2333;
            if(h1>MAX) h1%=MAX;
        }
        hashtable[h1]=h2;
        strcpy(data[h1],s1);
    }
    do{
        h1=Hash1(s1);
        h2=Hash2(s1);
        while(h2!=hashtable[h1]){
            if(data[h1][0]==0) break;
            h1+=2333;
            if(h1>MAX) h1%=MAX;
        }
        if(data[h1][0]==0) printf("eh\n");
        else printf("%s\n",data[h1]);
    }while(scanf("%s",s1)!=EOF);
    
    
    return 0;
}