本篇文章为大家展示了如何用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语言写一个散列表,你们学到知识或技能了吗?如果还想学到更多技能或者丰富自己的知识储备,欢迎关注亿速云行业资讯频道。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。