unordered_set的哈希函数 [英] hash function of unordered_set

问题描述

我第一次使用 std :: unordered_set ，并且有关于散列函数的问题。据我所知，如果你不指定一个哈希函数，它将默认为std :: hash。

I'm using a std::unordered_set for the first time and have a question about the hash function. As far as I understand, if you don't specify a hash function it will default to std::hash.

我有一个mySet成员在我的一个类：

I have a mySet member in one of my classes:

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

当我尝试构建时，我得到一个错误：

When I try to build, I get an error:

error C2440: 'type cast' : cannot convert from 'const MyClass' to 'size_t'

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

Is it necessary to define a conversion function (to size_t) if you want to use unordered_set with a custom class? Is there any way to avoid writing your own hash function and just using the default?

推荐答案

如果你不指定自己哈希函子作为模板参数，它将默认为 std :: hash< MyClass> ，除非你定义它不存在。

If you don't specify your own hash functor as template argument, it will default to std::hash<MyClass>, which does not exist unless you define it.

最佳定义 std :: hash 在命名空间内的专业化 std ：

Best define your own specialization of std::hash inside namespace 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> ，而不需要其他模板参数。

And make sure you include this code before the declaration of your hash. This way you can declare the hash simply as std::unordered_set<MyClass> with no need for further template arguments.

你没有指定 MyClass 看起来像里面，但典型的情况是你的用户定义类型只包含几个简单类型的成员，散列函数存在。在这种情况下，您可能想要将各个类型的哈希值合并为整个组合的哈希值。为此，Boost库提供了一个名为 hash_combine 的函数。当然，不能保证它在你的特定情况下能正常工作（取决于数据值的分布和冲突的可能性），但它提供了一个好的和易于使用的起点。

You didn't specify what MyClass looks like inside, but a typical situation is that your user-defined type simply consists of several simple-type members, for which a default hash function exists. In this case, you will probably want to combine the hash values for the individual types to a hash value for the entire combination. The Boost library provides a function called hash_combine for this purpose. Of course, there is no guarantee that it will work well in your particular case (it depends on the distribution of data values and the likelihood of collisions), but it provides a good and easy-to-use starting point.

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

Here is an example of how to use it, assuming MyClass consists of two string members:

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

这篇关于unordered_set的哈希函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！