C programming question on the implementation of a hash table

Question

Hi, I have a C programming question on the implementation of a hash table. I have implemented the hash table for storing some strings. I am having a problem while dealing with hash collisons. I am following a chaining linked-list approach to overcome the problem but, somehow, my code is behaving differently. I am not able to debug it. Can somebody help?

This is what I am facing: Say first time, I insert a string called gaur. My hash map calculates the index as 0 and inserts the string successfully. However, when another string whose hash also, when calculated, turns out to be 0, my previous value gets overrwritten i.e. gaur will be replaced by new string.

This is my code:

struct list
{ 
 char *string;
 struct list *next; 
};

struct hash_table
{
 int size;     /* the size of the table */
 struct list **table; /* the table elements */
}; 

struct hash_table *create_hash_table(int size)
{
    struct hash_table *new_table;
    int i;

    if (size<1) return NULL; /* invalid size for table */

    /* Attempt to allocate memory for the table structure */
    if ((new_table = malloc(sizeof(struct hash_table))) == NULL) {
        return NULL;
    }

    /* Attempt to allocate memory for the table itself */
    if ((new_table->table = malloc(sizeof(struct list *) * size)) == NULL) {
        return NULL;
    }

    /* Initialize the elements of the table */
    for(i=0; i<size; i++) 
     new_table->table[i] = '\0';

    /* Set the table's size */
    new_table->size = size;

    return new_table;
}


unsigned int hash(struct hash_table *hashtable, char *str)
{
    unsigned int hashval = 0;
    int i = 0;

    for(; *str != '\0'; str++)
    {
     hashval += str[i];
     i++;
    }

    return (hashval % hashtable->size);
}

struct list *lookup_string(struct hash_table *hashtable, char *str)
{
    printf("\n enters in lookup_string \n");

    struct list * new_list;
    unsigned int hashval = hash(hashtable, str);

    /* Go to the correct list based on the hash value and see if str is
     * in the list.  If it is, return return a pointer to the list element.
     * If it isn't, the item isn't in the table, so return NULL.
    */


    for(new_list = hashtable->table[hashval]; new_list != NULL;new_list = new_list->next)
    {
        if (strcmp(str, new_list->string) == 0)
          return new_list;
    }
    printf("\n returns NULL in lookup_string \n");
    return NULL;
}


int add_string(struct hash_table *hashtable, char *str)
{
    printf("\n enters in add_string \n");

    struct list *new_list;
    struct list *current_list;
    unsigned int hashval = hash(hashtable, str);
    printf("\n hashval = %d", hashval);

    /* Attempt to allocate memory for list */
    if ((new_list = malloc(sizeof(struct list))) == NULL)
    {
     printf("\n enters here \n");
     return 1;
    }

    /* Does item already exist? */
    current_list = lookup_string(hashtable, str);

    if (current_list == NULL)
    {
     printf("\n DEBUG Purpose \n");
     printf("\n NULL \n");
    }

    /* item already exists, don't insert it again. */
    if (current_list != NULL)
    {
     printf("\n Item already present...\n");
     return 2;
    }

    /* Insert into list */
    printf("\n Inserting...\n");

    new_list->string = strdup(str);
    new_list->next = NULL;
    //new_list->next = hashtable->table[hashval];
    if(hashtable->table[hashval] == NULL)
    {
      hashtable->table[hashval] = new_list;
    }
    else
    {
      struct list * temp_list = hashtable->table[hashval];
      while(temp_list->next!=NULL)
       temp_list = temp_list->next;

      temp_list->next = new_list;
      hashtable->table[hashval] = new_list;
    }

    return 0;
}

Answer 1

I haven't checked to confirm, but this line looks wrong:

hashtable->table[hashval] = new_list;

This is right at the end of the last case of add_string. You have:

• correctly created the new struct list to hold the value being added
• correctly found the head of the linked list for that hashvalue, and worked your way to the end of it
• correctly put the new struct list at the end of the linked list

BUT then, with the line I quote above, you are telling the hash table to put the new struct list at the head of the linked list for this hashvalue! Thus throwing away the whole linked list that was there before.

I think you should omit the line I quote above, and see how you get on. The preceding lines are correctly appending it to the end of the existing list.

Answer 2

The hash function must be a function which take your data in entry and return delimited id (eg: integer between 0 and HASH_MAX)

Then you must stock your element in a list in the Hash(data) index of a hash_table array. if a data have the same hash, it will be stock in the same list as the previous data.

struct your_type_list {
  yourtype data;
  yourtype *next_data;
};

struct your_type_list hash_table[HASH_MAX];

Answer 3

The statement hashtable->table[hashval] = new_list; is the culprit. You insrted the new_list ( I think better name would have been new_node) at end of the linked list. But then you overwrite this linked list with new_list which is just a single node. Just remove this statement.

Answer 4

As others have already pointed out, you are walking to the end of the list with temp_list, appending new_list to it, then throwing away the existing list.

Since the same value NULL is used to indicate an empty bucket and the end of the list, it's quite a bit easier to put the new item at the head of the list.

You also should do any test which would result in the new item not being added before creating it, otherwise you will leak the memory.

I would also have an internal lookup function that takes the hash value, otherwise you have to calculate it twice

int add_string(struct hash_table *hashtable, char *str)
{
    unsigned int hashval = hash(hashtable, str);

    /* item already exists, don't insert it again. */
    if (lookup_hashed_string(hashtable, hashval, str))
        return 2;

    /* Attempt to allocate memory for list */
    struct list *new_list = malloc(sizeof(struct list));

    if (new_list == NULL)
        return 1;

    /* Insert into list */
    new_list->string = strdup(str);
    new_list->next = hashtable->table[hashval];

    hashtable->table[hashval] = new_list;

    return 0;
}