如何为用户定义的类型特化std::hash<T>？

Question

如何为用户定义的类型特化std::hash<T>？

c++c++11unordered-mapunordered-sethash-function

20

问题

对于用户定义类型，其所有成员数据类型都已具有良好的std::hash专业化，作为std::unordered_map或std::unordered_set的第三个模板参数使用什么样的std::hash专业化效果最佳？

对于这个问题，我定义"好"是指易于实现和理解，效率合理，并且不太可能产生哈希表冲突。好的定义不包括任何关于安全性的声明。

可通过Google搜索获得的信息

目前，“std hash specialization” 的谷歌搜索结果的前两个链接是StackOverflow的两个问题。

第一个问题How to specialize std::hash::operator() for user-defined type in unordered containers?，涉及是否可以打开std名称空间并添加模板专业化。

第二个问题How to specialize std::hash for type from other library，本质上解决了同样的问题。

这就留下了当前的问题。假设C++标准库的实现为原始类型和标准库中的类型定义了哈希函数，那么一种简单而有效的方式来为用户定义类型进行std::hash专业化是什么？是否有一种将标准库实现提供的哈希函数组合在一起的好方法？

(由于dyp的编辑) 另一个StackOverflow问题讨论了如何组合一对哈希函数。

其他谷歌搜索结果没有更多帮助。

这篇 Dr. Dobbs文章指出，两个满意哈希的异或将产生一个新的满意哈希。

这篇文章似乎具备专业知识并暗示了许多事情，但是细节不够充分。它在第一个示例的简要评论中与Dr. Dobbs的文章相矛盾，称使用异或运算符将哈希函数组合起来会得到一个弱的哈希函数。

因为异或应用于任何两个相等的值都会得到0，我能理解为什么单独使用异或会很弱。

元问题

一个合理的答案可以解释为什么这个问题无效并且不能被普遍回答，这也是受欢迎的。

- Praxeolitic

2

也许你应该在列表中加入关于合并哈希的问题？ - dyp

1

嗯，我不确定。那个答案是针对两个值的，我不知道当递归地应用于N个值时算法的质量是否足够好。即使使用标准设施，似乎元组也不可哈希，参见https://dev59.com/MGw05IYBdhLWcg3wpTcV - dyp

3

我们正在标准中努力解决这个问题，但目前还比较棘手。http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html提供了一个不错的方法，但会稍微增加编译器优化的难度。希望我们能在接下来的六个月内（抱歉，标准进展缓慢）解决这个问题，并在下一个试验性版本中加入相关内容。 - Jeffrey Yasskin

3

这里有一个公共领域的部分实现，它是 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html 的一部分，可以在这里找到：https://github.com/HowardHinnant/hash_append/blob/master/hash_append.h，还有很多使用它的示例代码在这里：https://github.com/HowardHinnant/hash_append。虽然你无法完全实现它，这就是为什么需要标准化。但是我目前正在一个真实的项目中很好地使用它。它消除了组合步骤，并允许您选择和轻松更改用于原始类型的哈希算法。 - Howard Hinnant

1

可能是字符串的好哈希函数的重复问题。 - M.J. Rayburn

显示剩余3条评论

4个回答

3

首先，Dr. Dobbs的文章认为两个满意哈希的XOR将产生一个满意的哈希是错误的。这是一种制造劣质哈希的好方法。通常，要创建一个好的哈希，您需要将对象分解为子对象，每个子对象都有一个好的哈希，并组合哈希。其中一种简单的方法是类似于：

class HashAccumulator
{
    size_t myValue;
public:
    HashAccumulator() : myValue( 2166136261U ) {}
    template <typename T>
    HashAccumulator& operator+=( T const& nextValue )
    {
        myValue = 127U * myValue + std::hash<T>( nextHashValue );
    }
    HashAccumulator operator+( T const& nextHashValue ) const
    {
        HashAccumulator results( *this );
        results += nextHashValue;
        return results;
    }
};

这个设计可以让你在处理值序列时使用std::accumulate。当然，前提是所有的子类型都有良好的std::hash实现。对于基本类型和字符串，这是必备的；对于自定义类型，只需按照上述规则递归应用，并专门为其子类型使用HashAccumulator进行特化。对于标准容器存储基本类型，稍微有点棘手，因为你不能（至少正式上）对标准库中的类型进行特化，你可能需要创建一个直接使用HashAccumulator的类，并明确指定如果需要对这样一个容器进行哈希。

- James Kanze

