This is one of the posts that I unluckily lost on 2011-04-09 and then recovered. The information may be very old. Or not.
Time for two new C programs! At the DSA course I learned something about Hash Tables and collision resolutions.
I just implemented insert/search/print operations.
The first source code is an implementation of a Hash Map with open addressing (linear probing) as collision resolution method.
The following are the interesting functions of the program. As always, take a look at the source code for comments:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
// hashMapLinear[] is the hash map void linearProbingInsert(int value){ int probe = hash(value); while (hashMapLinear[probe]!=0){ probe = fmod((probe+1),SIZE_HASH_MAP); } hashMapLinear[probe] = value; } int linearProbingSearch(int value){ int probe = hash(value); int i; for(i=0;i<SIZE_HASH_MAP;i++){ if(hashMapLinear[probe]==value) return TRUE; probe = fmod((probe+1),SIZE_HASH_MAP); } return FALSE; } } |
Download: hash-map-linear-probing
The second program is an implementation of a Hash Map with chaining as collision resolution method.
Interesting functions:
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
// t_hashTableNode is a struct that is created as single linked list void chainedHashInsert(int value){ int probe = hash(value); if(hashMapChained[probe] == NULL){ hashMapChained[probe] = malloc(sizeof(t_hashTableNode)); hashMapChained[probe]->value = value; hashMapChained[probe]->next = NULL; }else{ t_hashTableNode *hashTableNode = hashMapChained[probe]; while(hashTableNode->next!=NULL){ hashTableNode = hashTableNode->next; } hashTableNode->next = malloc(sizeof(t_hashTableNode)); hashTableNode->next->value = value; hashTableNode->next->next = NULL; } } int chainedHashSearch(int value){ t_hashTableNode *hashTableNode = hashMapChained[hash(value)]; while(hashTableNode!=NULL){ if(hashTableNode->value==value){ return TRUE; } hashTableNode = hashTableNode->next; } return FALSE; } |
Download: hash-map-chaining.c
