C語(yǔ)言寫(xiě)一個(gè)散列表

更新時(shí)間：2022年01月04日 11:33:23 作者：微小冷

這篇文章主要介紹了C語(yǔ)言寫(xiě)一個(gè)散列表,散列表，就是下標(biāo)可以為字母的數(shù)組。更多內(nèi)容和小編一起學(xué)習(xí)下面內(nèi)容吧

一、快速理解散列表

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

假設(shè)現(xiàn)有一個(gè)數(shù)組int a[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è)字符串，即

def hash(key):
? ? return key[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)如下：

#include <stdio.h>
#define MAXHASH 100

//快速取冪法，a*b^n%c
int ?PowerMod (int a, int b, int n, int c)?
{ ?
? ? int ?ans = 1;?
? ? b = b % c;?
? ? while (n > 0) { ?
? ? ? ? if(n % 2 == 1)?
? ? ? ? ? ? ans = (ans * b) % c;?
? ? ? ? n = n / 2; ? ? ? //b >>= 1;
? ? ? ? b = (b * b) % c;?
? ? }?
? ? return (a*ans)%c;?
}?

int hash(char* key, int n){
? ? int addr = 0;
? ? for(int i = 0; i < n; i++){
? ? ? ? addr += PowerMod(key[i], 128, i, MAXHASH);
? ? }
? ? return addr%MAXHASH;
}

int main(){
? ? char* str;
? ? int i;
? ? while(1){
? ? ? ? gets(str);
? ? ? ? i = 0;
? ? ? ? while(str[i++]!='\0'){}
? ? ? ? printf("%d\n",hash(str,i));
? ? }
? ? return 0;
}

測(cè)試如下：

>gcc hash.c
>a.exe
asdf
21
microcold
81
tinycold
12
microcool
5
minicool
81
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ù)組中。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAXHASH 100
typedef struct HASHNODE{
? ? char *key;
? ? int next;
} *hashNode;

struct HASHNODE* hashTable[MAXHASH];
struct HASHNODE* crashTable[MAXHASH]; ? ? //存儲(chǔ)撞擊之后的值
int numCrash=0; ? ? ? ? ? ? ? ? ? //已有的撞擊值

void initTable(){
? ? for(int i=0; i < MAXHASH; i++){
? ? ? ? hashTable[i] = (hashNode)malloc(sizeof(struct HASHNODE));
? ? ? ? hashTable[i]->key = NULL;
? ? ? ? hashTable[i]->next = -1;
? ? ? ? crashTable[i] = (hashNode)malloc(sizeof(struct HASHNODE));
? ? ? ? crashTable[i]->key = NULL;
? ? ? ? hashTable[i]->next = -1;
? ? }
}

void insertCrash(char* str, int index, int n){
? ? 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)度
void insertHash(char* str, int index,int n){
? ? 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);
? ? }
}

void printHash(){
? ? for(int i = 0; i < MAXHASH; 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 (int a, int b, int n, int c)?
{ ?
? ? int ?ans = 1;?
? ? b = b % c;?
? ? while (n > 0) { ?
? ? ? ? if(n % 2 == 1)?
? ? ? ? ? ? ans = (ans * b) % c;?
? ? ? ? n = n / 2; ? ? ? //b >>= 1;
? ? ? ? b = (b * b) % c;?
? ? }?
? ? return (a*ans)%c;?
}?

int hash(char* key, int n){
? ? int addr = 0;
? ? for(int i = 0; i < n; i++){
? ? ? ? addr += PowerMod(key[i], 128, i, MAXHASH);
? ? }
? ? return addr%MAXHASH;
}

int main(){
? ? initTable();
? ? char* str;
? ? int i;
? ? 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();
? ? return 0;
}

最后得到：

>gcc hash.c
>a.exe
asdf
21
hellworld
84
microcold
81
minicool
81
tinycool
20
tinycold
12
weixiaoleng
11
exit
crashTable[0]:minicool
hashTable[11]:weixiaoleng
hashTable[12]:tinycold
hashTable[20]:tinycool
hashTable[21]:asdf
hashTable[81]:microcold
hashTable[84]:hellworld

可見(jiàn)一方面的確散列了，另一方面也的確防撞了。

到此這篇關(guān)于C語(yǔ)言寫(xiě)一個(gè)散列表的文章就介紹到這了,更多相關(guān)C語(yǔ)言寫(xiě)散列表內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

您可能感興趣的文章: