Для того чтобы использовать в качестве ключа собственный класс в 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
это касается двух полей, меня смущает этот момент 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
Код
h1 ^ h2 ^ ... ^ h(n)
считается неправильным, потому что довольно часто поля имеют одинаковые значения и имеют равные хэши (а для целочисленных полей часто в качестве хэша используется само поле). Поскольку при операции ^ равные значения взаимно уничтожаются, то у нас получается меньшее количество хэш-значений и соответственно много коллизий.
Также популярный вариант такой:
result_type hash = start;
hash = hash * factor + std::hash
(им пользуется Java и .NET) для подходящего значения start и factor. В качестве factor обычно используется небольшое простое число, наподобие 13 или там 29. start должно быть по идее взаимно простым с factor (например, другое простое число, обычно побольше).
Вот хорошая обзорная статья (на английском) по различным методикам вычисления хэша.
Комментариев нет:
Отправить комментарий