Hash Maps with linear probing and separate chaining
April 28th, 2008Time 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:
// 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.c
The second program is an implementation of a Hash Map with chaining as collision resolution method.
Interesting functions:
// 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
Tags: address, algorithms, C language, code, data structures, Download, hash, hash map, hash table, HTTP, java, javascript, link, list, page, pageTracker, php, pro, rest, source, source code, Wiki, wikipedia
September 26th, 2009 at 17:14
[...] [...]