# Hashing a tuple in C++17

C++ doesn't supply a std::hash<std::tuple<...>>, so I decided to implement one. However, I was viewing this as more of a hash library than extensions to std, so I placed it all under the namespace utils.

This was my first time seriously using template meta-progamming. I tried to make my code work no matter the cv-ness of the variable, or whether it was an rvalue or an lvalue. I'm not sure on the efficiency of execution, but I believe the compiler can optimize it down to simple arithmetic on hash values.

hash.h

#pragma once

#include <functional>
#include <tuple>
#include <type_traits>
#include <utility>

#include <cstdint>

namespace utils {

template<class T>
struct hash
{
template<class Type>
std::size_t operator()(Type && v) const {
return std::hash<T>()(std::forward<Type>(v));
}
};

namespace internal {
// A simple algorithm for combining two hash values,
// algorithm from boost: http://www.boost.org/doc/libs/1_61_0/doc/html/hash/reference.html#boost.hash_combine
constexpr inline std::size_t hash_combine(std::size_t hash1, std::size_t hash2) {
return hash1 ^ (hash2 * 0x9e3779b9 + (hash1 << 6) + (hash1 >> 2));
}

// Necessary to hold a value so that we can use the fold operator
struct hash_combine_t
{
const std::size_t value;
};

// % because it's a non-commutative operator that has been used for things other than
// it's "intended" purpose before (e.g. string formatting)
constexpr hash_combine_t operator%(const hash_combine_t &lhs, const hash_combine_t &rhs) {
return { hash_combine(lhs.value, rhs.value) };
}

template<class... Ts>
constexpr std::size_t hash_combine_impl(Ts&&... args) {
return (hash_combine_t{ static_cast<std::size_t>(args) } % ...).value;
}

template<class... Ts>
constexpr std::size_t hash_all_impl(Ts&&... args) {
return hash_combine_impl(utils::hash<std::decay_t<Ts>>()(std::forward<Ts>(args))...);
}
}

template<class... Ts>
constexpr std::size_t hash_combine(Ts&&... args) {
return internal::hash_combine_impl(args...);
}

template<class... Ts>
constexpr std::size_t hash_all(Ts&&... args) {
return internal::hash_all_impl(static_cast<std::decay_t<Ts>>(args)...);
}

template<class... Ts>
struct hash<std::tuple<Ts...>>
{
private:
// We have this impl_t struct in order to support hashing of the empty tuple:
//     std::tuple<>
// The struct gives us partial template specification.
template<std::size_t I, class Tuple>
struct impl_t {
std::size_t operator()(Tuple && tuple) const {
// If this was called with an lvalue, we need to add an lvalue reference to our
// types in order to get the correct utils::hash_all function.
// utils::hash_all<Ts...> does not work; only things similar to
// utils::hash_all<Ts&...> would work, but then it would not work for
// rvalues as well.
//
// So we determine whether this was called with an lvalue by using std::is_reference<Tuple>.
return std::apply(
utils::hash_all<
std::conditional_t<
std::is_reference<Tuple>::value,
>...
>,
std::forward<Tuple>(tuple)
);
}
};
template<class Tuple>
struct impl_t<0, Tuple> {
std::size_t operator()(Tuple && tuple) const {
// 0 is a good value for the empty tuple; there is only one empty tuple
return 0;
}
};
public:
template<class Tuple>
std::size_t operator()(Tuple && tuple) const {
return impl_t<sizeof...(Ts), Tuple>()(std::forward<Tuple>(tuple));
}
};

}

• – David Aug 4 '16 at 15:44

I think we can definitely simplify that:

#include <tuple>
#include <iostream>
#include <functional>
#include <type_traits>


## Forward Declaration.

template<typename Tuple, std::size_t... ids>
std::size_t tupleHash(Tuple const& tuple, std::index_sequence<ids...> const&);


## Hash All Types

template<typename T>
std::size_t hashValue(T const& value)
{
// SFINAE kicks in here for tuples.
// There is no std::hash that works for tuples.
// So this candidate will be ignored if you use a tuple.
std::hash<T>    hasher;
return hasher(value);
}


### Have a version for Tuples.

template<typename... Args>
std::size_t hashValue(std::tuple<Args...> const& value)
{
return tupleHash(value, std::make_index_sequence<sizeof...(Args)>());
}
// Special case the empty tuple (as Args... can not be the empty list).
std::size_t hashValue(std::tuple<> const& value)
{
// Not an expert in hashing.
// Do some appropriate thing to get a value;
return 1;
}


### Do all the work in a helper function.

template<typename Tuple, std::size_t... ids>
std::size_t tupleHash(Tuple const& tuple, std::index_sequence<ids...> const&)
{
// Not an expert in hashing.
// Not sure 0 is a good seed (or this algorithm is good) solely here for demo purpose.
std::size_t  result = 0;
for(auto const& hash: {hashValue(std::get<ids>(tuple))...})
{
result ^= hash + 0x9e3779b9 + (result<<6) + (result>>2);
}
return result;
};


### Tests

int main()
{
auto tp = std::make_tuple(1,2,"Loki");
std::cout << hashValue(tp) << "\n";

auto ttp = std::make_tuple(4,tp,8,tp);
std::cout << hashValue(ttp) << "\n";

auto et = std::make_tuple();
std::cout << hashValue(et) << "\n";
}

• @justin: It was just supposed to show where to combine the values. I did not want to look up an actual hash combining function as there are a couple out there and it would be arbitrary which one I chose (as I have no context for the use case). – Martin York Aug 3 '16 at 20:12
• This fails for nested tuples. You could define Hash as a specialization of std::hash and then it would work for that, but I wanted to not specialize std::hash. – Justin Aug 3 '16 at 20:23
• This also fails for the empty tuple, but a specialization for hash would fix that – Justin Aug 3 '16 at 20:29
• @Justin: Do you want me sit down tonight and actually work on real version rather than giving you hints on how to improve your code? – Martin York Aug 3 '16 at 22:26
• I'm sorry if I came across as demanding. I didn't understand that you were suggesting improvements rather than saying "this is a much better way to do it, just use this code instead" – Justin Aug 4 '16 at 20:53