How-To make C++ types hashable

Making a C++ type hashable for use as a key in e.g. std::unordered_map is simple; all it requires is that an overload of std::hash exists for that type.

We provide a simple macro to help with this, which delegates to a member function of that type. This is mostly a matter of preference, but it allows to keep the definition of how to hash a type closer to the type itself.

Make type hashable
 1#include <liberate/cpp/hash.h>
 2
 3struct my_type
 4{
 5  inline size_t hash() const
 6  {
 7    // Calculate hash value
 8  }
 9};
10
11LIBERATE_MAKE_HASHABLE(my_type);

Note

The macro defines an overload in the std namespace, and therefore must be used in the global scope, outside of any of the namespaces you define. This could mean that you need to prefix the namespace to its argument, e.g. use LIBERATE_MAKE_HASHABLE(foo::my_type).

The more complex part usually lies in how to calculate a hash value for a complex type in the first place. Hash functions should be relatively simple, and not produce too many collisions.

The library provides one such function liberate::cpp::hash_combine(), which adds a value to a pre-existing seed value in a way that lets you repeat this several times.

Make type hashable
 1struct my_type
 2{
 3  int foo;
 4  char bar;
 5
 6  inline size_t hash() const
 7  {
 8    using namespace liberate::cpp;
 9    size_t result = 0;
10    hash_combine(result, std::hash<int>()(foo));
11    hash_combine(result, std::hash<char>()(bar));
12    return result;
13  }
14};

Because the above is somewhat tedious, the header also defines a function liberate::cpp::multi_hash() which does the above recursively for a variable number of arguments, and even deduces the type of the arguments.

You can rewrite the above like this:

Use multi_hash
 1struct my_type
 2{
 3  int foo;
 4  char bar;
 5
 6  inline size_t hash() const
 7  {
 8    return liberate::cpp::multi_hash(foo, bar);
 9  }
10};

Finally, it sometimes is necessary to calculate a hash over a range, such as for a std::string, or a list of values. That is also made relatively easy.

Use range_hash
1std::string tmp{"Hello, world!"};
2auto hash = liberate::cpp::range_hash(tmp.begin(), tmp.end());

You can, for example, now liberate::cpp::hash_combine() this with other values.