Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

How to properly hash the custom struct?

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?

like image 609
abyss.7 Avatar asked Oct 05 '13 07:10

abyss.7


2 Answers

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

like image 134
P0W Avatar answered Sep 27 '22 21:09

P0W


boost::hash_combine is something that could help you out here:

namespace std
{
template <>
struct hash<CustomType>
{
    std::size_t operator()(const CustomType& c) const
    {
        std::size_t result = 0;
        boost::hash_combine(result, field1);
        boost::hash_combine(result, field2);
        return result;
    }
};
}

See the boost doc here.

like image 40
Yuushi Avatar answered Sep 27 '22 21:09

Yuushi