How do I combine hash values in C++0x?
Solution 1
Well, just do it like the boost guys did it:
template <class T>
inline void hash_combine(std::size_t& seed, const T& v)
{
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
}
Solution 2
I'll share it here since it can be useful to others looking for this solution: starting from @KarlvonMoor answer, here's a variadic template version, which is terser in its usage if you have to combine several values together:
inline void hash_combine(std::size_t& seed) { }
template <typename T, typename... Rest>
inline void hash_combine(std::size_t& seed, const T& v, Rest... rest) {
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed<<6) + (seed>>2);
hash_combine(seed, rest...);
}
Usage:
std::size_t h=0;
hash_combine(h, obj1, obj2, obj3);
This was written originally to implement a variadic macro to easily make custom types hashable (which I think is one of the primary usages of a hash_combine
function):
#define MAKE_HASHABLE(type, ...) \
namespace std {\
template<> struct hash<type> {\
std::size_t operator()(const type &t) const {\
std::size_t ret = 0;\
hash_combine(ret, __VA_ARGS__);\
return ret;\
}\
};\
}
Usage:
struct SomeHashKey {
std::string key1;
std::string key2;
bool key3;
};
MAKE_HASHABLE(SomeHashKey, t.key1, t.key2, t.key3)
// now you can use SomeHashKey as key of an std::unordered_map
Solution 3
A few days ago I came up with slightly improved version of this answer (C++ 17 support is required):
template <typename T, typename... Rest>
void hashCombine(uint& seed, const T& v, Rest... rest)
{
seed ^= ::qHash(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
(hashCombine(seed, rest), ...);
}
The code above is better in terms of code generation. I used qHash function from Qt in my code, but it's also possible to use any other hashers.
Solution 4
This could also be solved by using a variadic template as follows:
#include <functional>
template <typename...> struct hash;
template<typename T>
struct hash<T>
: public std::hash<T>
{
using std::hash<T>::hash;
};
template <typename T, typename... Rest>
struct hash<T, Rest...>
{
inline std::size_t operator()(const T& v, const Rest&... rest) {
std::size_t seed = hash<Rest...>{}(rest...);
seed ^= hash<T>{}(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
return seed;
}
};
Usage:
#include <string>
int main(int,char**)
{
hash<int, float, double, std::string> hasher;
std::size_t h = hasher(1, 0.2f, 2.0, "Hello World!");
}
One could certainly make a template function, but this could cause some nasty type deduction e.g hash("Hallo World!")
will calculate a hash value on the pointer rather than on the string. This is probably the reason, why the standard uses a struct.
Solution 5
The answer by vt4a2h is certainly nice but uses the C++17 fold expression and not everyone is able to switch to a newer toolchain easily. The version below uses the expander trick to emulate a fold expression and works in C++11 and C++14 as well.
Additionally, I marked the function inline
and use perfect forwarding for the variadic template arguments.
template <typename T, typename... Rest>
inline void hashCombine(std::size_t &seed, T const &v, Rest &&... rest) {
std::hash<T> hasher;
seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
(int[]){0, (hashCombine(seed, std::forward<Rest>(rest)), 0)...};
}
Comments
-
Neil G almost 2 years
C++0x adds
hash<...>(...)
.I could not find a
hash_combine
function though, as presented in boost. What is the cleanest way to implement something like this? Perhaps, using C++0xxor_combine
?