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 about 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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
$ 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

Author

Lei Mao

Posted on

02-25-2022

Updated on

02-25-2022

Licensed under


Comments