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語言寫一個散列表的文章就介紹到這瞭,更多相關C語言寫散列表內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！