HASHING IMPLEMENTATION

HASHING IMPLEMENTATION

Hashing: It is a technique in which we decide the index/location of an element/key using a HASHING FUNCTION for storing the element.

Example:Suppose your hashing function is key mod 10 (key%10) and if you have key as 34 then 34%10=4 .Hence 34 will be stored at 4th location.And generally the number by which you divide the key is the table length i.e. 10 here.

Some key points about hashing:

• It is also used in database management systems.
• It gives a faster storage and retrieval of data.
• There are various hashing techniques.Some of them are:

1. Division methods
2. Multiplicative methods
3. Digit folding method
4. Mid-square method
5. Digit analysis method

• Suppose you have to store 34 and 64 then both have to be placed at the 4th location.But it is not possible.This is called COLLISION.
• Collision should be as minimum as possible.This is the property of a good hashing function.
• The techniques used to resolve collisions are known as collision handling techniques.Some are:

1. Linear probing
2. Chaining with replacement
3. Chaining without replacement.
4. Extensible hashing  

The following code implements hashing:

/*************************************************************

Program to implement dictionary operations using hashing

*************************************************************/

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

#define MAX 10

class HashTab

{

 private:

     struct DCT{

int k;

int val;

}a[MAX];

 public:

 int hash(int);

 void init();

 void insert(int,int,int);

 void display();

 void size();

 void search(int);

};

void HashTab::init()

{

 for(int i=0;i<MAX;i++)

 {

a[i].k= -1;

a[i].val=-1;

 }

}

int HashTab::hash(int num)

{

 int Hkey;

 Hkey=num%10;

 return Hkey;

}

void HashTab::insert(int index,int key,int value)

{

 int flag,i,count=0;

 flag=0;

 if(a[index].k==-1)/*if the location indicated by hash key is empty*/

 {

a[index].k=key;

a[index].val=value;

 }

 else

 {

i=0;

while(i<MAX)

{

if(a[i].k!= -1)

count++;

i++;

}

if(count==MAX)         /*checking for the hash full*/

{

cout<<"\nHash Table Is Full";

}

for(i=index+1;i<MAX;i++)/*moving linearly down*/

if(a[i].k== -1)     /*searching for empty location*/

{

a[i].k=key;

a[i].val=value;

/*placing the number at empty location*/

flag=1;

break;

}

/*From key position to the end of array we have searched empty location and now we want to check empty location in the upper part of the array*/

for(i=0;i<index&&flag==0;i++)/*array from 0th to keyth location will be scanned*/

if(a[i].k== -1)

{

a[i].k=key;

a[i].val=value;

flag=1;

break;

}

  } /*outer else*/

} /*end*/

void HashTab::display()

{

 int i;

 cout<<"\n The Hash Table is...\n";

 cout<<"\n--------------------------------";

 for(i=0;i<MAX;i++)

{

cout<<"\n  "<<i<<"  "<<a[i].k<<"  "<<a[i].val;

}

 cout<<"\n--------------------------------";

}

void HashTab::size()

{

 int len=0,i;

 for(i=0;i<MAX;i++)

 {

if(a[i].k!=-1)

len++;

 }

 cout<<"\n The size of dictionary is ";

 cout<<len;

}

void HashTab::search(int search_key)

{

 int i,j;

i=hash(search_key);

if(a[i].k==search_key)

{

cout<<"\n The Record is present at location  "<<i;

return;

}

if(a[i].k!=search_key)

{

//searching from hash key to end of hash table

for(j=i;j<MAX;j++)

{

if(a[j].k==search_key)

{

cout<<"\n The Record is present at location  "<<j;

return;

}

}

//searching from beginning of hash table upto hash key

for(j=0;j<i;j++)

{

if(a[j].k==search_key)

{

cout<<"\n The Record is present at location "<<j;

return;

}

}

}

else

cout<<"\n The Record is not present in the hash table";

}

void main()

{

 int key,value,Hkey,search_key;

 char ans;

 HashTab obj;

 clrscr();

 cout<<"\nDictionary Functions using Hashing";

 obj.init();

 do

 {

cout<<"\n Enter The key";

cin>>key;

cout<<"\n Enter The Value";

cin>>value;

Hkey=obj.hash(key);/*returns hash key*/

obj.insert(Hkey,key,value);/*collision handled by linear probing*/

cout<<"\n Do U Wish To Continue?(y/n)";

ans=getche();

 }while(ans=='y');

 obj.display();/*displays hash table*/

 obj.size();

 cout<<"\n Enter the key for searching the record";

 cin>>search_key;

 obj.search(search_key);

 getch();

}

I hope it is clear.If you have any doubt feel free to ask.Good day.