Hash Map Library for any type (Void Pointers)

Question

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?

Answer 1

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.