LINEAR PROBING - COLLISION RESOLVING TECHNIQUE

LINEAR PROBING

Last Updated On: 12th Dec 2015

Linear Probing

When collision occurs i.e. when two records demand for the same location in the hash table, then the collision can be solved by placing second record linearly down wherever the empty location is found.

Before we move further, keep in mind that it is always good to have a decent Hash function which properly distributes the elements in the hash table. The following rules can be kept in mind for choosing a good Hash Function

• The hash function should be simple to compute.
• Number of collisions should be less while placing the record in the hash table. Ideally no collision should occur. Such a function is called perfect hash function.
• Hash function should produce such keys which will get distributed uniformly over an array.
• The hash function should depend on every bit of the key. Thus the hash function that simply extracts the portion of a key is not suitable.

If collision occurs, then it should be handled by applying some techniques, such a technique is called collision handling techniques. Linear Probing is one of them. Let's discuss it with an example.

Let us consider the following Hash Table ( Hash Function: Number % 10)

Explanation

In the hash table given above, if the first number which is to be placed is 131 then 131 % 10 = 1 i.e. remainder is 1 so hash key = 1. That means we are supposed to place the record at index 1. Next number is 21 which also gives hash key = 1 as 21 % 10 = 1. But 131 is already placed at index 1. That means collision has occurred. We will now apply linear probing. In this method, we will search the place for number 21 from location of 131. In this case we can place the number 21 at index 2. Then if 31 has to be stored, it can be stored at index 3. Similarly, 61 can be stored at 6 because number 4 and 5 are stored before 61. Because of this technique, the searching becomes efficient, as we have to search only limited list to obtain the desired number.

Now let's see the code in action:

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

Program to create hash table and to handle the collision using linear

probing.In this Program hash function is (number%10)

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

#include<iostream.h>

#include<conio.h>

#include<stdlib.h>

#define MAX 10

class Hash

{

 private:

  int a[MAX];

 public:

 Hash();

 int create(int);

 void linear_prob(int,int),display();

};

/*

--------------------------------------------------------------------------

The constructor defined

--------------------------------------------------------------------------

*/

Hash::Hash()

{

 int i;

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

  a[i]=-1;

}


/*

--------------------------------------------------------------------------

The create function is for generating the hash key

Input:the num means the number which we want to place in the hash table

Output:returns the hash key

Calls:none

Called By:main

--------------------------------------------------------------------------

*/

int Hash::create(int num)

{

 int key;

 key=num%10;

 return key;

}

/*------------------------------------------------------------------------

The linear_prob function handles the collision

Input:the num,hash key and hash table by array a[]

Output:none

Calls:none

Called By:main

--------------------------------------------------------------------------

*/

void Hash::linear_prob(int key,int num)

{

 int flag,i,count=0;

 flag=0;

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

  a[key]=num;//place the number in the hash table

 else

 {

  i=0;

  while(i<MAX)

  {

 if(a[i]!=-1)

  count++;

 i++;

  }

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

 {

 cout<<"\nHash Table Is Full Hence "<<num<<" Can not Be Inserted";

 display();

 getch();

 exit(1);

 }

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

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

 {

  a[i]=num;  //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<key&&flag==0;i++)//array from 0th to keyth loaction will be scanned

 if(a[i]==-1)

 {

  a[i]=num;

  flag=1;

  break;

 }

 } //outer else

}//end


/*

--------------------------------------------------------------------------

The display function displays the hash table

Output:none

Calls:none

Called By:main

--------------------------------------------------------------------------

*/

void Hash::display()

{

 int i;

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

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

  cout<<"\n  "<<i<<"  "<<a[i];

}


/*

--------------------------------------------------------------------------

The main function

Calls:create,linear_prob,display

Called By:O.S.

--------------------------------------------------------------------------

*/

void main()

{

 int num,key;

 char ans;

 Hash h;

 clrscr();

 cout<<"\nCollision Handling By Linear Probing";

 do

 {

  cout<<"\n Enter The Number";

  cin>>num;

  key=h.create(num);//returns hash key

  h.linear_prob(key,num);//collision handled by linear probing

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

  ans=getche();

 }while(ans=='y');

 h.display();//displays hash table

 getch();

}

We hope you liked the article. Let us know your feedback or any other queries. Cheers!!