Pages

Saturday 8 September 2012

implementation of hash table in c

#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#define INTCAPACITY 10

struct hashtable
{
    int size;
    int nelements;
    struct listnode **array;
};
struct listnode
{
    int data;
    struct node *next;
};
//creating hashtable

struct hashtable * createhashtbl()
{
    int i,position;
    struct hashtable *htbl;
    struct listnode *tmp;
    htbl=malloc(sizeof(struct hashtable));
    htbl->nelements=0;
    htbl->size=INTCAPACITY;
    htbl->array=malloc(INTCAPACITY*sizeof(struct listnode*));
    for(i=0;i<INTCAPACITY;++i)
    {
        tmp=malloc(sizeof(struct listnode));
        tmp->next=NULL;
        htbl->array[i]=tmp;
        }
        printf("\n hash table created successfully");
        return htbl;
}
//hash function u can use other hashfuntions
int hash(int key,int k)
{
    return key%k;
}
//for each index in hash table im maintaing linked list with sorted order
int listinsert(struct listnode *head,int i)
{
    struct listnode *temp,*q,*t;
    if(head->next==NULL)
    {
    temp=(struct listnode *)malloc(sizeof(struct listnode));
    temp->data=i;
    temp->next=NULL;
    head->next=temp;
     
    }
       
    else
    {
        temp=(struct listnode *)malloc(sizeof(struct listnode));
        temp->data=i;
        temp->next=NULL;
        t=head;
        q=head->next;
        while(i>q->data&&q->next!=NULL)
        {
        t=q;
        q=q->next;
         }
         if(i<q->data)
         {
         t->next=temp;
         temp->next=q;
        }
        else if(q->next==NULL)
        {
            q->next=temp;
            }   
    }
    return 1;
}


//insert in to hashtable

int add(struct hashtable *htbl,int key)
{
    int lf=1,position;
   
    if(htbl->nelements/htbl->size>lf)
    {
        rehash(htbl);
        }
   
   
    position=hash(key,htbl->size);
   
    if(listinsert(htbl->array[position],key))
    {
        htbl->nelements++;
        return 1;
        }
       
        else
        return 0;
}

//rehash when number of elements pointed to index crosses loadfactor we will do rehash       
int rehash(struct hashtable *htbl)
{
    int newsize,i,position;
    struct listnode **newarray;
    struct listnode *tmp,*current;
    newsize=2*htbl->size;
    newarray=malloc(newsize*sizeof(struct listnode *));
    printf("entered to rehash");
    for(i=0;i<newsize;i++)
    {
     tmp=malloc(sizeof(struct listnode));
            tmp->next=NULL;
            newarray[i]=tmp;
            }
    for(i=0;i<htbl->size;i++)
    {
        for(current=htbl->array[i];current->next!=NULL;)
        {
            tmp=current->next;
            position=hash(tmp->data,newsize);
            listinsert(newarray[position],tmp);
            current->next=tmp->next;
            }
        }
        htbl->size=newsize;
        htbl->array=newarray;
return 1;       
     }
//find in likned list this will be used when searching a key in table
int findlink(struct listnode *root,int j)
{
    struct listnode *temp=root->next;
    if(temp==NULL) return 0;
    while(temp->data<j&&temp->next!=NULL)
    {
        temp=temp->next;
        }
    if(temp->data==j)
    return 1;
    else return 0;
}

int find(struct hashtable *htbl,int j)
{
    int k;
    k=hash(j,htbl->size);
    return findlink(htbl->array[k],j);
}   
//remove node
int removenode(struct listnode *root,int j)
{
    struct listnode *temp1,*temp2;
    if(root->next==NULL) return 0;
    temp1=root->next;
    temp2=root;
    while(temp1->next!=NULL&&temp1->data!=j)
    {
        temp2=temp1;
        temp1=temp1->next;
        }
    if(temp1->data==j)
    {
    temp2->next=temp1->next;
    free(temp1);
    return 1;
     }
     else if(temp1->next==NULL)
     return 0;
}
//remove1 function
void remove1(struct hashtable *htbl,int j)
{
    int k,l;
    k=hash(j,htbl->size);
    l=removenode(htbl->array[k],j);
    if(l==1)
    {
        htbl->nelements--;
        printf("\n deleted successfully");
    }
    else printf("\n deletion not successfull given data not present in table");
}

void main()
{
    struct hashtable *htbl;
    int i,j;
    while(1)
    {
        printf("\n ");
    printf("\n enter 1 to initialize hashtable");
    printf("\n enter 2 to add elements to hashtable");
    printf("\n enter 3 to find whether elemnt is exist or not");
    printf("\n enter 4 to delete elment");
    scanf("%d",&i);
    switch(i)
    {
   
    case 1:
            htbl=createhashtbl();
            break;
   
    case 2:
        printf("\n enter value");
        scanf("%d",&j);
        i=add(htbl,j);
        if(i==1)
        printf("\n entered successfully");
        else printf("\n not success");
        break;
       
    case 3:
        printf("\n enter element to find");
        scanf("%d",&j);
        j=find(htbl,j);
        if(j) printf("\n element present in hashtable");
        else  printf("\n element not present in hashtable");
        break;
       
    case 4:
        printf("\n enter elemnt to delete");
        scanf("%d",&j);
        remove1(htbl,j);
        break;   
        }
    }
  }

comment here if this is usefull for anyone

No comments: