std::hash
Defined in header
<functional>
|
||
template< class Key >
struct hash; |
(since C++11) | |
The hash template defines a function object that implements a hash function. Instances of this function object satisfy Hash
. In particular, they define an operator() that:
1. Accepts a single parameter of type Key
.
2. Returns a value of type size_t that represents the hash value of the parameter.
3. Does not throw exceptions when called.
4. For two parameters k1
and k2
that are equal, std::hash<Key>()(k1) == std::hash<Key>()(k2).
5. For two different parameters k1
and k2
that are not equal, the probability that std::hash<Key>()(k1) == std::hash<Key>()(k2) should be very small, approaching 1.0/std::numeric_limits<size_t>::max().
The hash template is DefaultConstructible
, CopyAssignable
, Swappable
and Destructible
.
The unordered associative containers std::unordered_set, std::unordered_multiset, std::unordered_map, std::unordered_multimap use specializations of the template std::hash as the default hash function.
Contents |
[edit] Notes
The actual hash functions are implementation-dependent and are not required to fulfill any other quality criteria except those specified above. Notably, some implementations use trivial (identity) hash functions which map an integer to itself. In other words, these hash functions are designed to work with unordered associative containers, but not as cryptographic hashes, for example.
Hash functions are only required to produce the same result for the same input within a single execution of a program; this allows salted hashes that prevent collision DoS attacks. | (since C++14) |
There is no specialization for C strings. std::hash<const char*> produces a hash of the value of the pointer (the memory address), it does not examine the contents of any character array.
[edit] Member types
Member type | Definition |
argument_type
|
Key
|
result_type
|
std::size_t |
[edit] Member functions
constructs a hash function object (public member function) |
|
calculate the hash of the argument (public member function) |
[edit] Standard specializations for basic types
Defined in header
<functional>
|
||
template<> struct hash<bool>;
template<> struct hash<char>; |
||
In addition to the above, standard library provides specializations for all (scoped and unscoped) enumeration types (which are not required, but usually are implemented as std::hash<std::underlying_type<Enum>::type>) |
(since C++14) |
[edit] Standard specializations for library types
(C++11)(C++11)(C++11)(C++11)
|
hash support for strings (class template specialization) |
(C++11)
|
hash support for std::error_code (class template specialization) |
(C++11)
|
hash support for std::bitset (class template specialization) |
(C++11)
|
hash support for std::unique_ptr (class template specialization) |
(C++11)
|
hash support for std::shared_ptr (class template specialization) |
(C++11)
|
hash support for std::type_index (class template specialization) |
(C++11)
|
hash support for std::vector<bool> (class template specialization) |
(C++11)
|
hash support for std::thread::id (class template specialization) |
Note: additional specializations for std::pair
and the standard container types, as well as utility functions to compose hashes are available in boost.hash
[edit] Examples
Demonstrates the computation of a hash for std::string, a type that already has a hash specialization.
#include <iostream> #include <functional> #include <string> int main() { std::string str = "Meet the new boss..."; std::hash<std::string> hash_fn; std::size_t str_hash = hash_fn(str); std::cout << str_hash << '\n'; }
Possible output:
391070135
Demonstrates creation of a hash function for a user defined type. Using this as a template parameter for std::unordered_map, std::unordered_set, etc. also requires specialization of std::equal_to.
#include <iostream> #include <functional> #include <string> struct S { std::string first_name; std::string last_name; }; template <class T> class MyHash; template<> class MyHash<S> { public: std::size_t operator()(S const& s) const { std::size_t h1 = std::hash<std::string>()(s.first_name); std::size_t h2 = std::hash<std::string>()(s.last_name); return h1 ^ (h2 << 1); } }; int main() { std::string s1 = "Hubert"; std::string s2 = "Farnsworth"; std::hash<std::string> h1; S n1; n1.first_name = s1; n1.last_name = s2; std::cout << "hash(s1) = " << h1(s1) << "\n" << "hash(s2) = " << std::hash<std::string>()(s2) << "\n" << "hash(n1) = " << MyHash<S>()(n1) << "\n"; }
Possible output:
hash(s1) = 6119893563398376542 hash(s2) = 14988020022735710972 hash(n1) = 17649170831080298918
Demonstrates how to specialize std::hash for a user defined type.
#include <iostream> #include <functional> #include <string> struct S { std::string first_name; std::string last_name; }; namespace std { 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); } }; } int main() { S s; s.first_name = "Bender"; s.last_name = "Rodriguez"; std::hash<S> hash_fn; std::cout << "hash(s) = " << hash_fn(s) << "\n"; }
Possible output:
hash(s) = 32902390710