4

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

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

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

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

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

1
  • 1
    С коллизиями Вы неизбежно столкнётесь
    – ixSci
    16 июл 2015 в 14:46

2 ответа 2

5

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

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

Код

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

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

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

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

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


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

4

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

#include <boost/functional/hash.hpp>

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

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge you have read our privacy policy.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.