第C語(yǔ)言寫(xiě)一個(gè)散列表目錄一、快速理解散列表二、散列函數(shù)三、防撞

一、快速理解散列表

散列表，就是下標(biāo)可以為字母的數(shù)組。

假設(shè)現(xiàn)有一個(gè)數(shù)組inta[100]，想查找其中第40個(gè)元素，則直接輸入a[40]就可以了，時(shí)間復(fù)雜度為O(1)O(1)O(1)。

問(wèn)題在于，當(dāng)下標(biāo)不是數(shù)字，而是一個(gè)字符串的時(shí)候，可能需要一個(gè)超大的空間才能將所有下標(biāo)妥善地存放在特定的位置。例如，若以大小寫(xiě)字母作為下標(biāo)索引，那么一位就需要預(yù)留52個(gè)空間，10位就需要52的10次方這么大的空間，根本沒(méi)有設(shè)備可以滿(mǎn)足。

好在，52的10次方這么龐大的數(shù)字也超出了正常人的使用范圍，無(wú)論多長(zhǎng)的索引，我們能用上的值也絕對(duì)是有限的。

例如，現(xiàn)有下面三個(gè)字符串作為下標(biāo)

key1="microcold";

key2="tinycold";

key3="microcool";

其實(shí)只需要選取頭、尾兩個(gè)字母，就能很好地區(qū)分這三個(gè)字符串，即

defhash(key):

returnkey[0]+key[-1]

但這種算法對(duì)索引字符的要求非常高，至少頭尾不能重復(fù)。所以，現(xiàn)在需要能把超長(zhǎng)字符串映射成特定短字符串而且盡量避免重復(fù)的算法。

二、散列函數(shù)

最簡(jiǎn)單的散列函數(shù)就是求余，將輸入字符串按位轉(zhuǎn)為整數(shù)之后求余。由于在字符串可能會(huì)轉(zhuǎn)成非常大的整數(shù)，故需了解余數(shù)的性質(zhì)

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

相應(yīng)地有：

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

用C語(yǔ)言實(shí)現(xiàn)如下：

#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;

}

測(cè)試如下：

gcchash.c

a.exe

microcold

tinycold

microcool

minicool

minicold

73

三、防撞

盡管minicool和microcold撞車(chē)了，但通過(guò)100以?xún)?nèi)的位數(shù)，去表示52的9次方的樣本，也算是不錯(cuò)的表現(xiàn)了。

為了不發(fā)生撞車(chē)，則需更改數(shù)組中的元素類(lèi)型至少得是個(gè)結(jié)構(gòu)體。而防止撞車(chē)的方法很簡(jiǎn)單，如果發(fā)生撞車(chē)，那我就不散列了，直接發(fā)配到一個(gè)指定的數(shù)組中。

#includestdio.h

#includestdlib.h

#includestring.h

#defineMAXHASH100

typedefstructHASHNODE{

char*key;

intnext;

}*hashNode;

structHASHNODE*hashTable[MAXHASH];

structHASHNODE*crashTable[MAXHASH];

//存儲(chǔ)撞擊之后的值

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);

//此時(shí)新增一個(gè)節(jié)點(diǎn)

}

else{

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

crashTable[index]-next=numCrash;

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

}

//n為字符串長(zhǎng)度

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