Как специализировать std:: hash <T> для пользовательских типов?

Ответ 1

Один простой способ - использовать библиотеку boost::hash и расширить ее для своего типа. Он имеет приятную функцию расширения hash_combine (std::hash не хватает этого), что позволяет легко составлять хеши отдельных элементов данных ваших структур.

Другими словами:

• Перегрузка boost::hash_value для вашего собственного типа.
• Специализируйте std::hash для своего собственного типа и реализуйте его с помощью boost::hash_value.

Таким образом, вы получаете лучшее из std и boost worlds, и std::hash<> и boost::hash<> работают для вашего типа.

Лучше всего использовать предлагаемую новую хеширующую инфраструктуру в N3980 Типы Не знаю #. Эта инфраструктура делает ненужным hash_combine.

Ответ 2

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

class HashAccumulator
{
    size_t myValue;
public:
    HashAccumulator() : myValue( 2166136261U ) {}
    template <typename T>
    HashAccumulator& operator+=( T const& nextValue )
    {
        myValue = 127U * myValue + std::hash<T>( nextHashValue );
    }
    HashAccumulator operator+( T const& nextHashValue ) const
    {
        HashAccumulator results( *this );
        results += nextHashValue;
        return results;
    }
};

(Это было разработано так, что вы можете использовать std::accumulate, если у вас есть последовательность значений.)

Конечно, это предполагает, что все подтипы имеют хорошие реализации std::hash. Для основных типов и строки, это данность; для ваших собственных типов, просто примените выше правила рекурсивно, специализируясь на std::hash, чтобы использовать HashAccumulator по своим подтипам. Для стандартного контейнера базовый тип, это немного сложнее, потому что вы не (формально, по крайней мере) разрешено специализировать стандартный шаблон для типа из стандартной библиотеки; вам, вероятно, придется создавать класс, который использует HashAccumulator напрямую, и явно укажите, что если вам нужен хэш такого контейнера.

Ответ 3

Пока мы не получим библиотеку в стандарте, чтобы помочь с этим:

• Загрузите современный хешер, например SpookyHash: http://burtleburtle.net/bob/hash/spooky.html.
• В определении std::hash<YourType> создайте экземпляр SpookyHash и Init it. Обратите внимание, что выбор случайного числа при запуске процесса или std::hash, а использование этого в качестве инициализации будет сделать немного сложнее для DoS вашей программы, но doesn ' t устранить проблему.
• Возьмите каждое поле в своей структуре, которое вносит вклад в operator== ( "основное поле" ) и подает его в SpookyHash::Update.
  • Остерегайтесь таких типов, как double: у них есть 2 представления как char[], которые сравнивают ==: -0.0 и 0.0. Также будьте осторожны с типами, у которых есть отступы. На большинстве машин int нет, но трудно сказать, будет ли struct. http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2014/n3980.html#is_contiguously_hashable обсуждает это.
  • Если у вас есть подструктуры, вы получите более быстрое и качественное хеш-значение из рекурсивного кормления своих полей в один и тот же экземпляр SpookyHash. Однако для этого требуется добавить метод к этим структурам или вручную извлечь выделенные поля: если вы не можете этого сделать, допустимо просто передать их значение std::hash<> в экземпляр SpookyHash верхнего уровня.
• Возвращает вывод SpookyHash::Final из std::hash<YourType>.

Ответ 4

Ваша операция требуется для

• Возвращает значение типа size_t
• В соответствии с оператором ==.
• Имеют небольшую вероятность столкновения хешей для неравных значений.

Нет явного требования, чтобы хэш-значения равномерно распределялись в диапазоне size_t целых чисел. cppreference.com отмечает, что

некоторые реализации [стандартной библиотеки] используют тривиальные (тождественные) хэш-функции, которые отображают целое число в себя

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

 struct Point {
    uint8_t x;
    uint8_t y;
 };

 namespace std {
    template<>
    struct hash< Point > {
       size_t operator()(const Point &p) const {
          return hash< uint8_t >(p.x) ^ hash< uint8_t >(p.y);
       }
    };
 }

Хеши p.x будут находиться в диапазоне [0,255], а также хэши p.y. Поэтому хеши a Point также будут находиться в диапазоне [0,255], с 256 (= 2 ^ 8) возможных значений. Есть 256 * 256 (= 2 ^ 16) уникальных объектов Point (a std::size_t обычно поддерживает значения 2 ^ 32 или 2 ^ 64). Поэтому вероятность хэш-столкновения для хорошей хэш-функции должна быть приблизительно 2 ^ (- 16). Наша функция дает вероятность столкновения хэшей только при 2 ^ (- 8). Это ужасно: наш хэш содержит только 8 бит информации, но хороший хеш должен обеспечивать 16 бит информации.

Если хеширующие функции ваших данных содержат только хеш-значения в нижних частях диапазона std::size_t, вы должны "сдвигать" биты хэша компонента перед их объединением, поэтому каждый из них вносит независимые биты информации, Выполнение левого сдвига выглядит просто.

       return (hash< uint8_t >(p.x) << 8) ^ hash< uint8_t >(p.y);

но это приведет к отбрасыванию информации (из-за переполнения), если реализация hash< uint8_t > (в этом случае) пытается распространить значения хэш-кода в диапазоне std::size_t.

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

 namespace std {
    template<>
    struct hash< Point > {
       size_t operator()(const Point &p) const {
          const size_t prime = 257;
          size_t h {hash< uint8_t >(p.x)};
          h = h * prime + hash< uint8_t >(p.y);
          return h;
       }
    };
 }