如何正确hash的自定义结构？ [英] How to properly hash the custom struct?

问题描述

在C ++语言中，对于最简单的类型，如 std：有一个默认的散列函数模板 std :: hash< T> ：string ， int 等。我假设这些函数具有良好的熵，相应的随机变量分布在统计上是统一的。

In the C++ language there is the default hash-function template std::hash<T> for the most simple types, like std::string, int, etc. I suppose, that these functions have a good entropy and the corresponding random variable distribution is statistically uniform. If it's not, then let's pretend, that it is.

然后，我有一个结构：

struct CustomType {
  int field1;
  short field2;
  string field3;
  // ...
};

我想对其进行哈希运算，使用某些字段的单独哈希值，例如 std :: hash（field1）和 std :: hash（field2）。两个散列都在类型 size_t 的一组可能的值中。

I want to hash it, using separate hashes of some of it's fields, say, std::hash(field1) and std::hash(field2). Both hashes are in a set of possible values of the type size_t.

什么是好的哈希函数，可以组合这些结果并将它们映射回 size_t ？

What is a good hash-function, that can combine both those results and map them back to size_t?

推荐答案

boost :: hash_combine 是非常好的哈希不同的字段。

boost::hash_combine is really good one to hash different fields.

如果你没有boost库您可以使用此：

If you don't have boost library you can use this :

template <class T>
inline void hash_combine(std::size_t & s, const T & v)
{
  std::hash<T> h;
  s^= h(v) + 0x9e3779b9 + (s<< 6) + (s>> 2);
}

 struct S {
  int field1;
  short field2;
  std::string field3;
  // ...
};

template <class T>
class MyHash;

template<>
struct MyHash<S>
{
    std::size_t operator()(S const& s) const 
    {
        std::size_t res = 0;
       hash_combine(res,s.field1);
       hash_combine(res,s.field2);
       hash_combine(res,s.field3);
        return res;
    }
};

然后可能 std :: unordered_set< S> s; ，etc

这篇关于如何正确hash的自定义结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！