42. HASHING TECHNIQUE IN C++

//HASHING TECHNIQUE

#include<iostream.h>
#include<iomanip.h>

struct listnode;
typedef struct listnode *position;
typedef position list;
struct hashtbl;
typedef struct hashtbl *hashtable;

hashtable initialize(int tablesize);
void destroytable(hashtable h);
position find(int key, hashtable h);
void insert(int key,hashtable h);
int retrieve(position p);
int hash(int key, int tablesize);

struct listnode
{
int element;
position next;
};

struct hashtbl
{
int tablesize;
list *thelists;
};

int hash(int key, int tablesize)
{
return key % tablesize;
}

position find(int key, hashtable h)
{
position p;
list l;
l=h->thelists[hash(key,h->tablesize)];
p=l->next;
while(p!=NULL && p->element !=key)
p=p->next;
return p;
}

position findprevious(int key, hashtable h)
{
position p;
p=h->thelists[hash(key,h->tablesize)];
while(p!=NULL && p->next->element!=key)
p=p->next;
return p;
}

/*Roy Antony Arnold – Infant Jesus College of Engineering*/

void insert(int key, hashtable h)
{
position pos, newcell;
list l;
pos=find(key,h);
if(pos==NULL)
{
newcell = new listnode;
if(newcell!=NULL)
{
l=h->thelists[hash(key,h->tablesize)];
newcell->next=l->next;
newcell->element=key;
l->next=newcell;
}
}
else
cout<<”\nElement is already available in the Table..\n”;
}

void del(int key, hashtable h)
{
position pos, oldcell;
list l;
pos=findprevious(key,h);
if(pos->next!=NULL)
{
oldcell=pos->next;
pos->next=oldcell->next;
delete oldcell;
}
else
cout<<”\nElement is not found in the Hash Table…\n”;
}

hashtable initialize(int tablesize)
{
hashtable h;
int i;
if(tablesize<1)
{
cout<<”Table Size is too small\n”;
return NULL;
}
h = new hashtbl;
if(h!=NULL)
{
h->tablesize= tablesize;
h->thelists= new list[h->tablesize];
for(i=0; i<h->tablesize; i++)
{
h->thelists[i]=new listnode;
h->thelists[i]->next = NULL;
}
}
return h;
}

/*Roy Antony Arnold – Infant Jesus College of Engineering*/

void display(hashtable h)
{
int i;
position p;
cout<<”\nThe Hash Table is…\n”;
for(i=0; i<h->tablesize; i++)
{
p=h->thelists[i]->next;
cout<<”——-\n”<<”|”<<setw(3)<<i<<”  |->”;
while(p!=NULL)
{
cout<<p->element<<”->”;
p=p->next;
}
cout<<”NULL\n”;
}
cout<<”——-”;
}

void main()
{
int size,ch,ele,child;
hashtable h;
cout<<”\nWorking with Hashing Techniques – Separate Chaining Method\n”;
cout<<”\nEnter the Size of the Hash Table…”;
cin>>size;
h = initialize(size);
do
{
cout<<”\n\t\tMenu\n”;
cout<<”\n1. Insert”;
cout<<”\n2. Delete”;
cout<<”\n3. Display”;
cout<<”\n4. Find”;
cout<<”\n5. Exit”;
cout<<”\nEnter Your Choice…”;
cin>>ch;
switch(ch)
{
case 1:
cout<<”\nEnter an Element…”;
cin>>ele;
insert(ele, h);
break;
case 2:
cout<<”\nEnter an Element…”;
cin>>ele;
del(ele,h);
break;
case 3:
display(h);
break;
case 4:
position p;
cout<<”\nEnter an Element…”;
cin>>ele;
if(find(ele, h)!=NULL)
cout<<”The Element is found  in the table\n”;
else
cout<<”The Element is not  found in the table\n”;
break;
default:
cout<<”\n Exit “;
}
}while(ch<5);
}