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.).
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