Как специализировать std :: hash & lt; T & gt; для пользовательских типов?

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

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

1. Загрузите современный хеш, например, SpookyHash: http://burtleburtle.net/bob/hash/spooky.html.
2. В определении std::hash<YourType>, создать SpookyHash экземпляр и Init Это. Обратите внимание, что выбор случайного числа при запуске процесса или std::hash строительство, и использование этого в качестве инициализации будет сделать DoS вашу программу немного сложнее, но не решает проблему.
3. Возьмите каждое поле в вашей структуре, которое способствует 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 пример.
4. Вернуть вывод SpookyHash::Final от std::hash<YourType>,

Ваша операция необходимо в

• Вернуть значение типа 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, Поэтому хэши Point также будет в диапазоне [0,255], с 256 (= 2 ^ 8) возможных значений. Есть 256 * 256 (= 2 ^ 16) уникальных Point объекты (а 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;
}
};
}