std::hash is a C++ standard library class template that produces hash values for objects of a specified type. Unordered containers use it to map keys to buckets, then use equality comparison to resolve collisions. section 8.2.1
Using std::hash with an unordered container involves these ideas:
- Use the standard specializations for supported types, including numeric types and std::string. section 8.2.1
- Provide a hash implementation for a user-defined key type that lacks one. section 8.2.1
- Provide equality comparison as well, because different keys can produce the same hash value. section 8.2.1
Hashing a game state
A matching-pennies game stores its state in an std::tuple. A specialization of std::hash<state_t> hashes each tuple element with std::hash, then combines the results: h1 + (h2 << 1) + (h3 << 2). This makes state_t usable as the key of an std::unordered_map. section 8.2.1
Listing 8.4 Specializing std::hash for our state tuple
#include <functional>
template<> #1
struct std::hash<state_t> #1
{
std::size_t operator()(state_t const& state) const noexcept #2
{
std::size_t h1 = std::hash<Outcome>{}(std::get<0>(state)); #3
std::size_t h2 = std::hash<Choice>{}(std::get<1>(state)); #3
std::size_t h3 = std::hash<Outcome>{}(std::get<2>(state)); #3
return h1 + (h2 << 1) + (h3 << 2); #4
}
};
View the complete specialization for the game-state tuple, including its operator() and component hashes. section 8.2.1
