How to Implement Custom Hash Functions for User-Defined Types in std::unordered_map?
In C++ std::unordered_map
is a data structure that implements a hash table and allows fast access to each element based on its key. However, when we want to use user-defined types as keys, we need to provide a custom hash function. In this article, we will learn how to implement a custom hash function for user-defined types in std::unordered_map
.
Implement Custom Hash Functions for User-Defined Types in std::unordered_map
To implement a custom hash function, we need to define a functor (a struct or class that overloads the operator()
) that should take an object of our user-defined type as input and return the hash value. We need to pass that custom hash function as a template argument while declaring the std::unordered_map
using the below syntax.
Syntax to Use a Custom Hash Function in std::unordered_map
unordered_map<KeyType, ValueType, HashType>
Here,
KeyType
is a user-defined type,ValueType
is the type of the values in the map.HashType
is the custom hash function.
Approach:
- First, define a user-defined type(class, struct or any other user-defined type) for which you want to implement a custom hash function.
- Next, define a custom hash function that should be a struct or class that overloads the
operator() and i
t should take an object of your user-defined type as input and return astd::size_t
representing the hash value.- Finally, use the custom hash function as a template argument while declaring the
std::unordered_map
.
C++ Program to Implement Custom Hash Functions for User-Defined Types in std::unordered_map
The below program demonstrates how we can implement a custom hash function for user-defined types in std::unordered_map
in C++.
// C++ program to Implement Custom Hash Functions for
// User-Defined Types in std::unordered_map
#include <iostream>
#include <unordered_map>
using namespace std;
struct Point {
int x, y;
// Constructor
Point(int x, int y)
: x(x)
, y(y)
{
}
bool operator==(const Point& other) const
{
return x == other.x && y == other.y;
}
};
// Define a custom hash function for the Point
struct PointHasher {
size_t operator()(const Point& p) const
{
// Combine hashes of x and y using the bitwise XOR
return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
}
};
int main()
{
// Create an unordered_map with the Point as key and int
// as value and pass hash function as template arguement
unordered_map<Point, int, PointHasher> point_map;
point_map[Point(1, 2)] = 10;
point_map[Point(3, 4)] = 20;
point_map[Point(5, 6)] = 30;
// printing the key-value pairs of point_map
for (const auto& pair : point_map) {
cout << "Point(" << pair.first.x << ", "
<< pair.first.y << "): " << pair.second
<< endl;
}
return 0;
}
Output
Point(5, 6): 30 Point(3, 4): 20 Point(1, 2): 10
Time Complexity: O(1), for insertion, deletion, and access in std::unordered_map
Auxilliary Space: O(n), where n is the number of elements in the map.
Contact Us