Answer to Implement hash search in C

Here we use shift- folding as the hashing function and chaining for overflow handling.


#include <stdio.h>
#include <string.h>
#include <malloc.h>

#define MAXLEN 80
#define HASHSIZE 23             // some prime val.
#define SHIFTBY 3               // each group size in hashing.

typedef struct node node;
typedef char *type;

struct node {
   int val;
   char *key;
   node *next;
};
node *h[HASHSIZE];


int hGetIndex(char *key) {
   /*
    * returns index into hashtable applying hash function.
    * uses shift-folding followed by mod function for hashing.
    */
   int i, n, finaln=0;
   char *keyptr;
   for(keyptr=key; *keyptr; finaln+=n)
       for(i=0, n=0; i<SHIFTBY && *keyptr; ++i, ++keyptr)
              n = n*10 + *keyptr;
   finaln %= HASHSIZE;

   return finaln;
}

void hInsert( char *key, int val) {
    /*
     * insert s in hashtable h.
     * use shift-folding followed by mod function for hashing.
     * does NOT check for duplicate insertion.
     */
   node *ptr = (node *)malloc(sizeof(node));
   int index = hGetIndex(key);

   ptr->key = strdup(key);
   ptr->val = val;
   ptr->next = h[index];

   h[index] = ptr;
   printf("h[%d] = %s.\n", index, key);
}

int hGetVal( char *key) {
   /*
    * returns val corresponding to key if present in h else −1.
    */
   node *ptr;
    ptr=h[hGetIndex(key)];
   while (1)
   {
   if (ptr==NULL || strcmp(ptr->key, key)==0)
       break;
    ptr=ptr->next;
    }
   if(ptr)
       return ptr->val;
   return -1;
}

void printHash() {
    /*
     * print the hashtable rowwise.
     */
   int i;
   node *ptr;

   for(i=0; i<HASHSIZE; ++i) {
       printf("%d: ", i);
       for(ptr=h[i]; ptr; ptr=ptr->next)
              printf("%s=%d ", ptr->key, ptr->val);
       printf("\n");
   }
}

int main() {
    char s[MAXLEN];
    int i = 0;
    for (i=0;i<HASHSIZE;i++)
        h[i]=NULL;
    i=0;
    printf("Enter the string to be hashed: ");
    gets(s);

    while(*s) {
       hInsert( s, i++);
       printf("Enter the string to be hashed(enter to end): ");
       gets(s);
    }
    printHash();
    printf("Enter the string to be searched: ");
    gets(s);

    while(*s) {
        i=hGetVal(s);
        if (i!=-1)
               printf("%s was inserted at number %d.\n", s,i);
    else
        printf("%s was not inserted in the hashtable",s);
       
       printf("\nEnter the string to be searched(enter to end): ");
       gets(s);
    }

    return 0;
}