是否有自定义类的unordered_set的默认哈希函数？

Question

我第一次使用std::unordered_set并且对哈希函数有疑问。据我所知，如果你没有指定哈希函数，它将默认为std::hash<Key>。

我的一个课程中有一个mySet成员：

typedef std::unordered_set<MyClass> USetType;
USetType mySet;

当我尝试构建时，我收到以下错误：

错误C2440：'type cast'：无法从'const MyClass'转换为'size_t'

如果要将size_t与自定义类一起使用，是否有必要定义转换函数（到unordered_set）？有没有办法避免编写自己的哈希函数并只使用默认值？

Answer 1

如果您没有将自己的散列函数指定为模板参数，则默认为std::hash<MyClass>，除非您定义它，否则它不存在。

最好在命名空间std::hash中定义自己的std专业化：

namespace std {
  template <>
  struct hash<MyClass>
  {
    typedef MyClass      argument_type;
    typedef std::size_t  result_type;

    result_type operator()(const MyClass & t) const
    {
       /* ..calculate hash value for t */
    }
  };
}

并确保在声明哈希之前包含此代码。这样，您可以将哈希声明为std::unordered_set<MyClass>，而无需进一步的模板参数。

你没有指定MyClass里面的内容，但典型的情况是你的用户定义类型只包含几个简单类型的成员，其中存在一个默认的哈希函数。在这种情况下，您可能希望将各个类型的哈希值组合为整个组合的哈希值。为此，Boost库提供了一个名为hash_combine的函数。当然，不能保证它在您的特定情况下能够很好地工作（它取决于数据值的分布和碰撞的可能性），但它提供了一个好的且易于使用的起点。

这是一个如何使用它的例子，假设MyClass由两个字符串成员组成：

#include <unordered_set>
#include <boost/functional/hash.hpp>

struct MyClass
{
  std::string _s1;
  std::string _s2;
};

namespace std {
  template <>
  struct hash<MyClass>
  {
    typedef MyClass      argument_type;
    typedef std::size_t  result_type;

    result_type operator()(const MyClass & t) const
    {
      std::size_t val { 0 };
      boost::hash_combine(val,t._s1);
      boost::hash_combine(val,t._s2);
      return val;
    }
  };
}

int main()
{
  std::unordered_set<MyClass> s;
  /* ... */
  return 0;
}

Answer 2

我想扩展jogojapan给出的answer。正如CashCow在comment中提到的那个答案，你也需要overload the equality comparison operator（operator==）为MyClass或定义一个单独的比较函数并提供给unordered_set。否则，您将收到另一条错误消息。例如，VS 2013抛出：

错误C2678：二进制'=='：找不到哪个运算符带有'const MyClass'类型的左操作数（或者没有可接受的转换）

此外，您可以使用lambda expressions而不是定义哈希和比较函数。如果你不想使用Boost，那么你也可以使用handcraft a hash function。我明白，你想使用一些默认函数，但编译器不知道如何为自定义类计算有意义的哈希。但是，您可以将std::hash用于您班级的成员。如果你把所有东西放在一起，那么你的代码可以写成如下：

class MyClass {
public:
    int i;
    double d;
    std::string s;
};

int main()
{
    auto hash = [](const MyClass& mc){
        return (std::hash<int>()(mc.i) * 31 + std::hash<double>()(mc.d)) * 31 + std::hash<std::string>()(mc.s);
    };
    auto equal = [](const MyClass& mc1, const MyClass& mc2){
        return mc1.i == mc2.i && mc1.d == mc2.d && mc1.s == mc2.s;
    };
    std::unordered_set<MyClass, decltype(hash), decltype(equal)> mySet(8, hash, equal);

    return 0;
}

Code on Ideone