20

问题

对于所有成员数据类型都已经具有良好的 std::hash 特化的用户定义类型，在 std::unordered_map 或 std::unordered_set 的第三个模板参数中使用 std::hash 的好的特化是什么？

对于这个问题，我将“好”定义为易于实现和理解、相当有效且不太可能产生哈希表冲突。良好的定义不包括任何关于安全的陈述。

Google 的现状

目前，两个 StackOverflow 问题是 Google 搜索“std hash specialization”的第一名。

第一个，如何为无序容器中的用户定义类型专门化 std::hash::operator()？, 解决打开 std 命名空间和添加模板特化是否合法。

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

这就留下了当前的问题。鉴于 C++ 标准库的实现为标准库中的基本类型和类型定义了散列函数，那么将 std::hash 专门用于用户定义类型的简单而有效的方法是什么？有没有一种组合标准库实现提供的散列函数的好方法？

（感谢 dyp 编辑。） StackOverflow 上的另一个问题解决了如何组合一对哈希函数。

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

Dobbs 博士的这篇文章指出，两个令人满意的散列的异或将产生一个新的令人满意的散列。

这篇文章似乎是从知识上讲的，暗示了很多东西，但细节却很轻。它与 Dobbs 博士在第一个示例中的简短评论中的文章相矛盾，他说使用 XOR 组合散列函数会导致生成的散列函数很弱。

因为 XOR 应用于任何两个相等的值会导致 0，所以我可以看到为什么 XOR 本身很弱。

元问题

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

4

4 回答 4

7

一种简单的方法是使用boost::hash库并为您的类型扩展它。它有一个很好的扩展功能hash_combine（std::hash缺少），可以轻松组合结构中各个数据成员的散列。

换句话说：

  1. 为您自己的类型重载boost::hash_value。
  2. 专门std::hash针对您自己的类型并使用boost::hash_value.

通过这种方式，您可以充分利用 std 和 boost 世界，std::hash<>并boost::hash<>为您的类型工作。

更好的方法是使用N3980 Types Don't Know #中建议的新散列基础设施。这种基础设施是hash_combine不必要的。

于 2014-06-23T09:33:50.067 回答
3

首先，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。对于基本类型和字符串，这是给定的；对于您自己的类型，只需递归应用上述规则，专门在其子类型上std::hash使用 。HashAccumulator对于基本类型的标准容器，这有点棘手，因为（至少正式地）不允许您针对标准库中的类型专门化标准模板；您可能必须创建一个HashAccumulator直接使用的类，并明确指定是否需要此类容器的哈希。

于 2014-06-23T11:26:14.617 回答
2

直到我们在标准中获得一个库来帮助解决这个问题：

  1. 下载现代散列器，例如 SpookyHash：http ://burtleburtle.net/bob/hash/spooky.html 。
  2. 在 的定义中std::hash<YourType>，创建一个SpookyHash实例，然后Init它。请注意，在进程启动或std::hash构建时选择一个随机数，并将其用作初始化将使您的程序更难 DoS，但不能解决问题。
  3. 获取结构中有助于operator==（“显着领域”）的每个字段，并将其输入SpookyHash::Update.
    • 当心像这样的类型double：它们有 2 种表示形式，因为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实例中。
  4. 返回SpookyHash::Finalfrom的输出std::hash<YourType>。
于 2014-06-23T09:24:46.367 回答
1

您的操作需要

  • 返回一个类型的值size_t
  • ==与运营商保持一致。
  • 对于不相等的值，哈希冲突的概率很低。

没有明确要求哈希值均匀分布在size_t整数范围内。cppreference.com注意到_

[标准库]的一些实现使用将整数映射到自身的普通（身份）哈希函数

避免哈希冲突以及该弱点意味着std::hash您的类型的专业化永远不应简单地使用（快速）按位 XOR ( ^) 来组合数据成员的子哈希。考虑这个例子：

 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。因此，a 的哈希值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;
       }
    };
 }
于 2017-12-05T16:29:29.107 回答