std::hash

来自cppreference.com
< cpp‎ | utility
定义于头文件 <functional>
template< class Key >
struct hash;
(C++11 起)

此模板的每个特化为启用(“无污染”)或为禁用(“中毒”)。对于每个既非库亦非用户提供的数据类型的Key启用特化的函数 std::hash<Key>, 特化存在且被禁用。被禁用特化不满足哈希 (Hash) ,不满足函数对象 (FunctionObject) ,且 std::is_default_constructible_vstd::is_copy_constructible_vstd::is_move_constructible_vstd::is_copy_assignable_vstd::is_move_assignable_v 全为 false 。换言之,它们存在但无法使用。

(C++17 起)

hash 函数模板启用的特化 (C++17 起)定义一个实现哈希函数的函数对象。此函数对象的实例满足哈希 (Hash) 。特别是它们定义满足下列条件的 operator()

1. 接收 Key 类型的单个参数

2. 返回表示参数哈希值的 size_t 类型。

3. 调用时不抛出异常。

4. 对于二个相等的参数 k1k2std::hash<Key>()(k1) == std::hash<Key>()(k2)

5. 对于二个相异而不相等的参数 k1k2std::hash<Key>()(k1) == std::hash<Key>()(k2) 的概率应非常小,接近 1.0/std::numeric_limits<size_t>::max()

库函数提供的 hash 的所有显式和部分特化可复制构造 (DefaultConstructible) 、可复制赋值 (CopyAssignable) 、可交换 (Swappable) 且可析构 (Destructible) 。用户提供的 hash 特化亦必须满足这些要求。

无序关联容器 std::unordered_setstd::unordered_multisetstd::unordered_mapstd::unordered_multimap 以该模板 std::hash 的特化为默认哈希函数。

目录

[编辑] 注意

实际的哈希函数是实现定义的,且不要求满足任何其他质量标准,除了上述指定者。值得注意的是,一些实现使用映射整数到其自身的平凡(自身)哈希函数。换言之,这些哈希函数设计为与无序关联容器一同工作,然而不是加密哈希之类的哈希函数。

哈希函数仅要求在程序的单次执行中对同样的输入返回同样的结果;这允许避免碰撞 DoS 攻击的加盐哈希。 (C++14 起)

没有对 C 字符串的特化。 std::hash<const char*> 产生指针值(内存地址)的哈希,它不检验任何字符数组的内容。

[编辑] 成员类型

成员类型 定义
argument_type(C++17 中过时) Key
result_type(C++17 中过时) std::size_t

[编辑] 成员函数

构造哈希函数对象
(公开成员函数)
计算参数的哈希
(公开成员函数)

[编辑] 基本类型的标准特化

定义于头文件 <functional>
template<> struct hash<bool>;

template<> struct hash<char>;
template<> struct hash<signed char>;
template<> struct hash<unsigned char>;
template<> struct hash<char16_t>;
template<> struct hash<char32_t>;
template<> struct hash<wchar_t>;
template<> struct hash<short>;
template<> struct hash<unsigned short>;
template<> struct hash<int>;
template<> struct hash<unsigned int>;
template<> struct hash<long>;
template<> struct hash<long long>;
template<> struct hash<unsigned long>;
template<> struct hash<unsigned long long>;
template<> struct hash<float>;
template<> struct hash<double>;
template<> struct hash<long double>;

template< class T > struct hash<T*>;

在上述之外,标准库对所有(有作用域或无作用域)枚举类型提供特化。可以(但不要求)实现为 std::hash<std::underlying_type<Enum>::type>

(C++14 起)

每个声明模板 std::hash 的标准库头文件提供 std::hashstd::nullptr t 和所有无 cv 限定算术类型(包含任何扩展整数类型)、所有枚举类型和所有指针类型的启用特化。

此模板的标准库特化的所有函数均为 noexcept ,除了 std::hash<std::optional>std::hash<std::variant>std::hash<std::unique_ptr> 的成员函数

(C++17 起)

[编辑] 库类型的标准特化

字符串的哈希支持
(类模板特化) [编辑]
std::error_code 的哈希支持
(类模板特化) [编辑]
std::bitset 的哈希支持
(类模板特化) [编辑]
std::unique_ptr 的哈希支持
(类模板特化) [编辑]
std::shared_ptr 的哈希支持
(类模板特化) [编辑]
std::type_index 的哈希支持
(类模板特化) [编辑]
std::vector<bool> 的哈希支持
(类模板特化)
std::thread::id 的哈希支持
(类模板特化)
特化 std::hash 算法
(类模板特化) [编辑]
特化 std::hash 算法
(类模板特化) [编辑]
字符串视图的哈希支持
(类模板特化) [编辑]
std::error_condition 的哈希支持
(类模板特化) [编辑]

注意:对 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                           or "
               << std::hash<S>{}(obj) << " (using std::hash) " << '\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 std::hash) 
"Leela" "Turanga"
"Bender" "Rodriguez"
"Hubert" "Farnsworth"