Почему std :: hash & lt; int & gt; кажется, функция идентичности
#include <iostream>
int main() {
std::hash<int> hash_f;
std::cout << hash_f(0) << std::endl;
std::cout << hash_f(1) << std::endl;
std::cout << hash_f(2) << std::endl;
std::cout << hash_f(3) << std::endl;
}
Я компилирую с «g ++ main.cpp -std = c ++ 11», а затем результат:
0
1
2
3
Почему это происходит? Я не использую какую-либо библиотеку, и у меня нет специальной функции хеширования.
Приложение: я хотел определить хеш для unordered_set для unordered_set int с хешем набора, представляющим собой сумму хешей его компонентов, но если это просто тождество, это не круто, потому что хеш {2,4} такой же, как хеш {1,5}. Самый простой способ избежать этого — использовать двойную функцию std :: hash.
Решение
Кажется, что его идентичность, его допускают как его отличные ..
От ссылка cpp
Фактические хеш-функции зависят от реализации и не обязаны выполнять какие-либо другие критерии качества, кроме указанных выше. Примечательно, что в некоторых реализациях используются тривиальные (идентифицирующие) хеш-функции, которые отображают целое число на себя. Другими словами, эти хеш-функции предназначены для работы с неупорядоченными ассоциативными контейнерами, но не, например, в качестве криптографических хешей. ….
Другие решения
Это кажется вполне разумным для хэш-функции int→int быть личностью, и не понятно, почему вас это удивляет. Выполнять любые дальнейшие вычисления бессмысленно. Это, на самом деле, идеальный хэш во всех смыслах этого термина.
Помните, std::hash должен (почти уникально) идентифицировать значения, а не шифровать их.
Это только когда вы хотите хешировать типы больше, чем у самого хэша (скажем, uint9999999_t) что вам нужно проделать некоторую работу, чтобы «сжать» значение до размера хэша.
Другие ответы очень хорошо охватывают обоснование функции идентичности. Чтобы обратиться к вашему приложению:
Я хотел определить хеш unordered_set как сумму хешей его компонентов, но если это просто тождество, это не круто, потому что хеш {2,4} совпадает с хешем {1,5}. Самый простой способ избежать этого — использовать функцию std :: hash.
Как вы можете видеть, используя + Оператор для объединения хешей не самая лучшая идея. Чтобы быть более устойчивым, вы можете использовать XOR (^) или вдохновиться подходом, например, boost::hash_combine (подробности в этом посте):
seed ^= hash_value(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
Например, для ваших двух целочисленных пар (1,5 / 2,4) и seed из 0, это сработает
uint32_t seed = 0;
seed ^= 1 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= 5 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// 3449077526
uint32_t seed = 0;
seed ^= 2 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
seed ^= 4 + 0x9e3779b9 + (seed << 6) + (seed >> 2);
// 3449077584