How to properly hash the custom struct?

abyss.7 picture abyss.7 · Oct 5, 2013 · Viewed 11.1k times · Source

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.

Then, I have a structure:

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

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.

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

Answer

P0W picture P0W · Oct 5, 2013

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

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

And then probably std::unordered_set<S> s; , etc