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.