C / C++ / 系统课时
自定义类型怎样参与哈希
自定义类型怎样参与哈希
当业务键由多个字段组成,例如“租户 ID + 用户名”时,直接把它作为 unordered_map 的键,需要同时告诉容器两件事:怎样计算哈希值,以及怎样判断两个键相等。本篇用一个完整示例实现这两个规则,并说明它们必须保持一致。
学习目标
- 为自定义键类型编写可用的哈希函数
- 为 unordered 容器提供一致的相等比较规则
- 理解“相等键必须得到相同哈希值”的约束
unordered 容器需要两套规则
查找一个键时,unordered 容器会先调用哈希函数,把键映射到某个桶,再在桶内用相等比较确认具体元素。因此哈希负责缩小搜索范围,相等比较负责给出最终判断。
对任意两个键 a 和 b,如果相等比较认为它们相等,那么哈希函数必须保证 hash(a) == hash(b)。反过来不要求成立:不同键出现相同哈希值是允许的,容器会继续用相等比较解决冲突。
为组合键实现哈希与相等比较
下面把 tenantId 和 username 一起定义为键。哈希函数分别计算两个字段的哈希值后再组合,相等比较也同时检查这两个字段。
#include <cstddef>
#include <functional>
#include <iostream>
#include <string>
#include <unordered_map>
struct UserKey {
int tenantId;
std::string username;
};
struct UserKeyHash {
std::size_t operator()(const UserKey& key) const {
const std::size_t h1 = std::hash<int>{}(key.tenantId);
const std::size_t h2 = std::hash<std::string>{}(key.username);
// 组合两个字段,避免只使用其中一个字段造成大量冲突。
return h1 ^ (h2 + 0x9e3779b9u + (h1 << 6) + (h1 >> 2));
}
};
struct UserKeyEqual {
bool operator()(const UserKey& left, const UserKey& right) const {
return left.tenantId == right.tenantId
&& left.username == right.username;
}
};
int main() {
std::unordered_map<
UserKey,
std::string,
UserKeyHash,
UserKeyEqual
> profiles;
profiles.emplace(UserKey{7, "alice"}, "enabled");
profiles.emplace(UserKey{7, "bob"}, "disabled");
profiles.emplace(UserKey{8, "alice"}, "pending");
const UserKey target{7, "alice"};
const auto it = profiles.find(target);
if (it != profiles.end()) {
std::cout << "Alice profile: " << it->second << '\n';
}
const UserKey unknown{7, "charlie"};
std::cout << std::boolalpha
<< "Unknown found: "
<< (profiles.find(unknown) != profiles.end())
<< '\n';
}预期输出
Alice profile: enabled
Unknown found: false这里没有依赖容器的遍历顺序,因此输出稳定。unordered_map 的整体迭代顺序本来就没有排序保证,不应把顺序写进业务逻辑。
为什么哈希规则必须和相等规则一致
假设相等比较只看 tenantId,却让哈希函数同时使用 tenantId 和 username。那么 {7, "alice"} 与 {7, "bob"} 会被判定为相等,却可能进入不同的桶,从而破坏 unordered 容器要求“等价键具有相同哈希值”的契约,查找结果也可能不符合预期。
更常见的错误是相等比较做了大小写忽略,而哈希仍直接使用原始字符串。如果业务规定 "Alice" 与 "alice" 是同一个键,那么比较和哈希都必须采用同样的规范化规则。
什么时候应该自定义键
当多个字段共同形成自然唯一标识,并且代码经常按这组字段做哈希查找时,自定义键通常比拼接字符串更清晰。它保留了字段类型,也避免分隔符冲突和重复解析。
哈希质量会影响性能,但正确性优先于“看起来随机”。先确保所有参与相等判断的字段都以一致规则进入哈希,再根据真实数据分布评估冲突情况;没有测量依据时,不必自行设计复杂哈希算法。