Sunday, July 28, 2013

Hashing Program using Division Method and collision resolution by Chaining

It's  Hashing Implementation for long integers, i have used Division method to fix the slot's and chaining to resolve the collision.
Division Method:-
  To efficiently implement(for uniform hashing) division method in a program, there is some fix rule
Note- choose no. of slots (m) , a prime not too close to an exact power of 2, is often a good choice for m.
 i.e h(k)=k mod 701. where as k is key and m=701 ( a prime not close to a power of any 2.).

// Hasihng implementation
#include<stdio.h>
#include<stdlib.h>
#define Max 15
struct Hash
{
long     int data;
struct Hash *next;
};
 
void LookUp(long int N,struct Hash arr[])
{
if(arr[N%Max].data>0)
{       
struct Hash *ptr;
ptr=&arr[N%Max];
while(ptr->next!=NULL)
ptr=ptr->next;
struct Hash *temp;
temp=(struct Hash*)malloc(sizeof(struct Hash));
temp->data=N;
temp->next=NULL;
ptr->next=temp;
}
else
  arr[N%Max].data=N;
}
 
 
// Function for searching the data goes here
int Search(long int N,struct Hash arr[])
{
struct Hash *ptr;
ptr=&arr[N%Max];
while(ptr!=NULL&&ptr->data!=N)
ptr=ptr->next;
if(ptr!=NULL&&ptr->data==N)
return 1;
return 0;
}
//Main goes here
int main(void)
{  
struct Hash arr[Max];
int i=0;long int N;
while(i<Max)
{
arr[i].data=0;
arr[i++].next=NULL;
}
i=0;
while(i++<10)
{
 scanf("%d",&N);;
LookUp(N,arr);
}
 
printf("Table is like this ... Inside\n");
i=0;
struct Hash *temp;
while(i<Max)
{
printf("\n%d ",arr[i].data);
temp=&arr[i];
while(temp->next!=NULL)  
{
temp=temp->next;
printf("%d ",temp->data);
 
}
i++;
}
 
printf("\nEnter the integer to be searched\n"); 
i=0;
while(i++<4)
{
scanf("%ld",&N);
Search(N,arr)?printf("%d Exist\n",N):printf("%d Do not exist\n",N);
}
return 0;
}

No comments:

Post a Comment