What is Hashing in C++?

Hashing in C++ STL is a technique that maps a key with the associated hash value. The elements in an array can be referred to as the keys, which will have a hash value that helps in finding these keys in the hash table easily. This helps in faster access to the required element, and the efficiency might vary based on the selection of the hash function.

Why is Hashing so Important? Although the most popular data structures, such as arrays and linked lists, can still be utilized to search for the necessary key, they could be more efficient.

Arrays can be helpful when we need to randomly access any element from a particular index, but for this purpose, we need to know the index of the specific element.

This is where hashing comes into the picture. The hash function finds the hash value where a key should be stored. When we need to fetch this key, it can be easily done with the help of its hash value.

As an example, the hashing technique makes finding a person's contact information easier with the help of their names.

How to Work with Hash Function in C++?

The hash function yields an integer value from the given key, be it a character, string, integer, etc., and associates this index with the actual key.

The syntax to create a template for hash class:

Now, to create objects with the hash class, we can use the following syntax:

The hash class also has a single member function, operator(), that returns the object's hash value.

Example:

But How Does Hashing Work? There are two heuristic techniques (an approach that finds shortcuts to a solution that might not be optimal but can be reached within the required deadline) to create a hash function, hashing by division and hashing by multiplication. 

A good hash function has the following properties:

• It should be efficient for computation.
• All the keys should be uniformly distributed in the hash table.

Suppose we have 7 elements in an array. We must create a hash table where these elements will be stored for efficient access. When we come across the first element, 52, we'll perform the following operation to get its index.

What if we have more than one element with the same index? As in our case, 52 and 66 will get the same index, 3. This leads to a collision. There's always a need for a good hash function to avoid collision in frequent cases, but it is likely to happen.

There are two ways to deal with collision:

• Separate chaining
• Open Addressing

Hashing in C++ STL can be done with the help of the hash class, which we are yet to see in the examples given below. When we pass an argument to the hash class, it obtains the hash value of the passed argument. The hashed value makes searching for objects easier. The keys passed as the argument will be mapped to their obtained hash values.

Given below are some programs to find the hash value of different arguments.

Character Hashing

Output:

String Hashing

Output:

Integer Hashing

Output:

Vector Hashing

Output:

Examples to Understand the Working of Hashing Function in C++

Let us look at a C++ program to see how the hash function works for a hash table. We also need to deal with collision, so each index comprises a list sequence of keys because two or more keys can have the same table position.

And to get the index, we'll use the following hash function, get_hash(), which returns the index by division.

Here, ht_size is the size of the hash table.

Output:

As evident in the above program, we can have several keys having the same index after division, so both keys have to be associated with the same index. Therefore, a list has to be used at every index to store more keys in the same position.

Learn More

To learn more about the other concepts in C++, you can find all the C++ topics here.