Tukukkk

The following code is an implementation of an hashtable in C.

hashTable.c:

  #include <stdio.h>

  #include <string.h>

  #include <stdlib.h>



  #include "hashTable.h"



  int hashCode(int key) {

     return key % SIZE;

  }



  /*

     By given key returns a pointer to a DataItem with the same key

     Input: Pointer to hashArray array, int key value

     Output: If key found - the pointer to a DataItem else NULL

  */

  DataItem *getValueByKey (DataItem** hashArray, int key) {

     /* Get the hash */

     int hashIndex = hashCode(key);  



     /* Move in array until an empty */

     while(hashArray[hashIndex] != NULL) {



        if(hashArray[hashIndex]->key == key)

           return hashArray[hashIndex]; 



        /* Go to next cell */

        ++hashIndex;



        /* Wrap around the table */

        hashIndex %= SIZE;

     }        



     return NULL;        

  }



  /*

     Adding a DataItem to a hashArray

     Input: Pointer to hashArray array, int key value, char* (string) data value

     Output: None

  */

  void putValueForKey (DataItem** hashArray, int key, char *data) {

     /* Get the hash */

     int hashIndex = hashCode(key);



     DataItem *item = (DataItem*) malloc(sizeof(DataItem));

     item->data = data;  

     item->key = key;



     /* Move in array until an empty or deleted cell */

     while(hashArray[hashIndex] != NULL) {

        /* Go to next cell */

        ++hashIndex;



        /* Wrap around the table */

        hashIndex %= SIZE;

     }



     hashArray[hashIndex] = item;

  }



  /*

     Deleting a DataItem node from an hash array

     Input: Pointer to hashArray array, pointer to the item we want to delete

     Output: The deleted item pointer

  */

  DataItem* deleteHash (DataItem** hashArray, DataItem* item) {

     int key;

     int hashIndex;

     if (item == NULL)

     {

        return NULL;

     }



     key = item->key;



     /* Get the hash */

     hashIndex = hashCode(key);



     /* Move in array until an empty */

     while(hashArray[hashIndex] != NULL) {



        if(hashArray[hashIndex]->key == key) {

           DataItem* temp = hashArray[hashIndex]; 



           /* Assign a dummy item at deleted position */

           hashArray[hashIndex] = NULL; 

           return temp;

        }



        /* Go to next cell */

        ++hashIndex;



        /* Wrap around the table */

        hashIndex %= SIZE;

     }      



     return NULL;        

  }



  /*

     displaying an hash array

     Input: Pointer to hashArray array

     Output: None

  */

  void displayHashTable (DataItem** hashArray) {

     int i = 0;



     for (i = 0; i < SIZE; i++) {



        if (hashArray[i] != NULL)

           printf(" (%d,%s)",hashArray[i]->key,hashArray[i]->data);

        else

           printf(" ~~ ");

     }



     printf("n");

  }



  /*

     Freeing an hash array

     Input: Pointer to hashArray array

     Output: None

  */

  void freeHashTable (DataItem** hashArray) {

     int i = 0;

     for (i = 0; i < SIZE; ++i)

     {

        if (hashArray[i] != NULL) {

           free(hashArray[i]);

        }

     }

  }



  /*

     Initialize an hash array by setting all the nodes to NULL

     Input: Pointer to hashArray array

     Output: None

  */

  void initializeHashArray (DataItem** hashArray) {

     int i = 0;

     for (i = 0; i < SIZE; i++) {

        hashArray[i] = NULL;

     }

  }



  int main() {

     DataItem* hashArray[SIZE];

     initializeHashArray(hashArray);



     putValueForKey(hashArray, 100, "MAIN");

     putValueForKey(hashArray, 107, "LOOP");

     putValueForKey(hashArray, 121, "END");

     putValueForKey(hashArray, 122, "STR");

     putValueForKey(hashArray, 129, "LENGTHHHHHHHHHHHHHHHHHHHHH");

     putValueForKey(hashArray, 132, "K");

     putValueForKey(hashArray, 133, "M1");





     displayHashTable(hashArray);

     DataItem* item = getValueByKey(hashArray, 100);



     if (item != NULL) {

        printf("Element found: %sn", item->data);

     } 

     else {

        printf("Element not foundn");

     }



     deleteHash(hashArray, item);

     item = getValueByKey(hashArray, 100);



     if (item != NULL) {

        printf("Element found: %sn", item->data);

     } 

     else {

        printf("Element not foundn");

     }

     displayHashTable(hashArray);



     freeHashTable(hashArray);

  }

I believe this code is well commented and very understandable, if you think it's not please let me know.

The main is there just for testing and will not be part of the final code.

My main concerns are:

1. The free function (freeHashTable) because I don't know how to test it so I don't know if it's working.




2. The while loops that might get into an infinite loop condition for some reason.

Also this is the first time I'm trying to implement hash table, so if I'm missing something from the logical aspect of hash code explanation will be very welcomed.

hashTable.h:

#define SIZE 20



struct DataItem {

    char *data;   

    int key;

}typedef DataItem;



DataItem *getValueByKey (DataItem** hashArray, int key);

void putValueForKey (DataItem** hashArray, int key, char *data);

