hash maps with linear probing and separate chaining
2011-04-09
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:
// 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
I do not use a commenting system anymore, but I would be glad to read your feedback. Feel free to contact me.