C programming question to implement a hash table
I have a C programming question on a hash table implementation. I have implemented a hash table to store some strings. I have a problem while working with hashing. I am using chaining of linked links to solve the problem, but somehow my code behaves differently. I cannot debug it. Can anyone please help?
This is what I ran into: Let's say the first time I insert a line called gaur. My hashmap calculates the index as 0 and inserts the row successfully. However, when another string whose hash is also 0 when computed, my previous value becomes overrwritten, i.e. Gaura will be replaced with a new line.
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 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;
}
a source to share
I haven't checked the confirmation, but this line doesn't look right:
hashtable->table[hashval] = new_list;
This is true at the end of the last case add_string
. You have:
- correctly created a new
struct list
one to keep the added value - found the linked list chapter correctly for this hashvalue and worked its way all the way to the end.
- put the new one correctly
struct list
at the end of the linked list
BUT then when the string above you tell the hashtable to put a new one struct list
in the head of the linked list for that hashvalue! Thus, throwing away the entire linked list that was there before.
I think you should omit the line I quote above and see how you get along. The preceding lines correctly add it to the end of the existing list.
a source to share
As others have already pointed out, you go to the end of the list with temp_list
adding to it new_list
and then discarding the existing list.
Since the same value is NULL
used to indicate the empty bucket and the end of the list, it is fairly easy to put a new item at the beginning of the list.
You should also do any test that will result in the new item not being added before it is created, otherwise you will leak memory.
I would also have an internal lookup function that takes a 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;
}
a source to share
The hash function should be a function that takes your data as input and returns a delimited identifier (for example: an integer from 0 to HASH_MAX)
Then you have to store your element in the list at the index of the Hash(data)
array hash_table
. if the data has 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];
a source to share