DATA STRUCTURES-HASHING-TECHNIQUES

IMPLEMENTATION OF OPEN ADDRESSING:-

#include<stdio.h>
#include<stdlib.h>
typedef int elementtype;
struct Hashtable
{
elementtype *data;
int *occupancy;
int size;
int noofelements;
};
struct Hashtable * rehash(struct Hashtable *H);
int hash(struct Hashtable *H,elementtype key)
{
int index=key%H->size;
return index;
}
int find(struct Hashtable *H,elementtype key)
{
int index=hash(H,key),i=1;
while(H->occupancy[index]==1)
{
if(H->data[index]==key)
return index;
index=(hash(H,key)+i++)%H->size;
}
return -1;
}
void retrieve(struct Hashtable *h,int key)
{
if(key>h->size)
{
printf("Index greater than hash table size!**!");
return;
}
else
{
if(h->occupancy[key]==0)
printf("No element present at index %d",key);
else
printf("Element at index %d is : %d",key,h->data[key]);
}
}
void display(struct Hashtable *H)
{
int i;
printf("\n\t\tHASH TABLE:\n\n");
for(i=0;i<H->size;i++)
{
printf("\t\t%d\t",i);
if(H->occupancy[i]==0)
printf("No data");
else if(H->occupancy[i]==1)
printf("%d",H->data[i]);
printf("\n");
}
}
int isprime(int no)
{
int i=2;
for(;i<=no/2;i++)
{
if(no%i==0)
return 0;
}
return 1;
}
int nextnearestprime(int no)
{
if(no%2==0)
no++;
for(;;no+=2)
{
if(isprime(no)==1)
break;
}
printf("Next prime: %d",no);
return no;
}
struct Hashtable* createhashtable(int size)
{
int i;
struct Hashtable *temp;
temp=(struct Hashtable *)malloc(sizeof(struct Hashtable));
temp->size=size;
temp->noofelements=0;
temp->occupancy=(int *)malloc(size*sizeof(int));
for(i=0;i<size;i++)
temp->occupancy[i]=0;
temp->data=(elementtype *)malloc(size*sizeof(elementtype));
return temp;
}
struct Hashtable* insertintotable(struct Hashtable *H, elementtype key)
{
int percentfilled=H->noofelements*100/H->size;
if(percentfilled< 70)
{
int index=hash(H,key);
int i=1;
while(H->occupancy[index]==1)
index=(hash(H,key)+i++)%H->size;
H->data[index]=key;
H->occupancy[index]=1;
H->noofelements++;
}
else
{
H=rehash(H);
insertintotable(H,key);
}
return H;
}
int deletefromtable(struct Hashtable *H,elementtype key)
{
int index=find(H,key);
if(index==-1)
return 0;
else
{
H->occupancy[index]=0;
index++;
index=index%H->size;
H->noofelements--;
while(H->occupancy[index]==1)
{
insertintotable(H,H->data[index]);
H->occupancy[index]=0;
index++;
index=index%(H->size);
H->noofelements--;
}
return 1;
}
}
struct Hashtable * rehash(struct Hashtable *H)
{
int i=0,count=0;
struct Hashtable *NewTable;
printf("70 percent of hash table size crossed-->Rehashing under process...\n");
NewTable=createhashtable(nextnearestprime(2*H->size));
while(i<H->size)
{
if(H->occupancy[i]==1)
{
insertintotable(NewTable,H->data[i]);
count++;
if(count==H->noofelements)
break;
}
i++;
}
free(H->data);
free(H->occupancy);
free(H);
printf("\nRehashing done!**!\n");
return NewTable;
}
int main()
{
int ch=0,size,data,i;
struct Hashtable *H;
printf("Enter the inital Hashtable size: ");
scanf("%d",&size);
H=createhashtable(nextnearestprime(size));
do
{
printf("\nOPEN ADDRESSING MENU:\n\t1.Insert\n\t2.Find\n\t3.Retrieve\n\t4.Delete\n\t5.Display\n\t6.Exit\nChoice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter the value to be inserted: ");
scanf("%d",&data);
H=insertintotable(H,data);
display(H);
break;
case 2:
printf("Enter the value to be searched: ");
scanf("%d",&data);
i=find(H,data);
if(i==-1)
printf("Value not found!**!");
else
printf("Value found!**!");
break;
case 3:
printf("Enter the index: ");
scanf("%d",&data);
retrieve(H,data);
break;
case 4:
printf("Enter the value to be deleted: ");
scanf("%d",&data);
i=deletefromtable(H,data);
if(i==1)
{
printf("Deletion successful!**!");display(H);
}
else
printf("Error:Value not found in table!**!");
break;
case 5:
display(H);
break;
case 6:
break;
default:
printf("Enter correct menu option!**!");
}
}while(ch!=6);
free(H->data);
free(H->occupancy);
free(H);
return 0;
}


