Страницы

Поиск по вопросам

среда, 19 декабря 2018 г.

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

Для того чтобы использовать в качестве ключа собственный класс в 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 )?
Не хотелось бы столкнуться с коллизиями, их будет очень сложно обнаружить, но подпортят работу они значительно.


Ответ

На самом деле, лучше всего стараться «перемешивать» хэшкоды как можно больше. Например, 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 (например, другое простое число, обычно побольше).

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

Комментариев нет:

Отправить комментарий