c++中std：：hash以及万能hash的使用方式

前言std::hash是标准库为无序容器提供的默认哈希函数对象。它对整数、浮点、指针、std::string、std::string_view等类型有特化对用户自定义类型则没有——想让自定义类型进std::unordered_map要么提供自定义的哈希仿函数要么为它特化std::hash。所谓「万能 hash」并不是标准里的术语通常指两种写法一种是把多个字段的哈希值组合起来的通用函数另一种是能给任意「可哈希类型」生成哈希的模板。它们解决的是同一个问题自定义类型往往有多个成员而相等比较会用到所有成员哈希也必须覆盖所有成员。常见误解有三个。第一以为std::hash的输出在不同程序运行之间是稳定的于是把哈希值存进数据库当 ID。第二以为std::hashconst char*会对字符串内容求哈希实际它哈希的是指针地址。第三只对结构体的一个字段求哈希而operator比较了全部字段导致「相等的对象哈希值不同」直接违反无序容器的前提。本文先讲std::hash的契约再给自定义类型的特化写法然后给出字段组合的通用模板最后说明质量与安全边界。一、std::hash 的契约标准对std::hashKey的要求可以概括为四条默认构造、可拷贝、可调用、对相等的键必须返回相等的值。它不要求不同键返回不同值哈希碰撞是允许的也不要求跨实现、跨版本、跨进程稳定。// 适用于 C17#include cstddef#include functional#include iostream#include stringint main() {std::hashstd::string hs;std::hashint hi;const std::size_t a hs(hello);const std::size_t b hi(42);std::cout a b \n;}输出类型是std::size_t。具体数值由实现决定标准没有规定算法也没有规定不同字符串是否会碰撞。某些实现会对字符串哈希加随机种子用来缓解哈希碰撞攻击这意味着同一个字符串在不同进程里可能得到不同结果。所以哈希值只能用于当前进程内的容器不能持久化也不能跨进程比较。标准库为以下类型提供了std::hash特化不完全列举所有整型、bool、char系列、浮点类型、指针类型、std::string、std::string_viewC17、std::u16string等。对枚举类型C14 起标准保证std::hash可用底层按整型处理更早的标准里这属于实现提供。对std::pair、std::tuple、std::vector标准没有提供哈希需要自己写。二、为自定义类型特化 std::hash假设有一个二维点相等比较看两个坐标// 适用于 C17#include cstddef#include functionalstruct Point {int x 0;int y 0;bool operator(const Point other) const {return x other.x y other.y;}};namespace std {template struct hashPoint {std::size_t operator()(const Point p) const noexcept {const std::size_t hx std::hashint{}(p.x);const std::size_t hy std::hashint{}(p.y);return hx ^ (hy 0x9e3779b9u (hx 6) (hx 2));}};} // namespace std规则很明确特化必须写在namespace std里模板参数写具体的用户类型并且要在该类型第一次被用作std::hash实参之前出现。放在头文件里、紧跟在类型定义之后是最稳妥的做法。noexcept不是标准强制要求但哈希函数在无序容器里会被频繁调用不抛异常能让实现少一层考虑。0x9e3779b9是常用的混合常数来自黄金比例它的作用是把两个哈希值的位打散减少简单异或带来的规律性。这个常数不是标准的一部分只是工程惯例。还有一条容易忽略的纪律如果operator比较了x和y哈希就必须同时覆盖x和y只哈希x会让(1,2)和(1,3)得到相同哈希这不算错只是碰撞但如果反过来operator只看x哈希却混入了y那么两个相等对象的哈希可能不同直接违反契约容器行为将不可靠。三、组合多个字段的通用写法字段一多手写混合表达式既啰嗦又容易漏。C17 的折叠表达式可以把「对每个字段做一次 combine」写成一行// 适用于 C17#include cstddef#include functional#include string#include utilitytemplate class Tinline void hash_combine(std::size_t seed, const T value) {seed ^ std::hashT{}(value) 0x9e3779b9u (seed 6) (seed 2);}template class... Tsstd::size_t hash_all(const Ts... values) {std::size_t seed 0;(hash_combine(seed, values), ...); // 逗号折叠从左到右依次执行return seed;}struct Person {std::string name;int age 0;bool operator(const Person other) const {return name other.name age other.age;}};struct PersonHash {std::size_t operator()(const Person p) const {return hash_all(p.name, p.age);}};hash_all要求每个参数的类型都有可用的std::hash特化。const char*虽然能编译但哈希的是地址而不是内容传字符串时要用std::string或std::string_view。折叠表达式里的逗号运算符保证从左到右求值seed被依次更新。这种组合方式不是密码学哈希碰撞分布也谈不上最优但对unordered_map足够。若对分布有更高要求可以换用更复杂的混合函数或使用成熟的哈希库具体接口以对应库的官方文档为准。四、给 unordered_map 配自定义哈希最直接的用法是把哈希仿函数作为第三个模板参数相等比较用默认的std::equal_to它调用operator// 适用于 C17#include string#include unordered_map#include utilitystruct PairHash {template class A, class Bstd::size_t operator()(const std::pairA, B p) const {return hash_all(p.first, p.second);}};std::unordered_mapstd::pairint, int, std::string, PairHash grid;这里不需要特化std::hashstd::pairint,int因为容器显式接收了PairHash。两种方式的选择标准是如果这个类型在项目里到处都要哈希特化std::hash更省事如果只是某个容器需要特殊处理传仿函数更局部也不会污染std命名空间。C20 起还可以用std::hash对std::pair的提案吗标准至今没有为std::pair提供std::hash特化仍然需要自己写。不要凭印象假设它有。五、质量与安全边界std::hash不是加密哈希不能用它存密码、做文件校验和、或生成防篡改标识。它没有抗碰撞性保证攻击者可以构造大量同哈希的键让unordered_map退化成链表这就是哈希碰撞拒绝服务。标准库实现可能会对字符串哈希加随机化来缓解但这不是所有类型、所有实现都有的保证。另外哈希值不是 ID。它可能碰撞可能随实现版本变化也可能因为随机种子在每次运行时不同。要稳定标识用内容本身或单独生成的 UUID。常见坑点❌operator比较全部字段哈希只算一个字段还不够——不这只会增加碰撞尚可接受真正致命的是反过来相等比较只看部分字段哈希却混入了其他字段。✅ 哈希覆盖的字段集合必须与operator完全一致。❌ 用std::unordered_mapconst char*, int以为按字符串内容查找。✅ 用std::string或std::string_view作键指针键哈希的是地址。❌ 把std::hashstd::string{}(s)的结果存进数据库当唯一标识。✅ 用字符串本身或另行生成的稳定 ID哈希值不保证跨进程稳定。❌ 在类型已经被用作std::hash实参之后才写特化。✅ 特化紧跟在类型定义之后放在头文件里先于任何使用。❌ 组合哈希只写h1 ^ h2(a,b)与(b,a)恒等。✅ 用带移位和常数的 combine打破对称性。❌ 在namespace mylib里特化hashMyType编译器找不到。✅ 特化必须位于namespace std。❌ 用std::hash做密码存储或完整性校验。✅ 密码用专门的密钥派生函数校验和用 SHA-2 等密码学哈希库。总结主题结论契约相等键必须同哈希不保证无碰撞、不保证跨进程稳定自定义类型在namespace std内特化覆盖全部参与相等的字段多字段组合用 combine 函数加折叠表达式避免简单异或容器用法可传自定义仿函数也可特化std::hash安全性非密码学哈希不可用于密码、校验和、持久 IDstd::hash的用法本身不复杂真正的风险在于把它当成「稳定摘要」或「唯一标识」。记住它只是当前进程内无序容器的一个分布函数契约只有「相等则同哈希」其余一概不保证。把字段覆盖齐、把const char*换成std::string、把哈希值留在内存里三点做到就不会出大问题。