且构网

分享程序员开发的那些事...
且构网 - 分享程序员编程开发的那些事

unordered_set的哈希函数

更新时间:2023-11-10 09:33:04

如果你不指定自己哈希函子作为模板参数,它将默认为 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;
}