IMPLEMENTATION OF SEPARATE CHAINING:-

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
struct node
{
int data;
struct node * next;
};
struct hash
{
int tablesize;
struct node **thelist;
};
int hashfunc(int key,int tablesize)
{
return(key%tablesize);
}
struct hash * initialize()
{
struct hash * h;
int i;
h=(struct hash *)malloc(sizeof(struct hash));
h->tablesize=10;
h->thelist=(struct node **)malloc(sizeof(struct node)*(h->tablesize));
for(i=0;i<h->tablesize;i++)
{
h->thelist[i]=(struct node *)malloc(sizeof(struct node));
h->thelist[i]->next=NULL;
}
return h;
}
void find(int key,struct hash *h)
{
struct node *pos,*temp;
int i=0,flag=0;
pos=h->thelist[hashfunc(key,h->tablesize)];
temp=pos->next;
while(pos!=NULL)
{
if(pos->data==key)
{
flag=1;break;
}
i++;
pos=pos->next;
}
if(flag==1)
printf("First occurence of the key is found at\n\tCell: %d\n\tLink :%d",hashfunc(key,h->tablesize),i);
else
printf("Key not found!**!");
}
void display(struct hash * h)
{
struct node *temp;
int i;
printf("Contents of the hash table are:\n");
for(i=0;i<h->tablesize;i++)
{
temp=h->thelist[i];
printf("\n%d\t",i);
while(temp->next!=NULL)
{
printf("%d -> ",temp->next->data);
temp=temp->next;
}
printf("\b\b\b   ");
}
}
void insert(int key,struct hash *h)
{
struct node *newcell,*l;
newcell=(struct node *)malloc(sizeof(struct node));
l=h->thelist[hashfunc(key,h->tablesize)];
while(l->next!=NULL)
l=l->next;
newcell->next=NULL;
newcell->data=key;
l->next=newcell;
display(h);
}
int delete(struct hash * h,int key)
{
struct node *l,*temp;
int i=0;
l=h->thelist[hashfunc(key,h->tablesize)];
while(l->next!=NULL)
{
i++;
if(l->data==key)
{
temp=l->next;
l->next=l->next->next;
free(temp);
return 1;
}
l=l->next;
}
return 0;
}
struct hash * makeempty(struct hash *h)
{
int i;
struct node *temp,*t;
for(i=0;i<h->tablesize;i++)
for(temp=h->thelist[i];temp->next!=NULL;)
{
t=temp->next;
temp->next=temp->next->next;
free (t);
}
return h;
}
void dispose(struct hash *h)
{
h=makeempty(h);
free(h);
}
int maxno(struct hash *h)
{
struct node *temp;
int i,max=-99999;
for(i=0;i<h->tablesize;i++)
for(temp=h->thelist[i]->next;temp!=NULL;temp=temp->next)
if(temp->data>max)
max=temp->data;
return max;
}
struct hash * radixsort(struct hash *h)
{
struct hash *h1;
struct node *temp,*l,*newcell;
int key,i,datum,j;
int n=0,max=maxno(h);
if(max==-99999)
{printf("Hash table is empty!**!\n");return h;}
while(max!=0)
{
max=max/10;
n++;
}
for(i=2;i<=n;i++)
{
  h1=initialize();
  for(j=0;j<h->tablesize;j++)
for(temp=h->thelist[j]->next;temp!=NULL;temp=temp->next)
{
datum=temp->data;
key=datum/pow(10,(i-1));
newcell=(struct node *)malloc(sizeof(struct node));
l=h1->thelist[hashfunc(key,h1->tablesize)];
while(l->next!=NULL)
l=l->next;
newcell->next=NULL;
newcell->data=datum;
l->next=newcell;
}
  h=h1;
  printf("\nAfter pass %d: \n",i-1);
  display(h1);
}
return h1;
}
int main()
{
struct hash *h;
int ch,key;
printf("\t\tHASHING BY SEPARATE CHAINING\n");
h=initialize();
while(1)
{
printf("\nMAIN MENU:\n\t1.Insert\n\t2.Locate\n\t3.Display\n\t4.Make empty\n\t5.Radix Sort\n\t6.Dispose hash table and exit\nChoice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:
printf("Enter the key to be inserted: ");
scanf("%d",&key);
insert(key,h);
break;
case 2:
printf("Enter the key to be searched for: ");
scanf("%d",&key);
find(key,h);
break;
case 3:
display(h);
break;
case 4:
makeempty(h);
printf("\b\b\b\b\b\b\b\b\b\b\b\b\bHash table made empty!**!");
break;
case 5:
h=radixsort(h);
printf("After radix sorting: ");
display(h);
break;
case 6:
dispose(h);
printf("\b\b\b\b\b\b\b\b\b\b\b\b\b ");
return 1;
default:printf("Enter correct menu option!**!");
}
}
return 0;
}