请参考此答案，了解为什么XOR不是一种很好的组合哈希的方式：https://dev59.com/RG025IYBdhLWcg3wpHl_#27952689 - Raedwald

2

您的操作需要：

返回 size_t 类型的值
与 == 运算符保持一致。
对于不相等的值，具有较低的哈希碰撞概率。

没有明确要求哈希值在 size_t 整数范围内均匀分布。cppreference.com 的说明如下：

一些标准库实现使用简单（恒等）哈希函数将整数映射到自身

避免哈希碰撞以及上述弱点意味着，针对您的类型的 std::hash 特化永远不应该仅使用（快速的）位异或（^）来组合数据成员的子哈希。考虑以下示例：

 struct Point {
    uint8_t x;
    uint8_t y;
 };

 namespace std {
    template<>
    struct hash< Point > {
       size_t operator()(const Point &p) const {
          return hash< uint8_t >(p.x) ^ hash< uint8_t >(p.y);
       }
    };
 }

p.x的哈希值将在[0,255]范围内，p.y的哈希值也是如此。因此，Point的哈希值也将在[0,255]范围内，有256（=2^8）个可能的值。有256*256（=2^16）个唯一的Point对象（std::size_t通常支持2^32或2^64个值）。因此，对于一个“好”的哈希函数，哈希冲突的概率应该约为2^(-16)。我们的函数给出的哈希冲突概率略低于2^(-8)。这很糟糕：我们的哈希只提供了8位信息，但一个好的哈希应该提供16位信息。

如果您的数据成员的哈希函数仅提供std::size_t范围内的低位哈希值，则必须在组合它们之前“移位”组件哈希的位，以便它们各自贡献独立的位信息。左移看起来很简单。

       return (hash< uint8_t >(p.x) << 8) ^ hash< uint8_t >(p.y);

但是，如果实现 hash< uint8_t >（在这种情况下）试图将哈希码值分散到 std::size_t 范围内，则会丢弃信息（由于溢出）。

使用乘以质数加法方法累积组件哈希码值，如 Java 中通常所做的，可能总体上效果更好：

 namespace std {
    template<>
    struct hash< Point > {
       size_t operator()(const Point &p) const {
          const size_t prime = 257;
          size_t h {hash< uint8_t >(p.x)};
          h = h * prime + hash< uint8_t >(p.y);
          return h;
       }
    };
 }

- Raedwald

2

在C++标准库中没有相应的支持时，可按以下步骤进行哈希处理：

下载现代哈希器，例如SpookyHash：http://burtleburtle.net/bob/hash/spooky.html。
在std::hash<YourType>定义中创建一个SpookyHash实例，并将其初始化。请注意，在进程启动或std::hash构造期间随机选择一个数字并将其用作初始化将使攻击你的程序变得更加困难，但无法解决问题。
将结构体中贡献于operator==（“关键字段”）的每个字段传递给SpookyHash::Update。
- 注意像double这样的类型：它们有两个表示为char[]的表现形式，可以进行比较：-0.0和0.0。还需注意具有填充的类型。在大多数计算机上，int没有填充，但很难确定struct是否具有填充。 http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html#is_contiguously_hashable有相关讨论。
- 如果有子结构，可以将它们的字段递归地传递到同一个SpookyHash实例中，从而获得更快、更高质量的哈希值。但是，这需要向这些结构体添加方法或手动提取关键字段：如果无法完成这一步骤，可以将其std::hash<>值传递到顶层SpookyHash实例中。
从std::hash<YourType>中返回SpookyHash::Final的输出。

- Jeffrey Yasskin

2

Bloomberg已经开源了他们的生产质量N3980实现：https://github.com/bloomberg/bde/blob/master/groups/bsl/bslh/doc/bslh.txt。SpookyHash实现在这里找到：https://github.com/bloomberg/bde/blob/master/groups/bsl/bslh/bslh_spookyhashalgorithm.h。 - Andrew Paprocki

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Maxim Egorushkin · Accepted Answer

一种简单的方法是使用boost::hash库并扩展它以适用于您的类型。它有一个很好的扩展函数hash_combine（std::hash缺少此功能），允许轻松组合结构体中各个数据成员的哈希值。

换句话说：

为您自己的类型重载boost::hash_value。
为您自己的类型专门化std::hash，并使用boost::hash_value实现它。

这样您就可以得到std和boost两个世界的最佳结合，std::hash<>和boost::hash<>都可以适用于您的类型。

更好的方式是使用N3980 Types Don't Know #中提出的新哈希基础设施。该基础设施不需要使用hash_combine。