std::hash
定义于头文件 <functional>
|
||
template< class Key > struct hash; |
(C++11 起) | |
此模板的每个特化为启用(“无污染”)或为禁用(“中毒”)。
hash
函数模板的启用的特化定义一个实现散列函数的函数对象。此函数对象的实例满足散列 (Hash) 。特别是它们定义满足下列条件的 operator() :
- 接收
Key
类型的单个参数 - 返回表示参数散列值的 std::size_t 类型。
- 调用时不抛出异常。
- 对于二个相等的参数
k1
与k2
, std::hash<Key>()(k1) == std::hash<Key>()(k2) 。 - 对于二个相异而不相等的参数
k1
与k2
, std::hash<Key>()(k1) == std::hash<Key>()(k2) 的概率应非常小,接近 1.0/std::numeric_limits<std::size_t>::max() 。
库函数提供的 hash
的所有显式和部分特化可默认构造 (DefaultConstructible) 、可复制赋值 (CopyAssignable) 、可交换 (Swappable) 且可析构 (Destructible) 。用户提供的 hash
特化亦必须满足这些要求。
无序关联容器 std::unordered_set 、 std::unordered_multiset 、 std::unordered_map 、 std::unordered_multimap 以该模板 std::hash
的特化为默认散列函数。
对于每个既非库亦非用户提供的数据类型的 Key
启用特化的函数 std::hash<Key>
,特化存在且被禁用。被禁用特化不满足散列 (Hash) ,不满足函数对象 (FunctionObject) ,且下列值全为 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
换言之,它们存在但无法使用。
注解
除了上述指定的情况外,散列函数的实现方式是实现定义的。(比如, gcc 的实现)。需要注意,某些散列函数的实现过于简单,甚至是直接将对象映射至自身。这可能会造成严重的后果。换言之,这些散列函数可以用于无序关联容器,但它们不一定安全/抗碰撞。
散列函数仅要求在程序的单次执行中对同样的输入返回同样的结果;这允许避免碰撞拒绝服务攻击的加盐哈希。
没有对 C 字符串的特化。 std::hash<const char*> 产生指针值(内存地址)的散列值,它不检验任何字符数组的内容。
成员类型
|
(C++20 前) |
成员函数
构造散列函数对象 (公开成员函数) | |
计算参数的散列值 (公开成员函数) |
基本类型的标准特化
定义于头文件 <functional>
|
||
template<> struct hash<bool>; template<> struct hash<char>; |
||
在上述之外,标准库对所有(有作用域或无作用域)枚举类型提供特化。可以(但不要求)实现为 std::hash<std::underlying_type<Enum>::type> 。
标准库提供 std::hash
对 std::nullptr_t 和所有无 cv 限定算术类型(包含任何扩展整数类型)、所有枚举类型和所有指针类型的启用特化。
每个声明模板 std::hash
标准库头文件提供上述启用特化。这些头文件包括 <string>、 <system_error>、 <bitset>、 <memory>、 <typeindex>、 <vector>、 <thread>、 <optional> 、 <variant>、 <string_view> (C++17 起)、 <coroutine> (C++20 起)、 <stacktrace> (C++23 起) 。
此模板的标准库特化的所有成员函数均为 noexcept ,除了 std::hash<std::optional> 、 std::hash<std::variant> 和 std::hash<std::unique_ptr> 的成员函数。 |
(C++17 起) |
库类型的标准特化
(C++11)(C++20)(C++11)(C++11)(C++11)(C++17)(C++20)(C++17)(C++17)(C++17) |
string 的散列支持 (类模板特化) |
(C++11) |
std::error_code 的散列支持 (类模板特化) |
(C++11) |
std::bitset 的散列支持 (类模板特化) |
(C++11) |
std::unique_ptr 的散列支持 (类模板特化) |
(C++11) |
std::shared_ptr 的散列支持 (类模板特化) |
(C++11) |
std::type_index 的散列支持 (类模板特化) |
(C++11) |
std::vector<bool> 的散列支持 (类模板特化) |
(C++11) |
std::thread::id 的散列支持 (类模板特化) |
(C++17) |
特化 std::hash 算法 (类模板特化) |
(C++17) |
特化 std::hash 算法 (类模板特化) |
string_view 的散列支持 (类模板特化) | |
std::error_condition 的哈希支持 (类模板特化) | |
std::coroutine_handle 的散列支持 (类模板特化) | |
std::basic_stacktrace 的散列支持 (类模板特化) | |
std::stacktrace_entry 的散列支持 (类模板特化) |
注意:对 std::pair
和标准容器类型的特化,还有组合哈希的工具函数可用于 boost.hash
示例
#include <iostream> #include <iomanip> #include <functional> #include <string> #include <unordered_set> struct S { std::string first_name; std::string last_name; }; bool operator==(const S& lhs, const S& rhs) { return lhs.first_name == rhs.first_name && lhs.last_name == rhs.last_name; } // 自定义散列函数能是独立函数对象: struct MyHash { 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); // 或使用 boost::hash_combine (见讨论) } }; // std::hash 的自定义特化能注入 namespace std 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); // 或使用 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) << ") = " << str_hash << '\n'; S obj = { "Hubert", "Farnsworth"}; // 使用独立的函数对象 std::cout << "hash(" << std::quoted(obj.first_name) << ", " << std::quoted(obj.last_name) << ") = " << MyHash{}(obj) << " (using MyHash)\n" << std::setw(31) << "or " << std::hash<S>{}(obj) << " (using injected std::hash<S> specialization)\n"; // 自定义散列函数令在无序容器中使用自定义类型可行 // 此示例将使用注入的 std::hash 特化, // 若要使用 MyHash 替代,则将其作为第二模板参数传递 std::unordered_set<S> names = {obj, {"Bender", "Rodriguez"}, {"Leela", "Turanga"} }; for(auto& s: names) std::cout << std::quoted(s.first_name) << ' ' << std::quoted(s.last_name) << '\n'; }
可能的输出:
hash("Meet the new boss...") = 1861821886482076440 hash("Hubert", "Farnsworth") = 17622465712001802105 (using MyHash) or 17622465712001802105 (using injected std::hash<S> specialization) "Turanga" "Leela" "Bender" "Rodriguez" "Hubert" "Farnsworth"
缺陷报告
下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。
DR | 应用于 | 出版时的行为 | 正确行为 |
---|---|---|---|
LWG 2148 | C++11 | 缺失对枚举的特化 | 已提供 |
LWG 2543 | C++11 | hash 可能不是 SFINAE 友好的
|
通过禁用的特化使之为 SFINAE 友好 |
LWG 2817 | C++11 | 缺失对 nullptr_t 的特化
|
已提供 |