This is the 11th Part of Tutorial series on unordered_map. In this tutorial, we’ll learn how to use a custom class as a key in an unordered_map in C++, focusing on adding a custom hash function and overloading necessary operators.

How Hashing works in unordered_map in C++?

An unordered_map is an STL container that internally functions as a hash table and stores data in key-value pairs. It uses hash functions to organize and access its elements efficiently. When you insert key-value pairs into an std::unordered_map, it uses a hash function to compute a hash code for each key. This hash code is then used to determine the location (or “bucket”) in the underlying data structure where the corresponding value should be stored.

Here’s how things work internally:

  1. Hashing: When you insert a key-value pair into an std::unordered_map, the map uses the hash function associated with the key’s type to calculate a hash code for that key.
  2. Bucket Selection: The hash code is used to determine which bucket (storage location) in the map’s internal array the key-value pair should be placed. The map then stores the key-value pair in that bucket.
  3. Lookup and Retrieval: When you want to retrieve a value associated with a specific key, the map uses the same hash function to calculate the hash code for that key. It then goes to the corresponding bucket to quickly find and return the associated value.

Using hash codes and buckets allows std::unordered_map to provide fast average-case time complexity for common operations like insertion, retrieval, and deletion of key-value pairs. The average time complexity for these operations is O(1), meaning they are generally very efficient. However, in rare cases, when there are many hash collisions (i.e., different keys mapping to the same bucket), the performance can degrade to O(n) in the worst case. To minimize collisions, it’s essential to have a good hash function for the keys and to appropriately size the map’s internal data structure (number of buckets).

Creating Custom Hash Function & Overloading Equality Operator

When you use std::unordered_map in C++, you don’t need to specify a custom hash function explicitly for common data types like int, std::string, or other built-in types. The C++ standard library provides default implementations of std::hash() for many of these types, so the map automatically uses these default hash functions.

For example, if you have an std::unordered_map<std::string, int>, the map will use the default std::hash<std::string> to hash the string keys.

When you want to use your custom class type as a key in an unordered_map, there are two primary requirements that need to be fulfilled:”

  1. Custom Hash Function: This function is used to generate a unique hash for each key.
  2. Equality Operator Overload: This ensures that two keys are compared correctly to determine if they are the same.

Let’s consider an example in which we have a Message class with sender, receiver, messageID, and messageText as its member variables. In this case, messageID will serve as the unique key. To use this Message class as a key in an std::unordered_map, we need to overload the equality operator (==) in this Message class and also define a hash function as a function object. This hash function should use the messageID field of the Message class to calculate the hash.

#include <iostream>
#include <unordered_map>
#include <string>
#include <functional>

class Message {
public:
    std::string sender;
    std::string receiver;
    std::string messageID;
    std::string messageText;

    Message(std::string sender,
            std::string receiver,
            std::string messageID,
            std::string messageText)
        : sender(sender),
          receiver(receiver),
          messageID(messageID),
          messageText(messageText)
    {

    }

    // Overload the equality operator
    bool operator==(const Message &other) const 
    {
        return messageID == other.messageID;
    }
};

// Custom Hash Function
struct MessageHash 
{
    std::size_t operator()(const Message& msg) const {
        return std::hash<std::string>()(msg.messageID);
    }
};

In the above code, the Message class is defined with four member variables. The == operator is overloaded to compare Message objects based on their messageID. The MessageHash struct provides a custom hash function that hashes the messageID.

Using Custom Class as Key in Unordered_Map

Now that we have our Message class and the required custom hash function, we can now use it in the unordered_map as Key. Let’s see the code for that,

int main() 
{
    // Creating an unordered_map with Message as key
    std::unordered_map<Message, std::string, MessageHash> messageMap;

    // Creating Messages
    Message msg1("Ritika", "Sanjay", "ID1", "Welcome Back!!");
    Message msg2("Shruti", "Shaunak", "ID2", "Good Morning");

    // Adding Messages to the map
    messageMap[msg1] = "First Message";
    messageMap[msg2] = "Second Message";

    // Accessing data
    for (const auto& pair : messageMap) {
        std::cout << "Key(MessageID): " << pair.first.messageID << " Value: " << pair.second << std::endl;
    }

    return 0;
}

Output:

Key(MessageID): ID2 | Value: Second Message
Key(MessageID): ID1 | Value: First Message

In main() function, we declared an unordered_map object named messageMap that uses Message objects as keys. We then create two Message objects and add them to the map. The for loop iterates over the map and prints each key-value pair.

Summary

Today, we learned how to use a custom class (Message in our case) as a key in an unordered_map in C++. This involved creating a custom hash function and overloading the equality operator for the class.

Ritika Ohri

Hi, I am Ritika Ohri, founder of this blog. I craft comprehensive programming tutorials and also manage a YouTube channel. You can also connect with me on Linkedin.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.