Lately I have been refactoring some old code & found it littered with all sorts of things. This particular code had a custom hash-table for hashing based off 3 values instead of 1. std::tuple are the best fit, or probably providing a custom struct with std::hash specialization would have served as well. What std library provides is std::hash for basic types, reference here. There is nothing for composite types. Even for std::pair.
Providing a std::hash for both std::pair and std::tuple is what I want to address with this post.
hashing a std::pair
A pair has two elements, thus it is quite straight forward to specialize the hash, just have to use a special hash_combine:
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
| // on why XOR is not a good choice for hash-combining:
// https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes
//
// this is from boost
//
template<typename T>
inline void hash_combine(std::size_t& seed, const T& val)
{
std::hash<T> hasher;
seed ^= hasher(val) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
// taken from https://stackoverflow.com/a/7222201/916549
//
template<typename S, typename T>
struct hash<std::pair<S, T>>
{
inline size_t operator()(const std::pair<S, T>& val) const
{
size_t seed = 0;
hash_combine(seed, val.first);
hash_combine(seed, val.second);
return seed;
}
};
|
hash_combine is from boost, so that helps and the link has pretty good explanation for this algorithm.
For std::pair just call it twice and be done with it.
The complexity comes with std::tuple and how do you handle #types to be hashed without specialization for arity of types.
hashing a std::tuple
Now along similar lines, here is the specialization of hash, but in this case we need something that iterates/recurses over all the types.
1
2
3
4
5
6
7
8
9
10
11
|
template<class... TupleArgs>
struct std::hash<std::tuple<TupleArgs...>>
{
size_t operator()(std::tuple<TupleArgs...> tupleValue) const
{
size_t seed = 0;
hash_combine_tup(seed, tupleValue);
return seed;
}
};
|
I want to reuse hash_combine from before, yet want to define a way to iterate over the types of std::tuple and compute new hash using std::hash and hash_combine. Since I am fiddling with types here this calls for recursion instead of iteration.
There are various ways to do this, one could be to construct a new std::tuple with fewer elements and pass to the specialization or other is to increase/decrease the type index. I would go with type-index as it avoids copying business.
To achieve this we need:
- termination function, that does nothing- stops recursion
1
2
3
4
5
6
7
8
9
|
// this is a termination condition
// N == sizeof...(TupleTypes)
//
template<size_t Idx, typename... TupleTypes>
inline typename std::enable_if<Idx == sizeof...(TupleTypes), void>::type
hash_combine_tup(size_t& seed, const std::tuple<TupleTypes...>& tup)
{
}
|
- and a function that computes hash & recurses to termination
1
2
3
4
5
6
7
8
9
10
11
12
| // this is the computation workhorse
// N < sizeof...(TupleTypes)
//
template<size_t Idx, typename... TupleTypes>
inline typename std::enable_if<Idx < sizeof...(TupleTypes), void>::type
hash_combine_tup(size_t& seed, const std::tuple<TupleTypes...>& tup)
{
hash_combine(seed, std::get<Idx>(tup));
// on to next element
hash_combine_tup<Idx+1>(seed, tup);
}
|
Putting all of this together:
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
|
template <class T>
inline void hash_combine(std::size_t& seed, T v)
{
seed ^= std::hash<T>()(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}
template<class... TupleArgs>
struct std::hash<std::tuple<TupleArgs...>>
{
private:
// this is a termination condition
// N == sizeof...(TupleTypes)
//
template<size_t Idx = 0, typename... TupleTypes>
inline typename std::enable_if<N == sizeof...(TupleTypes), void>::type
hash_combine_tup(size_t& seed, const std::tuple<TupleTypes...>& tup) const
{
}
// this is the computation workhorse
// N < sizeof...(TupleTypes)
//
template<size_t Idx = 0, typename... TupleTypes>
inline typename std::enable_if<N < sizeof...(TupleTypes), void>::type
hash_combine_tup(size_t& seed, const std::tuple<TupleTypes...>& tup) const
{
hash_combine(seed, std::get<Idx>(tup));
// on to next element
hash_combine_tup<Idx+1>(seed, tup);
}
public:
size_t operator()(std::tuple<TupleArgs...> tupleValue) const
{
size_t seed = 0;
hash_combine_tup<0>(seed, tupleValue);
return seed;
}
};
|
That’s it for now..
I have posted entire thing as a gist here.