Symbol table implementation using hash table in C

Question

I am trying to implement a simple symbol table that stores the strings in a hash table according to their hash values. The hash table in my program is an array of pointers to linked lists. we have 6 linked lists corresponding to each hash value.

The problem is that though the program runs, it replaces the old strings with the new string in each iteration.

my code is..

struct node{
    char *string;
    struct node *next;
};
struct node *hashtable[6];

int calchash(char *arr);
main()
    {
    char *line, a='n';
    int val, i;
            do{
            printf("Enter string:\n");
            scanf("%s", line);
            struct node *current;
            struct node *q= (struct node*)malloc(sizeof(struct node));
            q->string = line;
            q->next = NULL;
            val= calchash(line);
            if(hashtable[val] == NULL)
                    {
                    hashtable[val] = q;
                    current =q;}
            else{
                    current->next = q;
                    current = q;
                    }
            printf("Node created\n");
    for(i=0; i<6; i++)
            { printf("Hash value %d :\n", i);
            if(hashtable[i]==NULL)
                    {printf("No STRINGS!\n\n");}
            else
                    {struct node *t = hashtable[i];
                    while(t != NULL)
                            {printf("%s \n", t->string);
                            t = t->next;}
                    printf("\n\n");
                   }
            }

    printf("CONTINUE(y/n):\n");
    scanf(" %c", &a);
    }while(a!='n');
    }

int calchash(char *arr)
    {int i=0, ascii;
    int sum=0;
    while(arr[i] != '\0')
            {ascii = arr[i];
            if(ascii>=48 && ascii<=57)
                    {
                    sum+= 2*ascii;}
            else
                    {sum=sum+ ascii;}
            i++;
            }
    return ((sum*17+5)%6);
    }

And the output is: Enter string: az9

Node created

Hash value 0 : No STRINGS!

Hash value 1 : No STRINGS!

Hash value 2 : az9

Hash value 3 : No STRINGS!

Hash value 4 : No STRINGS!

Hash value 5 : No STRINGS!

CONTINUE(y/n): y

Enter string: Az9

Node created

Hash value 0 : No STRINGS!

Hash value 1 : No STRINGS!

Hash value 2 : Az9

Hash value 3 : No STRINGS!

Hash value 4 : Az9

Hash value 5 : No STRINGS!

CONTINUE(y/n): n

Can someone please tell me what changes are needed so as to retain the previous az9 string under hash value 2???

You know that superfluous Casts are bad form and tend to muzzle the compiler? Never cast the return value of malloc(). How about trying to compile with all warnings enabled, and actually fixing the warnings properly? — Deduplicator
– Deduplicator, Commented Apr 2, 2014 at 16:46

Deduplicator · Accepted Answer · 2014-04-02 16:43:37Z

1

if(hashtable[val] == NULL) {
    hashtable[val] = q;
    current =q;
} else {
    current->next = q;
    current = q;
}

should be replaced with:

q->next = hashtable[val];
hashtable[val] = q;
// no need for current

Also, writing through any uninitialised pointer is UB, please allocate sufficient space first. Anything might happen...

answered Apr 2, 2014 at 16:43

Deduplicator

46k7 gold badges73 silver badges125 bronze badges

Sign up to request clarification or add additional context in comments.

Comments

pat · Accepted Answer · 2014-04-02 16:53:50Z

1

How does this not crash immediately? Neither line nor hashtable are initialized.

You will need to make a copy of the string to go into each hash node, probably with strdup. Currently, all of the nodes point to the same string buffer as line, so when you read a new string into line, all of the nodes will see it. This is why you must duplicate the string for each node. I wonder where the buffer ended up though, since you never initialized line...

Also, what is current? It is local to the loop, and appears unnecessary. You should just chain new nodes onto the head of the bucket, so you don't need to check if the bucket is empty.

The insert also does not check if the string is already present, so you will insert duplicates.

edited Apr 2, 2014 at 16:53

answered Apr 2, 2014 at 16:43

pat

12.8k1 gold badge25 silver badges53 bronze badges

Collectives™ on Stack Overflow

Symbol table implementation using hash table in C

2 Answers 2

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related