C++ Custom Hash

Introduction

In C++, the unordered containers from the standard STL library, such as std::unordered_set and std::unordered_map uses hashing so that finding one item takes $O(1)$ on average. The standard library has also provided convenient built-in hash functions for common types such as std::string so that those common types could be used with the unordered containers seamlessly. Custom types, however, cannot be used with the unordered containers directly because C++ does not know how to hash the custom type.

In this blog post, I would like to discuss how to create hash functions for custom types so that they can be used with the unordered containers in C++.

C++ Custom Hash

Creating a good hash function is research and it is hard. So in this example, we are only going to use the existing built-in hash function to hash custom type that consists of common hashable types.

hash.cpp

#include <algorithm>
#include <cstddef>
#include <functional>
#include <iostream>
#include <iterator>
#include <string>
#include <unordered_set>

class Player
{
public:
    explicit Player(unsigned long const id, std::string const name)
        : m_id{id}, m_name{name}
    {
    }
    unsigned long get_id() const { return m_id; }
    std::string get_name() const { return m_name; }
    friend std::ostream& operator<<(std::ostream& os, Player const& player)
    {
        os << player.get_id() << " " << player.get_name();
        return os;
    }

private:
    unsigned long m_id;
    std::string m_name;
};

class PlayerHasher
{
public:
    std::size_t operator()(Player const& player) const
    {
        return m_hasher(player.get_id());
    }

private:
    std::hash<unsigned long> m_hasher;
};

class PlayerEqual
{
public:
    bool operator()(Player const& lhs, Player const& rhs) const
    {
        return lhs.get_name() == rhs.get_name();
    }
};

int main()
{
    Player const kobe{24, "Kobe Bryant"};
    Player const michael{23, "Michael Jordan"};
    Player const gilbert{0, "Gilbert Arenas"};
    // Tracy and Derrick will be hashed to the same bucket with PlayerHasher.
    Player const tracy{1, "Tracy McGrady"};
    Player const derrick{1, "Derrick Rose"};
    Player const chaucey{1, "Chauncey Billups"};

    // Custom hash for custom objects requires a hasher and an equal judger.
    size_t const min_bucket_count{4};
    std::unordered_set<Player, PlayerHasher, PlayerEqual> association(
        min_bucket_count);
    association.insert(kobe);
    association.insert(michael);
    association.insert(gilbert);
    association.insert(tracy);
    association.insert(derrick);

    size_t actual_num_buckets{association.bucket_count()};
    std::cout << "Number of buckets: " << actual_num_buckets << std::endl;

    for (size_t i{0}; i < actual_num_buckets; ++i)
    {
        std::cout << "Bucket " << i << " size: " << association.bucket_size(i)
                  << std::endl;
        // Using the iterator for bucket interface.
        std::cout << "Players: " << std::endl;
        std::copy(association.cbegin(i), association.cend(i),
                  std::ostream_iterator<Player>{std::cout, "\n"});
    }

    for (auto player : {tracy, derrick, chaucey})
    {
        auto player_iter{association.find(player)};
        if (player_iter != association.end())
        {
            std::cout << "Found " << player.get_name()
                      << " in the association." << std::endl;
        }
        else
        {
            std::cout << "Not found " << player.get_name()
                      << " in the association." << std::endl;
        }
    }
}

The custom type Player had been hashed successfully and stored in std::unordered_set.

$ g++ hash.cpp -o hash --std=c++14
$ ./hash
Number of buckets: 5
Bucket 0 size: 1
Players:
0 Gilbert Arenas
Bucket 1 size: 2
Players:
1 Derrick Rose
1 Tracy McGrady
Bucket 2 size: 0
Players:
Bucket 3 size: 1
Players:
23 Michael Jordan
Bucket 4 size: 1
Players:
24 Kobe Bryant
Found Tracy McGrady in the association.
Found Derrick Rose in the association.
Not found Chauncey Billups in the association.

References

• std::unordered_set
• std::hash