C hashtable implementation

Question

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: %s\n", item->data);
     } 
     else {
        printf("Element not found\n");
     }

     deleteHash(hashArray, item);
     item = getValueByKey(hashArray, 100);

     if (item != NULL) {
        printf("Element found: %s\n", item->data);
     } 
     else {
        printf("Element not found\n");
     }
     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!

Answer 1

Fix the compiler warnings

These should all be straightforward to address:

gcc -std=c17 -fPIC -g -Wall -Wextra -Wwrite-strings -Wno-parentheses -Wpedantic -Warray-bounds      -Wconversion    171784.c    -o 171784
171784.c:11:1: warning: ‘typedef’ is not at beginning of declaration [-Wold-style-declaration]
 }typedef DataItem;
 ^
171784.c: In function ‘main’:
171784.c:163:36: warning: passing argument 3 of ‘putValueForKey’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
     putValueForKey(hashArray, 100, "MAIN");
                                    ^~~~~~
171784.c:56:58: note: expected ‘char *’ but argument is of type ‘const char *’
 void putValueForKey(DataItem** hashArray, int key, char *data) {
                                                    ~~~~~~^~~~
171784.c:164:36: warning: passing argument 3 of ‘putValueForKey’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
     putValueForKey(hashArray, 107, "LOOP");
                                    ^~~~~~
171784.c:56:58: note: expected ‘char *’ but argument is of type ‘const char *’
 void putValueForKey(DataItem** hashArray, int key, char *data) {
                                                    ~~~~~~^~~~
171784.c:165:36: warning: passing argument 3 of ‘putValueForKey’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
     putValueForKey(hashArray, 121, "END");
                                    ^~~~~
171784.c:56:58: note: expected ‘char *’ but argument is of type ‘const char *’
 void putValueForKey(DataItem** hashArray, int key, char *data) {
                                                    ~~~~~~^~~~
171784.c:166:36: warning: passing argument 3 of ‘putValueForKey’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
     putValueForKey(hashArray, 122, "STR");
                                    ^~~~~
171784.c:56:58: note: expected ‘char *’ but argument is of type ‘const char *’
 void putValueForKey(DataItem** hashArray, int key, char *data) {
                                                    ~~~~~~^~~~
171784.c:167:36: warning: passing argument 3 of ‘putValueForKey’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
     putValueForKey(hashArray, 129, "LENGTHHHHHHHHHHHHHHHHHHHHH");
                                    ^~~~~~~~~~~~~~~~~~~~~~~~~~~~
171784.c:56:58: note: expected ‘char *’ but argument is of type ‘const char *’
 void putValueForKey(DataItem** hashArray, int key, char *data) {
                                                    ~~~~~~^~~~
171784.c:168:36: warning: passing argument 3 of ‘putValueForKey’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
     putValueForKey(hashArray, 132, "K");
                                    ^~~
171784.c:56:58: note: expected ‘char *’ but argument is of type ‘const char *’
 void putValueForKey(DataItem** hashArray, int key, char *data) {
                                                    ~~~~~~^~~~
171784.c:169:36: warning: passing argument 3 of ‘putValueForKey’ discards ‘const’ qualifier from pointer target type [-Wdiscarded-qualifiers]
     putValueForKey(hashArray, 133, "M1");
                                    ^~~~
171784.c:56:58: note: expected ‘char *’ but argument is of type ‘const char *’
 void putValueForKey(DataItem** hashArray, int key, char *data) {
                                                    ~~~~~~^~~~

Fix the memory leak

valgrind -q --leak-check=full ./171784   
 (100,MAIN) (121,END) (122,STR) ~~  ~~  ~~  ~~  (107,LOOP) ~~  (129,LENGTHHHHHHHHHHHHHHHHHHHHH) ~~  ~~  (132,K) (133,M1) ~~  ~~  ~~  ~~  ~~  ~~ 
Element found: MAIN
Element not found
 ~~  (121,END) (122,STR) ~~  ~~  ~~  ~~  (107,LOOP) ~~  (129,LENGTHHHHHHHHHHHHHHHHHHHHH) ~~  ~~  (132,K) (133,M1) ~~  ~~  ~~  ~~  ~~  ~~ 
==26310== 16 bytes in 1 blocks are definitely lost in loss record 1 of 1
==26310==    at 0x483577F: malloc (in /usr/lib/x86_64-linux-gnu/valgrind/vgpreload_memcheck-amd64-linux.so)
==26310==    by 0x109271: putValueForKey (171784.c:60)
==26310==    by 0x10955D: main (171784.c:163)
==26310== 

It seems that the first item to be inserted was never freed.

That seems to be a bug in the test program: deleteHash() transfers ownership to its caller, meaning that main() is now responsible for freeing that item. It's easily fixed:

free(deleteHash(hashArray, item));

However, this is a warning that you might not have thought sufficiently about ownership of objects, in general. Give this some more thought, and try to make your code easy to use correctly, and harder to use incorrectly.

Style points

I noticed a few things whilst looking at this, but haven't done a thorough inspection. Other reviews have addressed quite a few style points; I'll try to make only new observations here.

• Don't cast the result of malloc() and family, and prefer to use the size of the variable rather than its type, to ensure consistency (and make that consistency obvious):

  DataItem *item =  malloc(sizeof *item);
  

• It's fine to pass a null pointer to free(), so there's very little point pre-testing the argument:

  for (size_t i = 0;  i < SIZE;  ++i) {
      free(hashArray[i]);
  }
  

Add more tests

The main() function performs only a very basic test. We should add tests that

• attempt to insert duplicate keys and entries with negative keys
• attempt to insert more than SIZE entries
• attempt to remove keys that aren't present

And we might consider tests of misuse, such as

• calling freeHashTable() twice

Advanced testing would also substitute malloc() with a library that allows failure injection, so that we can test the error paths.

Answer 2

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.

Answer 3

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.

Answer 4

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;
}