Updated April 18, 2023
Introduction to C++ hash
In C++, the hash is a function that is used for creating a hash table. When this function is called, it will generate an address for each key which is given in the hash function. And if the hash function returns a unique hash number, then this hash function is called a universal hash function. The standard library of C++ which provides a class called hash class which can be constructed without passing any arguments, so in general, a hash function is used for hashing, which will map key to some values which forms a hash table a data structure which this function will compute an index into an array.
Working of the hash function in C++ with examples
In this article, we will see the hash class defined as std::hash in the C++ standard library, which allows the user to create a hash class that can construct the objects without initializing the values and parameters can say a hash class as a template class. So the main moto of using a hash is to make the searching faster, which is done using the indexes of each value that are located in memory where a hash function has the key (index), which points to the address of the value that is located in the memory where it can be fetched faster by using its key. In C++, the hash function is a function where a key is pointing to a value which is an address; when this function is called, which uses the combination of letters and numbers in the hash table, which can be used for the arrangement of data.
There is a chance of collision of two or more keys pointing to the same values and can be avoided by using chain hashing, which will point the linked list records as each cell in the hash table having the same have the same values that the hash key maps to the hash function values. So in real-time, we can relate this hash function or hash table to a telephone directory book where each name is a key and the telephone number as a value to the key, which is the name.
The hash class can be defined using the STL library in C++, which is used for fetching the hash value of the parameters that are being passed to it, so let us see the syntax below:
Syntax:
template <class key> struct hash;In the above, we can see we have a syntax to write or create a hash class, and then we can create an object in std::hash class using the below syntax:
Syntax:
hash<class template> obj_name ;So to add some items inside the hash table, we need to have a hash function using the hash index of the given keys, and this has to be calculated using the hash function as “hash_inx = key % num_of_slots(size of the hash table) ” for, eg. The size of the hash table is 10, and the key-value(item) is 48, then hash function = 43 % 10 = 3; therefore, the hash code will be 3, which means 43 items is placed in the hash table at the index 3. Sometimes there may occur collision of placing the items at same index suppose if we have key-value 63 then again it would yield us 3 only as of the hash code which is colliding with key-value 43 so to avoid this type of collision or resolve this type of issues we can use open hashing or separate chaining which is implemented similarly as linked list, another way to resolve is using linear probing which allows all the entries to be stored in the hash table itself and many other ways to resolve this collision issues.
So the hash table is an array with a particular size having a hash function that is mapping from object to its items inside the hash table, where these objects are placed in the hash table, which is like an array having an index for each object it will have index via the hash function which can be computed as index = h(object) so such array is known as a hash table. This hash class has only one member function known as the operator(), which returns the hashed values for which parameters are passed or given to the member function. So in below, let us simple program to get hash values for the given corresponding hash function using various objects.
Example:
#include <iostream>
#include <string>
using namespace std;
void strhashing()
{
string h1 = "Educba";
cout <<"The string given to get the hash value is "<< h1 <<"\n"<<endl;
hash<string> hash_obj;
cout << "The hash value of the given string is : " << hash_obj(h1)<< endl;
}
int main()
{
cout<<"Program to demonstrate the string hash values that are returned using hash class and its objects."<<"\n"<<endl;
strhashing();
}Output:
In the above program, we can see we are defining function strhashing() where we are declaring a string “h1”, and we are trying to get the string hashed value for the given string “Educba”, where first we will create a hash object as “hash_obj” where we are passing the given string as an argument to the hash object that is created which will demonstrate the string hashing and the hashed value of the given string “Educba” is 11677389314383596536 as shown in the above screenshot. Therefore other than string data type, there are many other data types where the hash functions can be used to hash values of each data type, such as char, vector, Boolean, float, double, long, etc.
So now, let us try to create a hash table using C++ programming language using hash function values in the below example.
Example:
#include <iostream>
#include <list>
using namespace std;
class hash_table{private:
list<int> *tbl;
int all_ele;
int fetch_hash(int k){
return k % all_ele;
}public:
hash_table(int a){
all_ele = a;
tbl = new list<int>[all_ele];
}
void inst_ele(int k){
tbl[fetch_hash(k)].push_back(k);
}
void disp(){
for(int i = 0; i < all_ele; i++){
cout << "The Index of item is " << i << "\n " <<endl;
for(int j : tbl[i])
cout <<"The value for the index "<<i << " is " << j << endl;
cout << endl;
}
}
};
int main() {
hash_table kh(3);
int a[] = {2, 4, 6};
for(int i = 0; i < 3; i++)
kh.inst_ele(a[i]);
cout << "The hash table is created is as follows: " << "\n"<< endl;
kh.disp();
return 0;
}Output:
In the above program, we can see we are declaring an array and trying to insert each item in the hash table where we first calculate the hash function, which gives us the index value which can be used to place the items. So in the above screenshot, we can see we have placed the items in the particular index as shown in the output.
Conclusion
In this article, we conclude that hash in C++ is a function used for creating a hash table that is very useful for searching for any items easily and quickly. In this article, we saw the syntax of creating an object of a hash class using the syntax of the hash class. In this article, we also saw an example of getting the hashed value of the data type variables. In this article, we also saw how to create a hash table and how to insert the elements in the hash table.
Recommended Articles
This is a guide to C++ hash. Here we discuss the Working of the hash function in C++ and Examples along with the outputs. You can also look at the following article to learn more –
