Categories: Programming
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:
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:
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
Recent Comments: