Dictionary implementation using hash table in C

Question

I have written the below code which loads the dictionary and checks if the given word is present or not.

The implementation is using a hash table with a chained linked list.

In regards to the hash function, I have kept it simple as I was not very concerned about collisions.

Can someone please review it and let me know of anything I should improve? Like:

1. Optimizations
2. Standard practices
3. how to cover boundary/error condition?

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

#define SPELL_CHECKER

#ifdef SPELL_CHECKER

#define SIZE 10000                /* Number of elements in table */
#define WORD_SIZE 100             /* Max size of word */

typedef struct CHAINELEMENTS
{
    char word[100];               /* word to be saved in list */
    struct CHAINELEMENTS *next;   /* pointer to next element  */
}chainelements;

typedef struct TBLELEMENTS
{
    int total_elements;           /* total elements in chain  - Not used here so far  */
    chainelements *baseelement;   /* Pointer to chained linked list of words */
}tblelements;

typedef struct HASHTABLE
{
    int size;                     /* Number of table elements in hashtable */
    tblelements *base;            /* Pointer to first table element */
}hashtable;


/* 
  Below functions accomplish task as listed
  1. Create HASHTABLE
  2. For given string find its key and hash index
  3. Search the word in hashtable
  4. if word doesnt exist insert the word
 */

hashtable* createHashTable(int size);

int getKey(char *string);

void insertWord(hashtable *phashtable, char *str);

bool searchWord(hashtable *phashtable, char *str);


int main(void)
{
    FILE *fp1;
    char oneword[WORD_SIZE];
    char c;
    char *searchword = "abash";
    bool ispresent;
    hashtable *phashtable = createHashTable(SIZE);

    fp1 = fopen("snippet.txt", "r");

    do
    {
        c = fscanf(fp1, "%s", oneword); /* got one word from the file */
        printf("%s \n", oneword);       /* display it on the monitor  */
        insertWord(phashtable, oneword);
        insertWord(phashtable, oneword);  /* Test code to check insert does not happen again*/

    } while (c != EOF);


    ispresent = searchWord(phashtable, searchword);

    printf("IS the searchword  %s   present  -- %d \n", searchword, ispresent);

    fclose(fp1);
    return 0;
}

/*
    Funcntion    - searchWord(hashtable *phashtable, char *str)
    Input params - pointer to hashtable and word to be searched
    Return value - returns 1 if word is present else 0
    Task         - for given string finds it's hashindex
                   and searches all nodes in that chain to see if
                   word is present
 */
bool searchWord(hashtable *phashtable, char *str)
{
    /* error condition check */
    if (phashtable == NULL || str == NULL)
    {
        fprintf(stderr, " -- invalid pointer to string or hashtable -- \n");
        return false;
    }

    int hashindex = getKey(str);

    /* error condition check */
    if (hashindex > SIZE)
    {
        fprintf(stderr, " -- invalid hashindex -- \n");
        return false;
    }

    /* pointer to first element of the chained linked list */
    chainelements *pchainelements = phashtable->base[hashindex].baseelement;

    while (pchainelements != NULL)
    {
        /* compares the given word with present in node */
        if (!strcmp(pchainelements->word, str))
        {
            return true;
        }
        pchainelements = pchainelements->next;
    }

    return false;
}

/*
    Funcntion    - insertWord(hashtable *phashtable, char *str)
    Input params - pointer to hashtable and word to be inserted
    Return value - none
    Task         - for given string finds it's hashindex
                   and searches all nodes in that chain to see if
                   word is present if it's not present creates a 
                   new node and appends the word at the end of chain
*/
void insertWord(hashtable *phashtable, char *str)
{   
    if (phashtable == NULL || str == NULL)
    {
        return;
    }

    bool ispresent;
    int hashindex = getKey(str);

    if (hashindex > SIZE)
    {
        fprintf(stderr, " -- invalid hashindex -- \n");
        return;
    }

    chainelements *pchainelements = phashtable->base[hashindex].baseelement;

    /* if no elements are present - insert word */
    if (!pchainelements)
    {
        pchainelements = (chainelements *)malloc(sizeof(chainelements));
        if (pchainelements == NULL)
        {
            fprintf(stderr, " -- memory allocation failed for the word -- \n");
        }
        phashtable->base[hashindex].baseelement = pchainelements;
        strcpy(pchainelements->word, str);
        pchainelements->next = NULL;
    }
    else
    {
        /* Check if the word is already present if not insert*/
        ispresent = searchWord(phashtable, str);

        if (ispresent == 0)
        {
            printf("insert word   is not present - so inserting %s \n", str);

            /* Can this part be optimized ?? while searching we already reached
               till the end of loop now again before inserting we have to traverse 
               Another option is to do compare here only but that would result in
               same code present at two point - What is better stratergy ?
             */
            while (pchainelements->next != NULL)
            {
                pchainelements = pchainelements->next;
            }

            pchainelements->next = (chainelements *)malloc(sizeof(chainelements));
            if (pchainelements->next == NULL)
            {
                fprintf(stderr, " -- memory allocation failed for the word -- \n");
            }

            pchainelements = pchainelements->next;
            strcpy(pchainelements->word, str);
            pchainelements->next = NULL;
        }
    }
}

/*
    Funcntion    - getKey(char *string)
    Input params - string for which key is needed
    Return value - Returns the hashindex based on key
    Task         - for given string finds it's key.
                   for key generation a simple multiplcation 
                   is done, no logic used and once key is 
                   generated mod is performed based on size 
                   of hashtable
*/
int getKey(char *string)
{
    unsigned int key = 0;
    char *pstring = string;

    while (*pstring != '\0' && key < ULONG_MAX)
    {
        key += *pstring * 32;
        pstring++;
    }

    key = key % SIZE;

    return key;
} 

/*
    Funcntion    - createHashTable(int size)
    Input params - Table size 
    Return value - pointer to created hashtable
    Task         - hashtable is created based on given
                   size and all the hash table elements are 
                   initialized to NULL
*/

hashtable* createHashTable(int size)
{
    int i;

    /* error condition check */
    if (size < 1 || size > SIZE)
    {
        fprintf(stderr, " invalid size of hashtable suggested exiting ...\n");
        exit(1);
    }

    hashtable *phashtable = (hashtable *)malloc(sizeof(hashtable));

    if (phashtable == NULL)
    {
        fprintf(stderr, "memory allocation failed for hashtable...\n");
    }

    phashtable->size = size;

    if (size > 0)
    {
        phashtable->base = (tblelements *)malloc(sizeof(tblelements) * phashtable->size);

        if (phashtable->base == NULL)
        {
            fprintf(stderr, "memory allocation failed for table elements ... \n");
        }

        for (i = 0; i < size; i++)
        {
            phashtable->base[i].baseelement = NULL;
        }
    }

    return phashtable;
}

#endif

Answer 1

• Exceptional conditions

  It is infeasible to hashindex > SIZE ever hold. If it ever happen, the flow of the program execution is broken so badly that the only reasonable action is to abort and dump core. As coded, searchWord returning false simply lies to the rest of the program.

• Hash recomputation

  insertWord computes the hash, and calls searchWord which also computes the hash. I recommend to have a search helper with signature

  bool doSearchWord(phashtable * table, char * str, int hash);
  

  and call it from both searchWord and insertWord with precomputed hash.

• Cast malloc

  Don't do it

• Memory usage

  The word in the table occupies 100 bytes no matter what. It is possible (even though quite unlikely) to corrupt heap with very long words. It is also very wasteful. You should either allocate just right memory with strdup(), or memory map your file and use pointers into the mapped data.

• What is a better strategy?

  Since you don't care about an order in which collided words appear in the cain, always insert at the beginning. You wouldn't need to special case the empty chain, and the insertion code becomes

  ispresent = searchWord(phashtable, str);
  
  if (ispresent == 0)
  {
      printf("insert word   is not present - so inserting %s \n", str);
  
      pchainelements = malloc(sizeof(chainelements));
      if (pchainelements == NULL)
      {
          fprintf(stderr, " -- memory allocation failed for the word -- \n");
      }
  
      base = phashtable[hashindex].baseelement;
      phashtable->base[hashindex].baseelement = pchainelements;
      strcpy(pchainelements->word, str);
      pchainelements->next = base;
  }
  

Answer 2

Add spaces in your typedef statements.

typedef struct CHAINELEMENTS
{
  char word[100];               /* word to be saved in list */
  struct CHAINELEMENTS *next;   /* pointer to next element  */
} chainelements;

---

You should use underscores in your variables names, e.g. chainelements should be chain_elements. Furthermore, it should actually be chain_element, since it is only referring to one chain element. Even though this type is used to create a linked-list, it itself is only one element in the chain.

---

Declaring char word[100] is just asking for trouble (e.g. a buffer overflow). You should either

1. Create a macro #DEFINE MAX_ELEMENT_LENGTH 100 and then check everywhere that you copy into word that you are only copying MAX_ELEMENT_LENGTH bytes. However, this is error-prone, and wastes a lot of memory.

2. The better approach is to make it a dynamic string: char *word. Yes you have to spend some time allocating space on the heap, but this is a small trade-off.

---

You do not need to check if (hash_index > SIZE) because that is a post-condition of the getKey function. If there's an error it should be caught in testing, not in another function.

---

You want to explicitly check for the 0 return val from strcmp:

if (strcmp(pchain_element->word, str) == 0)

Not only is his better style in my opinion, but note that !(-1) actually evalutes to true!

---

You should use true and false instead of 1 and 0 in your Return description of searchWord.

---

You do not need to explicitly cast the result of malloc, the casting happens implicitly. See this thread.

---

Declare variables as late as possible (right before they are used). For example, you declare is_present at the top of insertWord, but it is only used much later (and only in the scope of one else block).

---

Use booleans! For example, you have is_present = searchWord(phashtable, str), which is a bool, but you then perform the comparison if (is_present == 0). You should instead do the much cleaner if (!is_present). C's type system is primitive, but we should at least use the small number of types we have available!

---

Your getKey(char*) function should be called hash or getIndex. It's getting an index into an array, whereas the word key is usually reserved for an associative array (i.e. a Hash Map, whereas this is a Hash Table).

---

In createHashTable, you don't need to check if (size > 0), you already check for that at the beginning of the function.

---

You should never printf or exit from a library function. You do this in createHashTable. Instead, just return some sensible error value (in this case NULL), and optionally set errno.

---

Finally, in regards to your question on optimization. To avoid searching through the chain twice, a good solution is to insert the new element at the beginning of the chain instead of the end. This will take constant time with respect to the size of the chain, instead of linear time.