如何在 C++ 中的 std::unordered_map 中为用户定义类型实现自定义哈希函数

在本文中，我们将讨论如何在 C++ 的 std::unordered_map 中为用户定义类型实现自定义哈希函数。在讨论自定义哈希函数的实现之前，我们必须了解 C++ 中的 std::unordered_map。

什么是 std::unordered_map？

现代 C++ 编程中的 std::unordered_map 容器提供了一种管理键值对集合的有效方法。尽管它与内置类型配合良好，但将用户定义类型添加到 std::unordered_map 中可能会很困难，尤其是在创建正确的哈希函数时。

认识自定义哈希函数的价值

std::unordered_map 的核心是一个哈希方法，它能够以恒定时间根据键访问元素。然而，这种哈希过程的成功主要取决于精心设计的哈希算法。当使用用户定义类型时，内置的 C++ 默认哈希函数可能不合适，因为它可能无法充分捕获自定义类型的独特特征。在这种情况下，为特定类创建唯一的哈希函数变得至关重要。

默认哈希函数的挑战

• 默认情况下，如果您不提供自定义哈希函数，std::unordered_map 依赖于您的自定义类型的 std::hash 特化。
• 它通常不足以处理高级用户定义类型，即使它可能适用于文本或整数等基本类型。
• 使用无序映射可以带来速度优势，但这些优势可能会被哈希不充分导致的高碰撞率所抵消。

实现自定义哈希函数

以下步骤可用于在 C++ 中为用户定义类型创建自定义哈希函数

第 1 步：创建您的自定义类型

• 首先在自定义类型定义中封装我们希望存储在 std::unordered_map 中的数据结构。
• 这里可以使用任何用户定义类型，包括类和结构体。

第 2 步：哈希函数定义

• 接下来，指定自定义类型的哈希函数。
• 此函数应在接收您的自定义类型对象作为输入后返回一个 size_t 哈希值。
• 为了减少冲突，哈希函数应尝试将哈希值均匀分布在哈希表中。

哈希函数注意事项

• 确保确定性行为：哈希函数对于相同项应产生相同的值。
尽可能均匀地分布在整个 size_t 范围内。
• 平衡复杂性和性能：力求哈希函数在哈希质量和计算效率之间取得平衡。

第 3 步：允许 std::unordered_map 使用哈希函数

• 在声明 std::unordered_map 时，如果能将自定义哈希函数用作第三个模板参数，那将很有帮助。
• 这指示无序映射使用自定义哈希函数对自定义类型键进行哈希。

示例

让我们举个例子来说明 C++ 中 std::unordered_map 中用户定义类型的自定义哈希函数。

输出

说明

• 此示例使用 MyTypeHash，这是一个为 MyType 提供哈希函数的函数对象。对于 MyType 中的每个成员变量，operator() 函数使用 std::hash 方法获取哈希值，然后将其组合以获得最终哈希值。
• MyTypeHash 是要用于 MyType 类型的 键 的哈希函数，它在声明 std::unordered_map 时作为第三个模板参数提供。

实现自定义哈希函数的优势

• 性能
  在无序映射中，通过优化哈希值的分布，自定义哈希函数可以加速插入、删除和查找操作。
• 减少冲突
  自定义哈希函数通过减少冲突来保持基于哈希的数据结构的有效性，确保即使在处理大数据集时操作也能保持快速和可预测。
• 复杂性处理
  为了有效地哈希各种复杂和多样的数据，自定义哈希函数可以处理用户定义类型中的嵌套或复杂数据结构。
• 类型特异性
  开发人员可以通过根据其用户定义类型的独特属性和特征定制哈希过程来确保精确有效的哈希。

确定性行为

• 无论何时何地对对象进行哈希，自定义哈希函数都能通过产生相同的哈希值来确保确定性行为。

控制

• 开发人员可以通过实现自定义哈希函数来更好地控制基于哈希的数据结构的行为和性能。
• 它允许根据特定的应用程序要求进行优化和微调。