std::hash

来自cppreference.com
< cpp‎ | utility
 
C++
 
工具库
语言支持
类型支持（基本类型、RTTI）
库功能特性测试宏 (C++20)
动态内存管理
程序工具
协程支持 (C++20)
变参数函数
(C++20)
(C++26)
(C++11)
(C++20)
调试支持
(C++26)
(C++26)
(C++26)
三路比较
(C++20)(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)
(C++20)   
(C++20)(C++20)(C++20)
(C++20)(C++20)(C++20)
通用工具
日期和时间
函数对象
格式化库 (C++20)
hash
(C++11)
关系运算符 (C++20 中弃用)
整数比较函数
(C++20)(C++20)(C++20)   
(C++20)
交换与类型运算
(C++20)
(C++14)
(C++11)
(C++23)
(C++11)
(C++23)
(C++11)
(C++11)
(C++17)
常用词汇类型
(C++11)
(C++17)
(C++17)
(C++17)
(C++11)
(C++11)
(C++17)
(C++17)
(C++23)
初等字符串转换
(C++17)
(C++17)
(C++17)

 
std::hash
 
在标头 <bitset> 定义
在标头 <coroutine> 定义
在标头 <chrono> 定义
(C++26 起)
在标头 <filesystem> 定义
在标头 <functional> 定义
在标头 <memory> 定义
在标头 <optional> 定义
在标头 <stacktrace> 定义
在标头 <string> 定义
在标头 <string_view> 定义
在标头 <system_error> 定义
在标头 <thread> 定义
在标头 <typeindex> 定义
在标头 <variant> 定义
在标头 <vector> 定义
template< class Key >
struct hash;
 (C++11 起)

无序关联容器 std::unordered_set、std::unordered_multiset、std::unordered_map、std::unordered_multimap 以模板 std::hash 的特化为默认散列函数。

给定类型 Key，每个特化 std::hash<Key> 要么被启用，要么被禁用：

  • 如果程序和用户都没有提供 std::hash<Key>，那么它被禁用。
  • 否则，std::hash<Key> 在满足以下所有条件时被启用：
  • 满足以下所有要求：
  • 给定以下值：
  • h，std::hash<Key> 类型的对象。
  • k1 和 k2，Key 类型的对象。
满足以下所有要求：
  • 如果 k1 == k2 是 true，那么 h(k1) == h(k2) 也是 true。
  • 除非 std::hash<Key> 是由程序定义的特化，那么 h(k1) 不会抛出异常。
  • 否则，std::hash<Key> 被禁用。

被禁用的特化不满足散列 (Hash) ，不满足函数对象 (FunctionObject) ，并且下列值都是 false：

也就是说，它们存在但无法使用。

嵌套类型

名字 定义
argument_type (C++17 中弃用) Key
result_type (C++17 中弃用) std::size_t
(C++20 前)

成员函数

 构造散列函数对象
(公开成员函数)
计算实参的散列值
(公开成员函数)

标准库特化

每个声明了模板 std::hash 的标头也会为以下类型提供 std::hash 的被启用特化：

此外，部分标头也会为库类型提供 std::hash 的其他被启用特化（见下文）。

对于标准库提供的除以下特化外的 std::hash 特化，它们的成员函数都是 noexcept 的：

(C++26 起)
 (C++17 起)

库类型特化

(C++20)
 std::coroutine_handle 的散列支持
(类模板特化)
(C++11)
 std::error_code 的散列支持
(类模板特化)
(C++17)
 std::error_condition 的散列支持
(类模板特化)
(C++23)
 std::stacktrace_entry 的散列支持
(类模板特化)
(C++23)
 std::basic_stacktrace 的散列支持
(类模板特化)
(C++17)
 std::optional 的散列支持
(类模板特化)
(C++17)
 std::variant 的散列支持
(类模板特化)
(C++17)
 std::monostate 的散列支持
(类模板特化)
(C++11)
 std::bitset 的散列支持
(类模板特化)
(C++11)
 std::unique_ptr 的散列支持
(类模板特化)
(C++11)
 std::shared_ptr 的散列支持
(类模板特化)
(C++11)
 std::type_index 的散列支持
