Difference between revisions of "cpp/utility/hash"
(Applied P2592R3 (Hashing support for std::chrono value classes) part 3.) |
m (→Header list: +<filesystem>.) |
||
(4 intermediate revisions by 3 users not shown) | |||
Line 1: | Line 1: | ||
{{cpp/title|hash}} | {{cpp/title|hash}} | ||
{{cpp/utility/hash/navbar}} | {{cpp/utility/hash/navbar}} | ||
− | {{ | + | |
+ | {{dcl begin}} | ||
+ | {{dcl header|bitset}} | ||
+ | {{dcl header|coroutine}} | ||
+ | {{dcl header|chrono|notes={{mark since c++26}}}} | ||
+ | {{dcl header|filesystem}} | ||
+ | {{dcl header|functional}} | ||
+ | {{dcl header|memory}} | ||
+ | {{dcl header|optional}} | ||
+ | {{dcl header|stacktrace}} | ||
+ | {{dcl header|string}} | ||
+ | {{dcl header|string_view}} | ||
+ | {{dcl header|system_error}} | ||
+ | {{dcl header|thread}} | ||
+ | {{dcl header|typeindex}} | ||
+ | {{dcl header|variant}} | ||
+ | {{dcl header|vector}} | ||
+ | {{dcl|since=c++11| | ||
template< class Key > | template< class Key > | ||
struct hash; | struct hash; | ||
}} | }} | ||
− | + | {{dcl end}} | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
The unordered associative containers {{lc|std::unordered_set}}, {{lc|std::unordered_multiset}}, {{lc|std::unordered_map}}, {{lc|std::unordered_multimap}} use specializations of the template {{tt|std::hash}} as the default hash function. | The unordered associative containers {{lc|std::unordered_set}}, {{lc|std::unordered_multiset}}, {{lc|std::unordered_map}}, {{lc|std::unordered_multimap}} use specializations of the template {{tt|std::hash}} as the default hash function. | ||
− | + | Given a type {{tt|Key}}, each specialization {{tt|std::hash<Key>}} is either ''enabled'' or ''disabled''{{sep}}: | |
+ | * If {{tt|std::hash<Key>}} is not provided by the program or the user, it is disabled. | ||
+ | * Otherwise, {{tt|std::hash<Key>}} is enabled if all following conditions are satisfied: | ||
+ | :* All following requirements are satisfied: | ||
+ | ::* {{named req|Hash}} (with {{tt|Key}} as the function call argument type) | ||
+ | ::* {{named req|DefaultConstructible}} | ||
+ | ::* {{named req|CopyAssignable}} | ||
+ | ::* {{named req|Swappable}} | ||
+ | :* Given the following values: | ||
+ | ::* {{c|h}}, an object of type {{tt|std::hash<Key>}}. | ||
+ | ::* {{c|k1}} and {{c|k2}}, objects of type {{tt|Key}}. | ||
+ | :: All following requirements are satisfied: | ||
+ | ::* If {{c|1=k1 == k2}} is {{c|true}}, {{c|1=h(k1) == h(k2)}} is also {{c|true}}. | ||
+ | ::* Unless {{tt|std::hash<Key>}} is a [[cpp/language/type#Program-defined type|program-defined specialization]], {{c|h(k1)}} will never throw an exception. | ||
+ | * Otherwise, {{tt|std::hash<Key>}} is disabled. | ||
+ | |||
+ | Disabled specializations do not satisfy {{named req|Hash}}, do not satisfy {{named req|FunctionObject}}, and following values are all {{c|false}}: | ||
* {{c|std::is_default_constructible<std::hash<Key>>::value}} | * {{c|std::is_default_constructible<std::hash<Key>>::value}} | ||
* {{c|std::is_copy_constructible<std::hash<Key>>::value}} | * {{c|std::is_copy_constructible<std::hash<Key>>::value}} | ||
Line 29: | Line 51: | ||
In other words, they exist, but cannot be used. | In other words, they exist, but cannot be used. | ||
− | + | {{rrev|until=c++20| | |
− | + | ===Nested types=== | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | {{rrev|until=c++20| | + | |
− | === | + | |
{{dsc begin}} | {{dsc begin}} | ||
− | {{dsc hitem| | + | {{dsc hitem|Name|Definition}} |
− | {{dsc|{{tt|argument_type}}{{mark deprecated c++17}}|{{tt|Key}}}} | + | {{dsc|{{tt|argument_type}} {{mark deprecated c++17}}|{{tt|Key}}}} |
− | {{dsc|{{tt|result_type}}{{mark deprecated c++17}}|{{lc|std::size_t}}}} | + | {{dsc|{{tt|result_type}} {{mark deprecated c++17}}|{{lc|std::size_t}}}} |
{{dsc end}} | {{dsc end}} | ||
}} | }} | ||
Line 51: | Line 66: | ||
{{dsc end}} | {{dsc end}} | ||
− | ===Standard specializations | + | ===Standard library specializations=== |
− | + | Each header that declares the template {{tt|std::hash}} also provides enabled specializations of {{tt|std::hash}} for the following types: | |
− | + | * all cv-unqualified [[cpp/language/types|arithmetic types]] | |
− | + | * all cv-unqualified [[cpp/language/enum|enumeration types]] | |
− | template | + | * all cv-unqualified [[cpp/language/pointer|pointer types]] |
− | + | * {{lc|std::nullptr_t}} | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | {{ | + | |
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
− | + | ||
+ | On top of that, some headers also provide other enabled {{tt|std::hash}} specializations for library types (see [[#Specializations for library types|below]]). | ||
{{rrev|since=c++17|<!-- P0599R1, not a DR in P0636R2 --> | {{rrev|since=c++17|<!-- P0599R1, not a DR in P0636R2 --> | ||
− | + | For all {{tt|std::hash}} specializations provided by the standard library except the following, all their member functions are {{c/core|noexcept}}: | |
* {{ltt|cpp/utility/optional/hash|std::hash<std::optional>}} | * {{ltt|cpp/utility/optional/hash|std::hash<std::optional>}} | ||
* {{ltt|cpp/utility/variant/hash|std::hash<std::variant>}} | * {{ltt|cpp/utility/variant/hash|std::hash<std::variant>}} | ||
Line 121: | Line 87: | ||
}} | }} | ||
− | === | + | ===Specializations for library types=== |
{{dsc begin}} | {{dsc begin}} | ||
{{dsc inc|cpp/coroutine/coroutine_handle/dsc hash}} | {{dsc inc|cpp/coroutine/coroutine_handle/dsc hash}} | ||
Line 161: | Line 127: | ||
{{dsc end}} | {{dsc end}} | ||
− | + | ===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 denial-of-service attacks. | ||
+ | |||
+ | There is no specialization for C strings. {{c/core|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. | ||
+ | |||
+ | Additional specializations for {{lc|std::pair}} and the standard container types, as well as utility functions to compose hashes are available in [https://www.boost.org/doc/libs/release/libs/container_hash/doc/html/hash.html#ref {{tt|boost::hash}}]. | ||
===Example=== | ===Example=== | ||
{{example | {{example | ||
− | |||
|code= | |code= | ||
+ | #include <cstddef> | ||
#include <functional> | #include <functional> | ||
#include <iomanip> | #include <iomanip> | ||
Line 180: | Line 153: | ||
}; | }; | ||
− | // Before C++20 | + | // Before C++20. |
// bool operator==(const S& lhs, const S& rhs) | // bool operator==(const S& lhs, const S& rhs) | ||
// { | // { | ||
Line 186: | Line 159: | ||
// } | // } | ||
− | // | + | // Custom hash can be a standalone function object. |
struct MyHash | struct MyHash | ||
{ | { | ||
Line 197: | Line 170: | ||
}; | }; | ||
− | // | + | // Custom specialization of std::hash can be injected in namespace std. |
template<> | template<> | ||
struct std::hash<S> | struct std::hash<S> | ||
Line 213: | Line 186: | ||
std::string str = "Meet the new boss..."; | std::string str = "Meet the new boss..."; | ||
std::size_t str_hash = std::hash<std::string>{}(str); | std::size_t str_hash = std::hash<std::string>{}(str); | ||
− | std::cout << "hash(" << std::quoted(str) << ") = | + | std::cout << "hash(" << std::quoted(str) << ") =\t" << str_hash << '\n'; |
− | + | ||
S obj = {"Hubert", "Farnsworth"}; | S obj = {"Hubert", "Farnsworth"}; | ||
− | // | + | // Using the standalone function object. |
std::cout << "hash(" << std::quoted(obj.first_name) << ", " | std::cout << "hash(" << std::quoted(obj.first_name) << ", " | ||
− | << std::quoted(obj.last_name) << ") = | + | << std::quoted(obj.last_name) << ") =\t" |
− | << MyHash{}(obj) << " (using MyHash) or\n\t" | + | << MyHash{}(obj) << " (using MyHash) or\n\t\t\t\t" |
<< std::hash<S>{}(obj) << " (using injected specialization)\n"; | << std::hash<S>{}(obj) << " (using injected specialization)\n"; | ||
− | + | ||
// Custom hash makes it possible to use custom types in unordered containers. | // Custom hash makes it possible to use custom types in unordered containers. | ||
// The example will use the injected std::hash<S> specialization above, | // The example will use the injected std::hash<S> specialization above, | ||
Line 232: | Line 205: | ||
|p=true | |p=true | ||
|output= | |output= | ||
− | hash("Meet the new boss...") = | + | hash("Meet the new boss...") = 10656026664466977650 |
− | + | hash("Hubert", "Farnsworth") = 12922914235676820612 (using MyHash) or | |
− | hash("Hubert", "Farnsworth") = | + | 12922914235676820612 (using injected specialization) |
− | + | "Bender" "Rodriguez" | |
− | + | ||
"Turanga" "Leela" | "Turanga" "Leela" | ||
− | |||
"Hubert" "Farnsworth" | "Hubert" "Farnsworth" | ||
}} | }} | ||
Line 244: | Line 215: | ||
===Defect reports=== | ===Defect reports=== | ||
{{dr list begin}} | {{dr list begin}} | ||
+ | {{dr list item|wg=lwg|dr=2119|std=C++11|before=specializations for extended integer types were missing|after=provided}} | ||
{{dr list item|wg=lwg|dr=2148|std=C++11|before=specializations for enumerations were missing|after=provided}} | {{dr list item|wg=lwg|dr=2148|std=C++11|before=specializations for enumerations were missing|after=provided}} | ||
− | {{dr list item|wg=lwg|dr=2543|std=C++11|before={{tt|std::hash}} might not be SFINAE-friendly|after=made SFINAE-friendly | + | {{dr list item|wg=lwg|dr=2543|std=C++11|before={{tt|std::hash}} might not be SFINAE-friendly|after=made SFINAE-friendly}} |
{{dr list item|wg=lwg|dr=2817|std=C++11|before=specialization for {{lc|std::nullptr_t}} was missing|after=provided}} | {{dr list item|wg=lwg|dr=2817|std=C++11|before=specialization for {{lc|std::nullptr_t}} was missing|after=provided}} | ||
{{dr list end}} | {{dr list end}} | ||
{{langlinks|de|es|fr|it|ja|pt|ru|zh}} | {{langlinks|de|es|fr|it|ja|pt|ru|zh}} |
Latest revision as of 08:23, 6 June 2024
Defined in header <bitset>
|
||
Defined in header <coroutine>
|
||
Defined in header <chrono>
|
(since C++26) |
|
Defined in header <filesystem>
|
||
Defined in header <functional>
|
||
Defined in header <memory>
|
||
Defined in header <optional>
|
||
Defined in header <stacktrace>
|
||
Defined in header <string>
|
||
Defined in header <string_view>
|
||
Defined in header <system_error>
|
||
Defined in header <thread>
|
||
Defined in header <typeindex>
|
||
Defined in header <variant>
|
||
Defined in header <vector>
|
||
template< class Key > struct hash; |
(since C++11) | |
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.
Given a type Key
, each specialization std::hash<Key>
is either enabled or disabled :
- If
std::hash<Key>
is not provided by the program or the user, it is disabled. - Otherwise,
std::hash<Key>
is enabled if all following conditions are satisfied:
- All following requirements are satisfied:
- Hash (with
Key
as the function call argument type) - DefaultConstructible
- CopyAssignable
- Swappable
- Hash (with
- Given the following values:
- h, an object of type
std::hash<Key>
. - k1 and k2, objects of type
Key
.
- h, an object of type
- All following requirements are satisfied:
- If k1 == k2 is true, h(k1) == h(k2) is also true.
- Unless
std::hash<Key>
is a program-defined specialization, h(k1) will never throw an exception.
- Otherwise,
std::hash<Key>
is disabled.
Disabled specializations do not satisfy Hash, do not satisfy FunctionObject, and following values are all false:
- std::is_default_constructible<std::hash<Key>>::value
- std::is_copy_constructible<std::hash<Key>>::value
- std::is_move_constructible<std::hash<Key>>::value
- std::is_copy_assignable<std::hash<Key>>::value
- std::is_move_assignable<std::hash<Key>>::value
In other words, they exist, but cannot be used.
Nested types
|
(until C++20) |
[edit] Member functions
constructs a hash function object (public member function) | |
calculates the hash of the argument (public member function) |
[edit] Standard library specializations
Each header that declares the template std::hash
also provides enabled specializations of std::hash
for the following types:
- all cv-unqualified arithmetic types
- all cv-unqualified enumeration types
- all cv-unqualified pointer types
- std::nullptr_t
On top of that, some headers also provide other enabled std::hash
specializations for library types (see below).
For all
|
(since C++17) |
[edit] Specializations for library types
hash support for std::coroutine_handle (class template specialization) | |
(C++11) |
hash support for std::error_code (class template specialization) |
hash support for std::error_condition (class template specialization) | |
hash support for std::stacktrace_entry (class template specialization) | |
hash support for std::basic_stacktrace (class template specialization) | |
(C++17) |
hash support for std::optional (class template specialization) |
(C++17) |
hash support for std::variant (class template specialization) |
(C++17) |
hash support for std::monostate (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 strings (class template specialization) |
hash support for string views (class template specialization) | |
(C++11) |
hash support for std::vector<bool> (class template specialization) |
hash support for std::filesystem::path (class template specialization) | |
(C++11) |
hash support for std::thread::id (class template specialization) |
hash support for std::chrono::duration (class template specialization) | |
hash support for std::chrono::time_point (class template specialization) | |
(C++26) |
hash support for std::chrono::day (class template specialization) |
hash support for std::chrono::month (class template specialization) | |
(C++26) |
hash support for std::chrono::year (class template specialization) |
hash support for std::chrono::weekday (class template specialization) | |
hash support for std::chrono::weekday_indexed (class template specialization) | |
hash support for std::chrono::weekday_last (class template specialization) | |
hash support for std::chrono::month_day (class template specialization) | |
hash support for std::chrono::month_day_last (class template specialization) | |
hash support for std::chrono::month_weekday (class template specialization) | |
hash support for std::chrono::month_weekday_last (class template specialization) | |
hash support for std::chrono::year_month (class template specialization) | |
hash support for std::chrono::year_month_day (class template specialization) | |
hash support for std::chrono::year_month_day_last (class template specialization) | |
hash support for std::chrono::year_month_weekday (class template specialization) | |
hash support for std::chrono::year_month_weekday_last (class template specialization) | |
hash support for std::chrono::zoned_time (class template specialization) | |
hash support for std::chrono::leap_second (class template specialization) |
[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 denial-of-service attacks.
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.
Additional specializations for std::pair and the standard container types, as well as utility functions to compose hashes are available in boost::hash
.
[edit] Example
#include <cstddef> #include <functional> #include <iomanip> #include <iostream> #include <string> #include <unordered_set> struct S { std::string first_name; std::string last_name; bool operator==(const S&) const = default; // since C++20 }; // Before C++20. // bool operator==(const S& lhs, const S& rhs) // { // return lhs.first_name == rhs.first_name && lhs.last_name == rhs.last_name; // } // Custom hash can be a standalone function object. struct MyHash { std::size_t operator()(const S& s) const noexcept { 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); // or use boost::hash_combine } }; // Custom specialization of std::hash can be injected in namespace std. template<> struct std::hash<S> { std::size_t operator()(const S& s) const noexcept { 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); // or use boost::hash_combine } }; int main() { std::string str = "Meet the new boss..."; std::size_t str_hash = std::hash<std::string>{}(str); std::cout << "hash(" << std::quoted(str) << ") =\t" << str_hash << '\n'; S obj = {"Hubert", "Farnsworth"}; // Using the standalone function object. std::cout << "hash(" << std::quoted(obj.first_name) << ", " << std::quoted(obj.last_name) << ") =\t" << MyHash{}(obj) << " (using MyHash) or\n\t\t\t\t" << std::hash<S>{}(obj) << " (using injected specialization)\n"; // Custom hash makes it possible to use custom types in unordered containers. // The example will use the injected std::hash<S> specialization above, // to use MyHash instead, pass it as a second template argument. std::unordered_set<S> names = {obj, {"Bender", "Rodriguez"}, {"Turanga", "Leela"}}; for (auto const& s: names) std::cout << std::quoted(s.first_name) << ' ' << std::quoted(s.last_name) << '\n'; }
Possible output:
hash("Meet the new boss...") = 10656026664466977650 hash("Hubert", "Farnsworth") = 12922914235676820612 (using MyHash) or 12922914235676820612 (using injected specialization) "Bender" "Rodriguez" "Turanga" "Leela" "Hubert" "Farnsworth"
[edit] Defect reports
The following behavior-changing defect reports were applied retroactively to previously published C++ standards.
DR | Applied to | Behavior as published | Correct behavior |
---|---|---|---|
LWG 2119 | C++11 | specializations for extended integer types were missing | provided |
LWG 2148 | C++11 | specializations for enumerations were missing | provided |
LWG 2543 | C++11 | std::hash might not be SFINAE-friendly
|
made SFINAE-friendly |
LWG 2817 | C++11 | specialization for std::nullptr_t was missing | provided |