Shulou(Shulou.com)06/02 Report--

This article shows you how to write a hash table in C language, the content is concise and easy to understand, it will definitely brighten your eyes. I hope you can get something through the detailed introduction of this article.

First, quickly understand the hash table

A hash table is an array whose subscript can be alphabetic.

Suppose you have an array int a, and if you want to find the 40th element in it, you can simply type a [40] with a time complexity of O (1).

The problem is that when a subscript is not a number, but a string, it may require an extra large space to store all the subscripts in a specific location. For example, if you use uppercase and lowercase letters as the subscript index, then one bit needs to reserve 52 spaces, and 10 bits need as much space as 52 to the 10th power, and there is no equipment to meet it.

Fortunately, such a large number of 52 to the 10th power is beyond the scope of normal use, no matter how long the index, the value we can use is absolutely limited.

For example, the following three strings are available as subscript

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

In fact, you only need to choose the first and last letters to distinguish the three strings, that is,

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

However, this algorithm requires very high index characters, at least it can not be repeated at the beginning and end. So now we need an algorithm that can map very long strings to specific short strings and avoid repetition as much as possible.

2. Hash function

The simplest hash function is the remainder, which converts the input string into an integer bit by bit. Since the string may be converted to a very large integer, it is necessary to understand the nature of the remainder

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

Accordingly, there are:

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

The implementation in C language is as follows:

# include # define MAXHASH 100amp / Quick Power method, a * b ^ n% cint 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.exeasdf21microcold81tinycold12microcool5minicool81minicold73 III. Anti-collision

Although minicool and microcold crashed, it was a good performance to represent a sample of 52 to the ninth power by digits less than 100.

To avoid a crash, you need to change the element type in the array-at least a structure. The way to prevent a collision is very simple. If there is a crash, I will not hash it and send it directly to a specified array.

# include # define MAXHASH 100typedef struct HASHNODE {char * key; int next;} * hashNode;struct HASHNODE* hashTable [MAXHASH]; struct HASHNODE* crashTable [MAXHASH]; / / Storage the post-impact value int numCrash=0; / / the existing impact value void initTable () {for (int item0; 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); / / A new node} else {if (crashTable [index]-> next==-1) crashTable [index]-> next= numCrash; insertCrash (str, hashTable [index]-> next, n) }} / / n is the string length 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]->

Printf ("hashTable [% d]:% s\ n", I, hashtable [I]-> key); if (crashTable [% d]:% s\ n ", I, crashtable 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.exeasdf21hellworld84microcold81minicool81tinycool20tinycold12weixiaoleng11exitcrashTable [0]: minicoolhashTable [11]: weixiaolenghashTable [12]: tinycoldhashTable [20]: tinycoolhashTable [21]: asdfhashTable [81]: microcoldhashTable [84]: hellworld

It can be seen that on the one hand, it is indeed hashed, on the other hand, it is indeed collision-proof.

The above is how to write a hash table in C language. have you learned any knowledge or skills? If you want to learn more skills or enrich your knowledge reserve, you are welcome to follow the industry information channel.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.