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;
}

Hashing Program using Division Method and collision resolution by Chaining

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

// 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;
}

Bit Flooding outward and backward of a set Bit...

FillBits:-

Consider a new bitwise binary operator that we will denote as x $ y. The result of this
operator is that the set bits of x "flood outwards" y bits to both the left and the right.
More precisely, the i-th bit (the least significant bit is considered to be the 0-th) of x $ y
will be 1 if and only if x has any bit whose value is 1 and whose position differs by at most
y from i (it can differ in either direction).


Write a program that given unsigned ints x and y, computes x $ y.


Example Inputs:
8 2
8 4
17 1


Outputs (respectively):
62
255
59


Explanation:
In the first case, 8 is 0000..00001000 in binary. The operation causes the only set bit in
the number to spread 2 positions in each direction, with a final result of 111110 (original
bit underlined), which is 62 in decimal.


In the second case, we spread the same bit 4 positions in each direction. This results in
4 1s to the left of the original bit's position. All 3 available positions to the right of the

original bit's position are filled (a 4th would normally be filled, but we have reached the
end of the number). The final number is 11111111, the value of which is 255.

In the third case, 17 is 10001 in binary, and spreading the 1s in each direction by 1 gives
111011, which is 59 in decimal.

With complexity:-K

#include<iostream>
using namespace std;
 
unsigned int FillBits(unsigned int x,unsigned int y)
{
    int i=0;
unsigned int a=x,b=x; 
while(y--)
{
a=a*2;   
b=b/2;
x=x|a|b;
}
 
return x;
}
int main(void)
{
unsigned int n,m;
cin>>n>>m;
cout<<FillBits(n,m);
return 0;
}

4 solution with complexity K
#include <iostream>
 
using namespace std;
 
unsigned int FillBits(unsigned int n,unsigned int y)
{
unsigned int k=0,m=1,p=0,r=0;
k=~(~k<<(2*y+1));
while(p<32)
{
  
  if(n&m)
  {
     if(p<y)
     {
         r=r|k>>(y-p);
         m=m<<1;
         p++;
     }
     else
     {
         r=r|k<<(p-y);
         m=m<<1;
         p=p+1;
     }
  }
  else
  {
  m<<=1;      
   p++;
  }
 
 
}
return r;
}
 
int main()
{  unsigned int x,y;
   cin>>x>>y;
   cout <<FillBits(x,y)<< endl; 
   
   return 0;
}

RangeOperation on A(m, n) = m & (m+1) & ... & (n-1) & n,

 RangeOperation

Let us define A(m, n) = m & (m+1) & ... & (n-1) & n, where & is the bitwise AND operation.
Write a program that, given 64-bit unsigned longs m and n, computes A(m, n).


Example Inputs:
49 54
2 2
2 3


Outputs (respectively):
48
2
2


Explanation:
A(49, 54)=49&50 &51&52&53&54= 48
A(2, 2) =2.If m= n,A(m, n)=m =n.
A(2, 3) =2& 3 =2

Let k be the bit width (maximum number of bits) of the primitive.
Easy: O(n -m) time. Consider that since m and n can be any 64-bit numbers, this could be
huge.
Moderate-Hard: O(k) time.
Hard: O(log(k)) time.

1.Complexity O(k)

#include <iostream>
 
using namespace std;
 
unsigned long int RangeOperation(unsigned long int n,unsigned long int m)
{
unsigned long int temp,k=~0,d;
d=m-n;
while(d)
{
k<<=1;
n=n&m&k;
d>>=1;
 
}
return n;
}
int main()
{  unsigned long int n,m;
     cin>>n>>m;
   cout <<RangeOperation(n,m)<< endl; 
   
   return 0;
}

other way of doing of the above complexity

//RangeOpearation with K complexity
#include <iostream>
 
using namespace std;
 
int MaxBit(unsigned long int n)
{
unsigned long int k=1;int p,count=0,i=0;
while(i<32)
{
    
if(k&n)
p=count;
count++;
k<<=1;
i++;
}
return p;
}
 
unsigned long int RangeOperation(unsigned long int n,unsigned long int m)
{
unsigned long int p,q,k,t=0;    
p=MaxBit(n);
q=MaxBit(m);
if(p!=q)
return 0;
k=MaxBit(m-n);
 
k=~t<<k;
return m&n&k;
}
 
int main()
{
     
    unsigned long int n,m;
     cin>>n>>m;
     cout <<"value is: "<< RangeOperation(n,m) << endl; 
     return 0;
}


2. With complexity O(logK)


//RangeOperation complexity logk.
 
#include <iostream>
 
using namespace std;
 
int MaxBit(unsigned long int n)
{
unsigned long int p=1,k=0;int left=0,right=31,mid;
 
 
while(n)
{
k=0,p=1;    
mid=(left+right)/2;
k=~(~k<<mid+1);
p=p<<mid;
if(n<=k && n&p)
{
return mid+1;    
}
else if(n>k)
{
left=mid;    
}
else
 right=mid;
 
}
return 0;
}
 
unsigned long int RangeOperation(unsigned long int n,unsigned long int m)
{
unsigned long int p,q,k,t=0;    
p=MaxBit(n);
q=MaxBit(m);
if(p!=q)
return 0;
k=MaxBit(m-n);
 
k=~t<<k;
return m&n&k;
}
 
int main()
{
     
    unsigned long int n,m;
     cin>>n>>m;
     cout <<"value is: "<< RangeOperation(n,m) << endl; 
     return 0;
}