Open Addressing concept of hashing to avoid collision.

Hashing implementation using Open Addressing

Open Addressing is way to not to use chaining to resolve collision, it will try to find a place inside the hash table for the element.This can be done the possible three ways

1.Linear Probing.. Try to search next empty slot to fill by the elements.

like h(k)=h(k)+i mod m(size of the table)

2.Quadratic Probing..Try to search quadratically.like h(k)=h(k)+c*i+c*i^2 mod m (size of the table).

3.Double hashing... Uses double hashing like h(k)=h(k)+i*H(k)mod m(size of table)

   In the below program i have used all the above method, you can active by removing double slash(//) and run it...while you do activate one deactivate others two.

//Hashing by using concepts of Open addressing....a various way implementation

#include <iostream>
#define Max 10
using namespace std;
int j=0;
//Linear Probing.... Remember it does suffer from primary clustering
void LinearProbing(unsigned long N,int Table[],int i)
{
if(Table[(N+i)%Max])
{
LinearProbing(N,Table,++i);
}
else
Table[(N+i)%Max]=N;
}
 
//Quadratic Probing .... Remember it does suffer from secondary clustering
void QuadraticProbing(unsigned long N,int Table[],int i)
{
 
if(j==Max)
{
cout<<"No empty place there...Sorry!!!\n";
return;
}
j++;
int p=0;
p=i+i*i;
if(Table[(N+p)%Max])
QuadraticProbing(N,Table,++i);
else
Table[(N+p)%Max]=N;
}
//Double Hashing.... It can have uniform hashing uses two hash functions
void DoubleHashing(unsigned long N,int Table[],int i)
{
unsigned int key=701%Max;
if(j==Max)
{
    cout<<"No empty slot exist... Sorry !!!\n";
    return;
}
j++;
if(Table[(N+i*key)%Max])
DoubleHashing(N,Table,++i);
else
Table[(N+i*key)%Max]=N;
}
//Insertion of data goes here.....Uses Open addressing approaches to get the slot
void Insert(unsigned long N,int Table[])
{
if(Table[N%Max])
{
//LinearProbing(N,Table,1);
//QuadraticProbing(N,Table,1);
DoubleHashing(N,Table,1);
j=0;
}
else
Table[N%Max]=N;
}    
//Searching through linear probe
int LinearProbSearch(unsigned long N,int Table[],int i)
{
if(j==Max)   
{
return 0;    
}
j++;
if(Table[(N+i)%Max]==N)
return 1;
else
return LinearProbSearch(N,Table,++i);
}
//Search through quadratic probe
int QuadraticProbSearch(unsigned long N,int Table[],int i)
{
unsigned long p=i+i*i;    
if(j==Max)
{
cout<<"Not Found\n";
return 0;
}
j++;
if(Table[(N+p)%Max]==N)
return 1;
else
return QuadraticProbSearch(N,Table,++i);
}
//Searchthrough double hashing
int DoubleHashingSearch(unsigned long int N,int Table[],int i)
{
unsigned long int  k=701%Max;
if(j==Max)
return 0;
j++;
if(Table[(N+i*k)%Max]==N)
return 1;
else
return DoubleHashingSearch(N,Table,++i);
}
 
int Search(unsigned long N,int Table[])
{
if(Table[N%Max]==N)
return 1;
else
{
//return LinearProbSearch(N,Table,1);
//return QuadraticProbSearch(N,Table,1);
return DoubleHashingSearch(N,Table,1);
}
return 0;
}
 
int main()
{
int Table[Max]={0};
unsigned long N;
int i=0;
while(i<10)
{  cin>>N;
 Insert(N,Table);
i++;
}
i=0;
while(i<Max)
cout<<Table[i++]<<endl;
i=0;
cout<<"Enter the integer to be searched\n";
while(i<2)
{
j=0;    
cin>>N;    
Search(N,Table)?cout<<N<<" Exist\n":cout<<N<<" Do not Exist\n";
i++;
} 
return 0;
}