1
\$\begingroup\$

This is a hash map library for C that stores void* pointers with char* strings (null terminated) for keys

//  ColiisionHashMap
//  Copyright © 2015 Leo Dastur.
//

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct HashMapNode {
    char* key;
    void* data;
} HashMapNode;

typedef struct HashLocation {
    HashMapNode** nodes;
    int numberNodes;
} HashLocation;

typedef struct HashMap {
    int mapSize;
    struct HashLocation** hasharray;

} HashMap;

HashMap* newHashMap(int mapSize) {
    if (mapSize<=0) {
        abort(); //Zero Mapsize is bad
    }
    HashLocation** array= calloc(mapSize, sizeof(HashLocation*));

    for (int i = 0; i<mapSize; i++) {
        array[i] = malloc(sizeof(HashLocation));
        array[i]->nodes=NULL;
        array[i]->numberNodes=0;
    }

    HashMap* aHashMap = calloc(1, sizeof(HashMap));
    aHashMap->mapSize = mapSize;
    aHashMap->hasharray = array;
    return aHashMap;
}

int keyHash (HashMap* aHashMap, char* key, int key_len) {
    int charSum=0;
    int i;
    for (i=0; i<key_len; i++) {
        charSum+=key[i];
    }
    return charSum % aHashMap->mapSize;
}

int getStringlen(char* astring) {
    strlen(astring);
/*
    int counter=0;
    while (astring[counter]!='\0') {
        counter++;
    }
 */
    return (int) strlen(astring); /*counter;*/

}

void mapAdd(HashMap* aHashMap, char* key, char* data) {
    int key_len = getStringlen(key);
    int hashed_key = keyHash(aHashMap, key, key_len);

    HashMapNode* dataNode = malloc(sizeof(HashMapNode));
    dataNode->key=key;
    dataNode->data=data;

    HashLocation* theHashlocation = aHashMap->hasharray[hashed_key];
    if (theHashlocation->nodes==NULL) {
        theHashlocation->nodes = calloc(1, sizeof(HashMapNode*));
        theHashlocation->nodes[0]=dataNode;
        theHashlocation->numberNodes=1;
    } else {
        realloc(theHashlocation->nodes, theHashlocation->numberNodes+1);
        theHashlocation->nodes[theHashlocation->numberNodes] = dataNode;
        theHashlocation->numberNodes++;
    }

}

void* mapGet(HashMap* aHashMap, char* key) {
    int key_len = getStringlen(key);
    int hashed_key = keyHash(aHashMap, key, key_len);

    HashLocation* theHashLocation = aHashMap->hasharray[hashed_key];
    if (theHashLocation->nodes==NULL) {
        return NULL;
    }
    if (theHashLocation->numberNodes==1) {
        HashMapNode* dataNode = theHashLocation->nodes[0];
        return dataNode->data;
    }
    else {
        //Get Node Array, Search Node Array for key, return that node's data. Return NULL if key is not found.
        HashMapNode** nodeArray = theHashLocation->nodes;
        int array_len = theHashLocation->numberNodes;
        HashMapNode* dataNode = NULL;

        for (int i = 0; i < array_len; i++) {
            if (!strcmp(nodeArray[i]->key, key) ) {
                dataNode = nodeArray[i];
                // printf("Found Key");
                break;
            }
            //else printf("Didn't Find it yet");
        }
        if (dataNode==NULL) {
            return NULL;
        }
        else return dataNode->data;
    }
}

Is there a more efficient way of handling collisions, and what else could I do to make this a real-world usable map?

\$\endgroup\$
2
\$\begingroup\$

Bug

Suppose there are 2 keys that hash to the same bucket (i.e. HashLocation). If you add key #1 and then search for key #2, mapGet() will return the data for key #1 instead of returning NULL. The problem is here:

if (theHashLocation->numberNodes==1) {
    HashMapNode* dataNode = theHashLocation->nodes[0];
    return dataNode->data;
}

Here, you assume that if there is only one node in the bucket, that it must match the key you are looking for. But you need to still compare the key to see if it matches.

Unnecessary array of pointers

Your hasharray inside HashMap is an array of pointers to HashLocations. There's no need for hasharray to be an array of pointers. It should simply be an array of HashLocations instead. Using one contiguous array is simpler (less allocations) and better for cache locality.

Bad reallocation strategy

The way you resize each bucket when it grows is by reallocating by one element larger. This will use \$O(n^2)\$ time because of all the recopying required. You should use a better reallocation strategy such as doubling the size every time and keeping track of how many elements are being used.

Poor hash function

Your hash function simply adds each character of the string together. This is a poor hash function which will result in many hash collisions. You should try something different such as rotating the hash by 5 bits every time you add the next character in. Here is a StackOverflow question about string hashes, and a short webpage describing a few string hashes, linked from that question.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions. For the Reallocation Strategy, my system manual says this about Realloc: "The realloc() function tries to change the size of the allocation pointed to by ptr to size, and returns ptr. If there is not enough room to enlarge the memory allocation pointed to by ptr, realloc() creates a new allocation, copies as much of the old data pointed to by ptr as will fit to the new allocation, frees the old allocation, and returns a pointer to the allocated memory." Does this make the average running time better, or should I still avoid calling it? \$\endgroup\$ – TheInnerParty Nov 12 '15 at 9:41
  • \$\begingroup\$ @TheInnerParty if each time you call realloc() original buffer can't grow then each time it will make a copy. If you allocate more space than required then you will reduce reallocation (and its expansive copies). Consider that often allocation strategy is not sequential but it problem is still there... \$\endgroup\$ – Adriano Repetti Nov 12 '15 at 13:14
  • \$\begingroup\$ @TheInnerParty Maybe this StackOverflow question could help you understand why doubling the size works better. \$\endgroup\$ – JS1 Nov 12 '15 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.