如何用C語言寫一個散列表

本篇文章為大家展示了如何用C語言寫一個散列表，內容簡明扼要并且容易理解，絕對能使你眼前一亮，通過這篇文章的詳細介紹希望你能有所收獲。

一、快速理解散列表

散列表，就是下標可以為字母的數組。

假設現有一個數組int a[100]，想查找其中第40個元素，則直接輸入a[40]就可以了，時間復雜度為O ( 1 ) O(1)O(1)。

問題在于，當下標不是數字，而是一個字符串的時候，可能需要一個超大的空間才能將所有下標妥善地存放在特定的位置。例如，若以大小寫字母作為下標索引，那么一位就需要預留52個空間，10位就需要52的10次方 這么大的空間，根本沒有設備可以滿足。

好在，52的10次方這么龐大的數字也超出了正常人的使用范圍，無論多長的索引，我們能用上的值也絕對是有限的。

例如，現有下面三個字符串作為下標

key1 = "microcold";
key2 = "tinycold";
key3 = "microcool";

其實只需要選取頭、尾兩個字母，就能很好地區分這三個字符串，即

def hash(key):
    return key[0]+key[-1]

但這種算法對索引字符的要求非常高，至少頭尾不能重復。所以，現在需要能把超長字符串映射成特定短字符串而且盡量避免重復的算法。

二、散列函數

最簡單的散列函數就是求余，將輸入字符串按位轉為整數之后求余。由于在字符串可能會轉成非常大的整數，故需了解余數的性質

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

相應地有：

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

用C語言實現如下：

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

測試如下：

>gcc hash.c
>a.exe
asdf
21
microcold
81
tinycold
12
microcool
5
minicool
81
minicold
73

三、防撞

盡管minicool和microcold撞車了，但通過100以內的位數，去表示52的9次方 的樣本，也算是不錯的表現了。

為了不發生撞車，則需更改數組中的元素類型——至少得是個結構體。而防止撞車的方法很簡單，如果發生撞車，那我就不散列了，直接發配到一個指定的數組中。

#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];     //存儲撞擊之后的值
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);  //此時新增一個節點
    }
    else {
        if(crashTable[index]->next==-1)
            crashTable[index]->next = numCrash;
        insertCrash(str, hashTable[index]->next, n);
    }
}

//n為字符串長度
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

可見一方面的確散列了，另一方面也的確防撞了。

上述內容就是如何用C語言寫一個散列表，你們學到知識或技能了嗎？如果還想學到更多技能或者豐富自己的知識儲備，歡迎關注億速云行業資訊頻道。