Friday, 10 November 2017

Hashing in Data Structure

Hash function is a mathematical formula which when applied to a key, produces an integer which can be used as an index for the key in the hash table. Hash table is a data structure in which keys are mapped to array positions by a hash function. The main aim of the hash function is that elements should be relatively, randomly and uniformaily distributed. It produces aunique set of integers within some suitable range in order to reduce the number of collisions. In practice, there is no hash function that eliminates collisions completely. So a good hash function only minimize the number of collisions by spreading the elements uniformaily throughtout the array.

Different hash functions:
1. Division Method
2. Multiplication Method
3. Mid-Square Method
4. Folding Method

Different Collision resolution methods:
1. Open Addressing
   1.1 Linear Probing
   1.2 Quadratic Probing
   1.3 Double Hashing
2. Chaining 
   2.1 Chained Hash Table
   2.2 Bucket Hashing

In the given program, we are using Division method for hashing and linear probing for collision resolution.

Program Code:
#include <iostream>
using namespace std;
// Global declaration of hash key generator function and linear probing function
int htsize;
int hasht(int);
int re_hash_lp(int);

// definition of main function
int main()
{
int key,arr[20],hash[20];
int i,n,k ;
cout<<"Enter the size of the hash table : ";
cin>>htsize;
cout<<"\nEnter the number of elements: ";
cin>>n;
for (i=0;i<htsize;i++)
hash[i]= 0;
cout<<"Enter Elements: ";
for (i=0 ;i<n;i++)
{
cin>>arr[i];
}
for (i=0;i<htsize;i++)
hash[i]=0 ;
for(k=0;k<n;k++)
{
key=arr[k] ;
i = hasht(key);
while (hash[i]!=0)
{
i = re_hash_lp(i);
}
hash[i]=key ;
}
cout<<"\nThe elements in the array are: ";
for (i=0;i<htsize;i++)
{
cout<<"\n Element at position "<<i<<"  "<<hash[i];
return 0;
}

// definition of the hash key function generator or division method for hash key generator
int hasht(int key)
{
 int i ;
 i = key%htsize ;
 return i;
}

// definition of the function which is used for collision resolution or linear probing method
int re_hash_lp(int key)
{
 int i ;
 i = (key+1)%htsize ;
 return i ;
}

The program is tested on www.jdoodle.com
Output:
Enter the size of the hash table : 
Enter the number of elements: Enter Elements: 
The elements in the array are: 
Element at position 0  18
Element at position 1  0
Element at position 2  11
Element at position 3  0
Element at position 4  13
Element at position 5  4
Element at position 6  15
Element at position 7  6
Element at position 8  0


Thanks
Mukesh Rajput

No comments:

Post a Comment

Thanks
Mukesh Rajput