I want to have an std::unordered_map
which uses arrays as keys. As long as a type has an operator==
and an std::hash
it can be used as a key.
Here is my std::hash<std::array>
template<class T, size_t N>
struct std::hash<std::array<T, N>> {
auto operator() (const std::array<T, N>& key) const {
std::hash<T> hasher;
size_t result = 0;
for(size_t i = 0; i < N; ++i) {
result = result * 31 + hasher(key[i]); // ??
}
return result;
}
};
I copied the multiply by 31 from somewhere. An example here uses <<
and ^
. I don't know which is better or how to apply the cppreference example to an array.
// cppreference example
template<> struct hash<S>
{
typedef S argument_type;
typedef std::size_t result_type;
result_type operator()(argument_type const& s) const
{
result_type const h1 ( std::hash<std::string>{}(s.first_name) );
result_type const h2 ( std::hash<std::string>{}(s.last_name) );
return h1 ^ (h2 << 1); // or use boost::hash_combine (see Discussion)
}
};
It seems to work. All of the code compiles and the return values for std::hash<key_type>
seem ok to me.
using key_type = std::array<int, 2>;
using hash_type = std::hash<key_type>;
using map_type = std::unordered_map<key_type, int>;
map_type map; // compiles
hash_type hasher; // compiles
int main() {
// test return values of std::hash<key_type>
for(int y = -2; y < 3; ++y) {
for(int x = -2; x < 3; ++x) {
std::cout << hasher({x, y}) << " ";
}
std::cout << std::endl;
}
}
The values printed from this code are:
18446744073709551552 18446744073709551583 18446744073709551614 29 60
18446744073709551553 18446744073709551584 18446744073709551615 30 61
18446744073709551554 18446744073709551585 0 31 62
18446744073709551555 18446744073709551586 1 32 63
18446744073709551556 18446744073709551587 2 33 64
I'm not sure what makes a good hash function for std::unordered_map
, so I'd appreciate any feedback on how to make this hash function better.