mercredi 25 mai 2016

std::hash variations of object with arbitrary number of attributes of fundamental type

Discussion:

Let's say I have a struct/class with an arbitrary number of attributes that I want to use as key to a std::unordered_map e.g.,:

struct Foo {
  int    i;
  double d;
  char   c;
  bool   b;
};

I know that I have to define a hasher-functor for it e.g.,:

struct FooHasher {
  std::size_t operator()(Foo const &foo) const;
};

And then define my std::unordered_map as:

std::unordered_map<Foo, MyValueType, FooHasher> myMap;

What bothers me though, is how to define the call operator for FooHasher. One way to do it, that I also tend to prefer, is with std::hash. However, there are numerous variations e.g.,:

std::size_t operator()(Foo const &foo) const {
  return std::hash<int>()(foo.i)    ^
         std::hash<double>()(foo.d) ^
         std::hash<char>()(foo.c)   ^
         std::hash<bool>()(foo.b);
}

I've also seen the following scheme:

std::size_t operator()(Foo const &foo) const {
  return std::hash<int>()(foo.i)           ^
         (std::hash<double>()(foo.d) << 1) ^
         (std::hash<char>()(foo.c)   >> 1) ^
         (std::hash<bool>()(foo.b)   << 1);
}

I've seen also some people adding the golden ratio:

std::size_t operator()(Foo const &foo) const {
  return (std::hash<int>()(foo.i)    + 0x9e3779b9) ^
         (std::hash<double>()(foo.d) + 0x9e3779b9) ^
         (std::hash<char>()(foo.c)   + 0x9e3779b9) ^
         (std::hash<bool>()(foo.b)   + 0x9e3779b9);
}

Questions:

  1. What are they trying to achieve by adding the golden ration or shifting bits in the result of std::hash.
  2. Is there an "official scheme" to std::hash an object with arbitrary number of attributes of fundamental type?

Aucun commentaire:

Enregistrer un commentaire