C / C++ / 系统课时

自定义类型怎样参与哈希

自定义类型怎样参与哈希

当业务键由多个字段组成,例如“租户 ID + 用户名”时,直接把它作为 unordered_map 的键,需要同时告诉容器两件事:怎样计算哈希值,以及怎样判断两个键相等。本篇用一个完整示例实现这两个规则,并说明它们必须保持一致。

学习目标

  • 为自定义键类型编写可用的哈希函数
  • 为 unordered 容器提供一致的相等比较规则
  • 理解“相等键必须得到相同哈希值”的约束

unordered 容器需要两套规则

查找一个键时,unordered 容器会先调用哈希函数,把键映射到某个桶,再在桶内用相等比较确认具体元素。因此哈希负责缩小搜索范围,相等比较负责给出最终判断。

对任意两个键 a 和 b,如果相等比较认为它们相等,那么哈希函数必须保证 hash(a) == hash(b)。反过来不要求成立:不同键出现相同哈希值是允许的,容器会继续用相等比较解决冲突。

为组合键实现哈希与相等比较

下面把 tenantId 和 username 一起定义为键。哈希函数分别计算两个字段的哈希值后再组合,相等比较也同时检查这两个字段。

cpp
#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';
}

预期输出

text
Alice profile: enabled
Unknown found: false

这里没有依赖容器的遍历顺序,因此输出稳定。unordered_map 的整体迭代顺序本来就没有排序保证,不应把顺序写进业务逻辑。

为什么哈希规则必须和相等规则一致

假设相等比较只看 tenantId,却让哈希函数同时使用 tenantId 和 username。那么 {7, "alice"} 与 {7, "bob"} 会被判定为相等,却可能进入不同的桶,从而破坏 unordered 容器要求“等价键具有相同哈希值”的契约,查找结果也可能不符合预期。

更常见的错误是相等比较做了大小写忽略,而哈希仍直接使用原始字符串。如果业务规定 "Alice" 与 "alice" 是同一个键,那么比较和哈希都必须采用同样的规范化规则。

什么时候应该自定义键

当多个字段共同形成自然唯一标识,并且代码经常按这组字段做哈希查找时,自定义键通常比拼接字符串更清晰。它保留了字段类型,也避免分隔符冲突和重复解析。

哈希质量会影响性能,但正确性优先于“看起来随机”。先确保所有参与相等判断的字段都以一致规则进入哈希,再根据真实数据分布评估冲突情况;没有测量依据时,不必自行设计复杂哈希算法。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

自定义类型怎样参与哈希

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通