Как использовать unordered_set с пользовательскими типами?

Question

Требуется ли создание собственной хэш-функции для пользовательских типов? Нет ли значений по умолчанию, которые я могу использовать с unordered_set?

Answer 1

Стандартная библиотека содержит специализации std::hash<T> для основных типов, для указателей и для std::string (точнее, для всех специализаций std::basic_string).

К сожалению, библиотека не содержит следующую жизненно важную комбинированную функцию "новый из старого", которая, однако, является частью Boost и которую вы должны скопировать в свой код:

template <class T>
inline void hash_combine(std::size_t & seed, const T & v)
{
    std::hash<T> hasher;
    seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

С помощью этой функции вы можете хэшировать пары, кортежи, массивы и любые типы элементов, которые сами могут быть хэшируемыми. Просмотрите источники Boost для множества примеров и полезных реализаций. И, очевидно, вы можете использовать эту функцию для создания хеш-функции для ваших собственных типов. Например, вот хэширование пары:

template<typename S, typename T> struct pair_hash<std::pair<S, T>>
{
    inline std::size_t operator()(const std::pair<S, T> & v) const
    {
         std::size_t seed = 0;
         hash_combine(seed, v.first);
         hash_combine(seed, v.second);
         return seed;
    }
};

Однако имейте в виду, что объединение хешей не дает хороших значений хешей. Результаты имеют очень плохие статистические качества (например, очень легко создавать коллизии хэшей). Хорошее хеширование должно быть в состоянии видеть все необработанные входные биты и не может быть учтено через частичные хеши. (Вот почему в текущей стандартной библиотеке нет лучшего решения; никто не смог придумать удовлетворительный дизайн.)

Answer 2

Да, вам нужно написать свою собственную хэш-функцию. Это не так плохо, как кажется: если в вашем классе есть какой-либо хешируемый элемент, который, как вы знаете, будет достаточно уникальным, вы можете просто вернуть хеш этого члена.

Вы можете предоставить этот хеш, специализируя std::hashили путем явной передачи хеш-класса в качестве параметра шаблона.