DataItem* deleteHash (DataItem** hashArray, DataItem* item);

void displayHashTable (DataItem** hashArray);

void freeHashTable (DataItem** hashArray);

void initializeHashArray (DataItem** hashArray);

Thanks in advance!

1. while loops can never terminate if the table is full. If all the slots're used and you're trying to insert a new element or look for a key that isn't there, it'll keep wrapping around as there're no NULL elements in the array.




2. You can fix it by terminating the loop after SIZE iterations, but it's only part of the problem.




3. The real question is: what is the desired behavior in this case? Being unable to keep more than SIZE elements (which should be known at compile time) is a serious limitation. In fact, a hash table that can hold only 20 elements is likely to be quite useless in practice (if the amount of data is so small, a simple array is unlikely to cause any performance issues). Ideally, the table should grow when there's too little room left. Roughly speaking, you should allocate a larger array, rehash the elements, but them into it, and delete old array.




4. Even if you decide to keep it fixed-size for simplicity, you need to indicate that the table is full somehow. It shouldn't silently fail to insert a new element. Using error codes is a typical way to do it in C.




5. You can run your program under valgrind (or some other memory-checking tool) to see if it leaks memory. If it does, your free... function's wrong (or is called improperly).




6. Assuming that malloc always returns a valid pointer is dangerous. It may not. You need to check if its return value is not NULL before working with it.




7. deleteHash is not a good name. It doesn't delete a hash. It deletes a key. It should be called correspondingly.




8. It's not clear how you code behaves if the user tries to insert a key that's already in the table. Does it allow duplicates? What value does it return upon lookup in this case? Whatever the policy is, document it.

Bug

If you insert a key, it might get pushed forward in the array because other keys are in the way. Then if you delete one of those keys that were in the way, you can never retrieve the first key. For example, imagine that key A and key B hash to the same index. Then if you do this :

putValueForKey(hash, A, data1); // Ends up in slot [0]

putValueForKey(hash, B, data1); // Ends up in slot [1]

deleteHash(hash, A);            // Now slot [0] is NULL

Then you can never find key B again:

// Here, ret becomes NULL because the hash table can't find B any more!

ret = getValueByKey(hash, B);

In order to fix this bug, your deletion function needs to be a lot more complicated. You should read this wikipedia article on how to delete an item when using linear probing. Better yet, you could choose a different collision strategy than linear probing. Here are some alternatives.

The while loops that might get into an infinite loop condition for some reason.

Bug: ability to generate negative hash indexes leads to UB, which includes the above concern.

putValueForKey(hashArray, -100, "minus");

Should key have a negative value, so will hashCode() return a negative value which causes out-of-bounds array access.

Various ways to handle that. For me I would use an unsigned type like unsigned or size_t. Also amend calling code.

// int hashCode(int key) {

unsigned hashCode(int key) {

 return (unsigned) key % SIZE;

}

Other idea:

Consider prime values for HASH

Certainly hashCode() here is a simple function and not truly meant to hash the key highly uniformly across [0...SIZE). Yet remember that if the hash calculation before the final % SIZE is good, finding the remainder with any SIZE will be good too.

On the other hand (OTOH), if the hash calculation before the % SIZE is weak, using a prime for SIZE will likely to make it better. Example

// #define SIZE 20

#define SIZE 23



unsigned hashCode(int key) {

 return (unsigned) key % SIZE;

}

If you really do not know how to test your freeing function, then try first add some 20 random numbers to your hashtable, and then try to add some sorted numbers, to your hash, if still does not work, then try to add some more values.
i am not a reviewer, i am just stuck in the problem i described, but i can not free my hashtable. codes which i am trying in my hash are like these.

printf("Inserting 10000 random values to hash");

    start=clock();

    for (key = 0; key < SIZE ; key++)

    {

        value = rand() % 1000;

        insert(key, value);

    }

    end=clock();

    printf("nDone. Took %.8f secondsnn", (double) (end - start) / CLOCKS_PER_SEC);



// Search in Hash



    printf("Searching 10000 random values in hash");

    start=clock();

    for(key=0;key<SIZE;key++)

    {

    item=search(key);

    }

    end=clock();



    printf("nDone. Took %.8f secondsnn", (double) (end - start) / CLOCKS_PER_SEC);

now try to insert some sorted values or something like that, and when you are trying to add some other values to the hash, you will not be able. now you can call your free function.

printf("Inserting 10000 sorted values to hash");

    start=clock();

    for(int key=0;key<SIZE;key++){

    insert(key, key);

    }

    end=clock();

    printf("nDone. Took %.8f secondsnn", (double) (end - start) / CLOCKS_PER_SEC);





// search in Hash with sorted values



     printf("Search 10000 sorted values in hash");

    start=clock();

    for(int key=0;key<SIZE;key++){

    item=search(key);

    }

    end=clock();

    printf("nDone. Took %.8f secondsnn", (double) (end - start) / CLOCKS_PER_SEC);

i assume that you already declared your necessary functions in your main, like clock_t start, end; and others.

Note: this is not a review of your code, i just wanted to give you an idea of how you can test your free function. i hope that i am right, and this help you.