C语言写一个散列表

第C语言写一个散列表目录一、快速理解散列表二、散列函数三、防撞

一、快速理解散列表

散列表，就是下标可以为字母的数组。

假设现有一个数组inta[100]，想查找其中第40个元素，则直接输入a[40]就可以了，时间复杂度为O(1)O(1)O(1)。

问题在于，当下标不是数字，而是一个字符串的时候，可能需要一个超大的空间才能将所有下标妥善地存放在特定的位置。例如，若以大小写字母作为下标索引，那么一位就需要预留52个空间，10位就需要52的10次方这么大的空间，根本没有设备可以满足。

好在，52的10次方这么庞大的数字也超出了正常人的使用范围，无论多长的索引，我们能用上的值也绝对是有限的。

例如，现有下面三个字符串作为下标

key1="microcold";

key2="tinycold";

key3="microcool";

其实只需要选取头、尾两个字母，就能很好地区分这三个字符串，即

defhash(key):

returnkey[0]+key[-1]

但这种算法对索引字符的要求非常高，至少头尾不能重复。所以，现在需要能把超长字符串映射成特定短字符串而且尽量避免重复的算法。

二、散列函数

最简单的散列函数就是求余，将输入字符串按位转为整数之后求余。由于在字符串可能会转成非常大的整数，故需了解余数的性质

(a+b)%c=(a%c+b%c)%c

相应地有：

(a*b)%c=((a%c)*(b%c))%c

用C语言实现如下：

#includestdio.h

#defineMAXHASH100

//快速取幂法，a*b^n%c

int

PowerMod(inta,intb,intn,intc)

int

ans=1;

b=b%c;

while(n0){

if(n%2==1)

ans=(ans*b)%c;

n=n/2;

//b=1;

b=(b*b)%c;

}

return(a*ans)%c;

inthash(char*key,intn){

intaddr=0;

for(inti=0;ii++){

addr+=PowerMod(key[i],128,i,MAXHASH);

}

returnaddr%MAXHASH;

intmain(){

char*str;

inti;

while(1){

gets(str);

i=0;

while(str[i++]!='\0'){}

printf("%d\n",hash(str,i));

}

return0;

}

测试如下：

gcchash.c

a.exe

microcold

tinycold

microcool

minicool

minicold

73

三、防撞

尽管minicool和microcold撞车了，但通过100以内的位数，去表示52的9次方的样本，也算是不错的表现了。

为了不发生撞车，则需更改数组中的元素类型至少得是个结构体。而防止撞车的方法很简单，如果发生撞车，那我就不散列了，直接发配到一个指定的数组中。

#includestdio.h

#includestdlib.h

#includestring.h

#defineMAXHASH100

typedefstructHASHNODE{

char*key;

intnext;

}*hashNode;

structHASHNODE*hashTable[MAXHASH];

structHASHNODE*crashTable[MAXHASH];

//存储撞击之后的值

intnumCrash=0;

//已有的撞击值

voidinitTable(){

for(inti=0;iMAXHASH;i++){

hashTable[i]=(hashNode)malloc(sizeof(structHASHNODE));

hashTable[i]-key=NULL;

hashTable[i]-next=-1;

crashTable[i]=(hashNode)malloc(sizeof(structHASHNODE));

crashTable[i]-key=NULL;

hashTable[i]-next=-1;

}

voidinsertCrash(char*str,intindex,intn){

if(index==numCrash){

crashTable[numCrash]-key=(char*)malloc(sizeof(char)*n);

strcpy(crashTable[numCrash++]-key,str);

//此时新增一个节点

}

else{

if(crashTable[index]-next==-1)

crashTable[index]-next=numCrash;

insertCrash(str,hashTable[index]-next,n);

}

//n为字符串长度

voidinsertHash(char*str,intindex,intn){

if(hashTable[index]-key==NULL){

hashTable[index]-key=(char*)malloc(sizeof(char)*n);

strcpy(hashTable[index]-key,str);

}else{

if(hashTable[index]-next==-1)

hashTable[index]-next=numCrash;

insertCrash(str,hashTable[index]-next,n);

}

voidprintHash(){

for(inti=0;iMAXHASH;i++){

if(hashTable[i]-key!=NULL)

printf("hashTable[%d]:%s\n",i,hashTable[i]-key);

if(crashTable[i]-key!=NULL)

printf("crashTable[%d]:%s\n",i,crashTable[i]-key);

}

int

PowerMod(inta,intb,intn,intc)

int

ans=1;

b=b%c;

while(n0){

if(n%2==1)

ans=(ans*b)%c;

n=n/2;

//b=1;

b=(b*b)%c;

}

return(a*ans)%c;

inthash(char*key,intn){

intaddr=0;

for(inti=0;ii++){

addr+=PowerMod(key[i],128,i,MAXHASH);

}

returnaddr%MAXHASH;

intmain(){

initTable();

char*str;

inti;

while(1){

gets(str);

if(strcmp(str,"exit")==0)break;

i=0;

while(str[i++]!='\0'){}

insertHash(str,hash(str,i),i);

printf("%d\n",hash(str,i));

}

printHash();

return0;

}

最后得到：

gcchash.c

a.exe

hellworld

microcold

minicool

tinycool

ti