Как получить хэш от произвольного класса для unordered контейнера?

#cpp #хеширование

Для того чтобы использовать в качестве ключа собственный класс в unordered_map (к
примеру) необходимо определить хэш функцию. Пример с cppreference.com

template<>
struct hash
{
    typedef S argument_type;
    typedef std::size_t result_type;

    result_type operator()(argument_type const& s) const
    {
        result_type const h1 ( std::hash()(s.first_name) );
        result_type const h2 ( std::hash()(s.last_name) );
        return h1 ^ (h2 << 1);
    }
};


это касается двух полей, меня смущает этот момент h1 ^ (h2 << 1) я видел примеры
без сдвига и теперь не совсем понимаю как мне проецировать этот пример на большее число
полей, по какому правилу. 
Я могу сделать просто h1 ^ h2 ^ ... ^ h(n) ? 
или же каждый последующий хэш мне нужно сдвигать? h1 ^ ( h2 << 1 ) ^ ... ^ ( h(n) << n )?

Не хотелось бы столкнуться с коллизиями, их будет очень сложно обнаружить, но подпортят
работу они значительно.
    

Ответы

Ответ 1

На самом деле, лучше всего стараться «перемешивать» хэшкоды как можно больше. Например,
Jon Skeet приводит такой пример:

result_type hash = (result_type)2166136261;
hash = hash * 16777619 ^ std::hash()(s.first_name);
hash = hash * 16777619 ^ std::hash()(s.second_name);
hash = hash * 16777619 ^ std::hash()(s.third_name);
return hash;


Код

h1 ^ h2 ^ ... ^ h(n)


считается неправильным, потому что довольно часто поля имеют одинаковые значения
и имеют равные хэши (а для целочисленных полей часто в качестве хэша используется само
поле). Поскольку при операции ^ равные значения взаимно уничтожаются, то у нас получается
меньшее количество хэш-значений и соответственно много коллизий.

Также популярный вариант такой:

result_type hash = start;
hash = hash * factor + std::hash()(s.first_name);
hash = hash * factor + std::hash()(s.second_name);
hash = hash * factor + std::hash()(s.third_name);
return hash;


(им пользуется Java и .NET) для подходящего значения start и factor. В качестве factor
обычно используется небольшое простое число, наподобие 13 или там 29. start должно
быть по идее взаимно простым с factor (например, другое простое число, обычно побольше).



Вот хорошая обзорная статья (на английском) по различным методикам вычисления хэша.


Ответ 2

Вот еще вариант по ссылке с использованием boost 

#include 

struct KeyHasher
{
  std::size_t operator()(const Key& k) const
  {
      using boost::hash_value;
      using boost::hash_combine;

      // Start with a hash value of 0    .
      std::size_t seed = 0;

      // Modify 'seed' by XORing and bit-shifting in
      // one member of 'Key' after the other:
      hash_combine(seed,hash_value(k.first));
      hash_combine(seed,hash_value(k.second));
      hash_combine(seed,hash_value(k.third));

      // Return the result.
      return seed;
  }
};