(类模板特化)
(C++11)
 字符串的散列支持
(类模板特化)
(C++17)(C++17)(C++20)(C++17)(C++17)
 字符串视图的散列支持
(类模板特化)
(C++11)
 std::vector<bool> 的散列支持
(类模板特化)
(C++17)
 std::filesystem::path 的散列支持
(类模板特化)
(C++11)
 std::thread::id 的散列支持
(类模板特化)
(C++26)
 std::chrono::duration 的散列支持
(类模板特化)
(C++26)
 std::chrono::time_point 的散列支持
(类模板特化)
(C++26)
 std::chrono::day 的散列支持
(类模板特化)
(C++26)
 std::chrono::month 的散列支持
(类模板特化)
(C++26)
 std::chrono::year 的散列支持
(类模板特化)
(C++26)
 std::chrono::weekday 的散列支持
(类模板特化)
(C++26)
 std::chrono::weekday_indexed 的散列支持
(类模板特化)
(C++26)
 std::chrono::weekday_last 的散列支持
(类模板特化)
(C++26)
 std::chrono::month_day 的散列支持
(类模板特化)
(C++26)
 std::chrono::month_day_last 的散列支持
(类模板特化)
(C++26)
 std::chrono::month_weekday 的散列支持
(类模板特化)
(C++26)
 std::chrono::month_weekday_last 的散列支持
(类模板特化)
(C++26)
 std::chrono::year_month 的散列支持
(类模板特化)
(C++26)
 std::chrono::year_month_day 的散列支持
(类模板特化)
(C++26)
 std::chrono::year_month_day_last 的散列支持
(类模板特化)
(C++26)
 std::chrono::year_month_weekday 的散列支持
(类模板特化)
(C++26)
 std::chrono::year_month_weekday_last 的散列支持
(类模板特化)
(C++26)
 std::chrono::zoned_time 的散列支持
(类模板特化)
(C++26)
 std::chrono::leap_second 的散列支持
(类模板特化)

注解

除了上述指定的情况外，散列函数的实现方由实现定义。（比如，gcc 的实现）。需要注意，某些散列函数的实现过于简单，甚至是直接将对象映射至自身。这可能会造成严重的后果。换言之，这些散列函数可以用于无序关联容器，但它们不一定安全/抗碰撞。

散列函数仅要求在程序的单次执行中对同样的输入返回同样的结果；这允许采用避免碰撞拒绝服务攻击的加盐散列。

没有对 C 字符串的特化。std::hash<const char*> 产生指针值（内存地址）的散列值，它不检验任何字符数组的内容。

对 std::pair 和标准容器类型的特化，还有组合散列的工具函数可以参考 boost.hash。

示例

运行此代码
#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; // C++20 起
};
 
// C++20 前
// 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 的自定义特化能注入命名空间 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); // 或者使用 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) << "（使用 MyHash）\n" << std::setw(31) << "或 "
              << std::hash<S>{}(obj) << "（使用注入的特化）\n";
 
    // 自定义散列函数令在无序容器中使用自定义类型可行。
    // 此示例将使用注入的 std::hash 特化，
    // 如果要使用 MyHash 替代，那么将它作为第二模板参数传递。
    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';
}

可能的输出： 

hash("Meet the new boss...") = 1861821886482076440
hash("Hubert", "Farnsworth") = 17622465712001802105（使用 MyHash）
                            或 17622465712001802105（使用注入的特化） 
"Turanga" "Leela"
"Bender" "Rodriguez"
"Hubert" "Farnsworth"

缺陷报告

下列更改行为的缺陷报告追溯地应用于以前出版的 C++ 标准。

缺陷报告 应用于 出版时的行为 正确行为
LWG 2119 C++11 缺失扩展整数类型的特化 已提供
LWG 2148 C++11 缺失对枚举的特化 已提供
LWG 2543 C++11 std::hash 可能不是 SFINAE 友好的 使之为 SFINAE 友好
LWG 2817 C++11 缺失对 std::nullptr_t 的特化 已提供
来自“https://zh.cppreference.com/mwiki/index.php?title=cpp/utility/hash&oldid=91631”