In this instructional exercise, you will find out about Hashing in C and C++ with the program example.
You will likewise learn different ideas of hashing like a hash table, hash work, and so forth.
Hashing in Data Structure
Looking is the prevailing activity on any information structure. A large portion of the cases for embeddings, erasing,
refreshing all tasks required looking through first. So looking through the activity of specific information structure decides it’s time
multifaceted nature. In the event that we take any information structure, the best time unpredictability for looking is O (log n) in AVL
tree and sorted exhibit as it were. The majority of the cases it will take O (n) time. To take care of this looking through issue hashing idea
presented which will take O (1) time for looking. It’s a steady time.
Hash Table and Hash Function
Prior when this idea acquainted programmers utilized with make “Direct address table”.
Direct address table methods, when we have “n” number of one of a kind keys we make a
variety of length “n” and addition component “I” at the ith list of the exhibit. That cluster is called a Hash Table.
Be that as it may, because of this strategy even we have 10 components of each range 1 need, we should make a table of size 1
need for just 10 components. Which will be a misuse of memory.
To maintain a strategic distance from this issue we fix the size of hash table (cluster) and guide our components into that table utilizing a capacity,
called Hash work. This capacity chooses where to place a given component into that table.
In the event that we need to look through additionally first apply hash capacity choose whether the component present in the hash table or not.
example
We have numbers from 1 to 100 and a hash table of size 10. Hash capacity is mod 10. That implies number 23 will be mapped
to (23 mod 10 = 3) third file of the hash table.
In any case, the issue is if components (for instance) 2, 12, 22, 32, components should be embedded then they attempt to embed at list 2 in
particular. This issue is called Collision. To tackle this impact issue we utilize various kinds of hash work procedures. Those are given beneath.
Affixing
Open tending to
Direct probing
Quadratic probing
Twofold hashing
These likewise called crash resolution systems.
Binding
In hash table, as opposed to placing one component in the record we keep up a connected rundown.
At the point when the crash happened, we place that component in comparing connected rundown.
Here some space is squandered on account of pointers.
Open Addressing
In the event that on the off chance that we have crash we again ascertain the hash worth utilizing comparing hash work. Yet, this time we do some minor adjustments to that information. This procedure of scanning for void space to embed component in called Probing.
Probing hash capacity is: h (k, I)
here k is the key esteem which is to be embedded. Furthermore, I is number of impact with that component.
example: If we are embeddings 2, we discover its hash worth utilizing h (2, 0) since it’s first crash. Assume the appropriate response (list) to this capacity record previously involved we again need to apply h (2, 1) to hash work.
Straight Probing
Give hash a chance to capacity is h, the hash table contains 0 to n-1 spaces.
Presently we need to embed a component k. Apply h (k). On the off chance that it results “x” and the file “x” as of now contain a worth then we again apply hash work that h (k, 1) this equivalents to (h (k) + 1) mod n.
General structure: h1 (k, j) = (h (k) + j) mod n
example: Let hash table of size 5 which has capacity is mod 5 has just filled at positions 0, 2, 3.
Presently new component 10 will attempt to embed. 10 mod 5 = 0. Be that as it may, list 0 previously involved. So it checks (tests) next (file 1) position. So 10 will embed at file 1.
Presently component 11 will attempt to embed. 11 mod 5 = 1. Be that as it may, file 1 previously involved, check file 2 it additionally involved (information given), 3 likewise involved. So it will embed at list 4 which is unfilled.
We can see that it directly checking for next void position. So it’s called direct probing.
Issues with direct probing:
Essential bunching: There is an opportunity that persistent cells involved, at that point the likelihood of new component addition will get diminished. This issue is called essential grouping
Optional grouping: If two components get the same esteem from the outset hash work, they pursue the same test succession.
Quadratic Probing
It is same as direct probing. In any case, when a crash happens we utilize diverse capacity.
On the off chance that crash happened that component attempt to involve at quadratic separation rather than straight separation.
Because of this “Essential bunching” will be diminished. In any case, optional grouping won’t be dispensed with.
Twofold Hashing
Here we use two hash capacities.
h1 (k) = (h1 (k) + I h2 (k)) mod n. Here h1 and h2 are two hash capacities.
Here the following prob position will rely upon two capacities h1 and h2 too.
Points of interest by this technique are there is zero chance of essential bunching. And furthermore, Secondary grouping additionally wiped out.
Affixing versus Open Addressing
| Chaining | Open Addressing |
| Elements can be stored outside of the table | In open addressing elements should be stored inside the table only |
| In chaining at any time the number of elements in the hash table may greater than the size of the hash table | In open addressing the number of elements present in the hash table will not exceed the number of indices in the hash table. |
| In case of deletion, chaining is the best method | If deletion is not required. Only inserting and searching is required open addressing is better |
| Chaining requires more space | Open addressing requires less space than chaining. |
The following is the usage of hashing or hash table in C.
Program
#include<stdio.h>
#include<limits.h>
/*
This is code for linear probing in open addressing. If you want to do quadratic probing and double hashing which are also
open addressing methods in this code when I used hash function that (pos+1)%hFn in that place just replace with another function.
*/
void insert(int ary[],int hFn, int size){
int element,pos,n=0;
printf("Enter key element to insert\n");
scanf("%d",&element);
pos = element%hFn;
while(ary[pos]!= INT_MIN) { // INT_MIN and INT_MAX indicates that cell is empty. So if cell is empty loop will break and goto bottom of the loop to insert element
if(ary[pos]== INT_MAX)
break;
pos = (pos+1)%hFn;
n++;
if(n==size)
break; // If table is full we should break, if not check this, loop will go to infinite loop.
}
if(n==size)
printf("Hash table was full of elements\nNo Place to insert this element\n\n");
else
ary[pos] = element; //Inserting element
}
void delete(int ary[],int hFn,int size){
/*
very careful observation required while deleting. To understand code of this delete function see the note at end of the program
*/
int element,n=0,pos;
printf("Enter element to delete\n");
scanf("%d",&element);
pos = element%hFn;
while(n++ != size){
if(ary[pos]==INT_MIN){
printf("Element not found in hash table\n");
break;
}
else if(ary[pos]==element){
ary[pos]=INT_MAX;
printf("Element deleted\n\n");
break;
}
else{
pos = (pos+1) % hFn;
}
}
if(--n==size)
printf("Element not found in hash table\n");
}
void search(int ary[],int hFn,int size){
int element,pos,n=0;
printf("Enter element you want to search\n");
scanf("%d",&element);
pos = element%hFn;
while(n++ != size){
if(ary[pos]==element){
printf("Element found at index %d\n",pos);
break;
}
else
if(ary[pos]==INT_MAX ||ary[pos]!=INT_MIN)
pos = (pos+1) %hFn;
}
if(--n==size) printf("Element not found in hash table\n");
}
void display(int ary[],int size){
int i;
printf("Index\tValue\n");
for(i=0;i<size;i++)
printf("%d\t%d\n",i,ary[i]);
}
int main(){
int size,hFn,i,choice;
printf("Enter size of hash table\n");
scanf("%d",&size);
int ary[size];
printf("Enter hash function [if mod 10 enter 10]\n");
scanf("%d",&hFn);
for(i=0;i<size;i++)
ary[i]=INT_MIN; //Assigning INT_MIN indicates that cell is empty
do{
printf("Enter your choice\n");
printf(" 1-> Insert\n 2-> Delete\n 3-> Display\n 4-> Searching\n 0-> Exit\n");
scanf("%d",&choice);
switch(choice){
case 1:
insert(ary,hFn,size);
break;
case 2:
delete(ary,hFn,size);
break;
case 3:
display(ary,size);
break;
case 4:
search(ary,hFn,size);
break;
default:
printf("Enter correct choice\n");
break;
}
}while(choice);
return 0;
}
/*
Note: Explanation for delete function and search function
suppose hash table contains elements 22, 32, 42 at index positions 2, 3, 4.
Now delete(22) applied. As per hash function defined we first check for index 2. Found, so deleted. And make that index to nill.
Next apply delete(32). This time also it first check at index 2, but found that its nothing.Then we stop and say element 32 not
found in hash table. But it's present at index 3. But how should we know whether to check to other index or not? For this
when we delete any element we flag that with INT_MAX which indicates that in that position previously some element is there now
it's deleted. So don't stop here your required element may present at next index.
*/Output
Enter size of hash table
10
Enter hash function [if mod 10 enter 10]
10
Enter your choice
1-> Insert
2-> Delete
3->Display
4->Searching
0->Exit
1
Enter key element to insert
12
Enter your choice
1-> Insert
2-> Delete
3->Display
4->Searching
0->Exit
1
Enter key element to insert
22
Enter your choice
1-> Insert
2-> Delete
3->Display
4->Searching
0->Exit
1
Enter key element to insert
32
Enter your choice
1-> Insert
2-> Delete
3->Display
4->Searching
0->Exit
3
Index Value
0 -2147483648
1 -2147483648
2 12
3 22
4 32
5 -2147483648
6 -2147483648
7 -2147483648
8 -2147483648
9 -2147483648
Enter your choice
1-> Insert
2-> Delete
3->Display
4->Searching
0->Exit
2
Enter element to delete
12
Element deleted
Enter your choice
1-> Insert
2-> Delete
3->Display
4->Searching
0->Exit
4
Enter element you want to search
32
Element found at index 4
Enter your choice
1-> Insert
2-> Delete
3->Display
4->Searching
0->Exit
0The following is the usage of hashing or hash table in C++.
Program
#include<iostream>
#include<limits.h>
using namespace std;
/*
This is code for linear probing in open addressing. If you want to do quadratic probing and double hashing which are also
open addressing methods in this code when I used hash function that (pos+1)%hFn in that place just replace with another function.
*/
void Insert(int ary[],int hFn, int Size){
int element,pos,n=0;
cout<<"Enter key element to insert\n";
cin>>element;
pos = element%hFn;
while(ary[pos]!= INT_MIN) { // INT_MIN and INT_MAX indicates that cell is empty. So if cell is empty loop will break and goto bottom of the loop to insert element
if(ary[pos]== INT_MAX)
break;
pos = (pos+1)%hFn;
n++;
if(n==Size)
break; // If table is full we should break, if not check this, loop will go to infinite loop.
}
if(n==Size)
cout<<"Hash table was full of elements\nNo Place to insert this element\n\n";
else
ary[pos] = element; //Inserting element
}
void Delete(int ary[],int hFn,int Size){
/*
very careful observation required while deleting. To understand code of this delete function see the note at end of the program
*/
int element,n=0,pos;
cout<<"Enter element to delete\n";
cin>>element;
pos = element%hFn;
while(n++ != Size){
if(ary[pos]==INT_MIN){
cout<<"Element not found in hash table\n";
break;
}
else if(ary[pos]==element){
ary[pos]=INT_MAX;
cout<<"Element deleted\n\n";
break;
}
else{
pos = (pos+1) % hFn;
}
}
if(--n==Size)
cout<<"Element not found in hash table\n";
}
void Search(int ary[],int hFn,int Size){
int element,pos,n=0;
cout<<"Enter element you want to search\n";
cin>>element;
pos = element%hFn;
while(n++ != Size){
if(ary[pos]==element){
cout<<"Element found at index "<<pos<<"\n";
break;
}
else
if(ary[pos]==INT_MAX ||ary[pos]!=INT_MIN)
pos = (pos+1) %hFn;
}
if(--n==Size)
cout<<"Element not found in hash table\n";
}
void display(int ary[],int Size){
int i;
cout<<"Index\tValue\n";
for(i=0;i<Size;i++)
cout<<i<<"\t"<<ary[i]<<"\n";
}
int main(){
int Size,hFn,i,choice;
cout<<"Enter size of hash table\n";
cin>>Size;
int ary[Size];
cout<<"Enter hash function [if mod 10 enter 10]\n";
cin>>hFn;
for(i=0;i<Size;i++)
ary[i]=INT_MIN; //Assigning INT_MIN indicates that cell is empty
do{
cout<<"Enter your choice\n";
cout<<" 1-> Insert\n 2-> Delete\n 3-> Display\n 4-> Searching\n 0-> Exit\n";
cin>>choice;
switch(choice){
case 1:
Insert(ary,hFn,Size);
break;
case 2:
Delete(ary,hFn,Size);
break;
case 3:
display(ary,Size);
break;
case 4:
Search(ary,hFn,Size);
break;
default:
cout<<"Enter correct choice\n";
break;
}
}while(choice);
return 0;
}
/*
Note: Explanation for delete function and search function
suppose hash table contains elements 22, 32, 42 at index positions 2, 3, 4.
Now delete(22) applied. As per hash function defined we first check for index 2. Found, so deleted. And make that index to nill.
Next apply delete(32). This time also it first check at index 2, but found that its nothing.Then we stop and say element 32 not
found in hash table. But it's present at index 3. But how should we know whether to check to other index or not? For this
when we delete any element we flag that with INT_MAX which indicates that in that position previously some element is there now
it's deleted. So don't stop here your required element may present at next index.
*/Remark beneath if have questions or discovered anything inaccurate in above instructional exercise for Hashing in C and C++.