Страницы

Поиск по вопросам

четверг, 30 мая 2019 г.

Шаблонная хэш-функция

Допустим, мне нужно сделать некий шаблонный контейнер Map на хэш-таблице. Контейнер, естественно, может принимать ключем значение любых типов - как, в таком случае, написать хэш-функцию? Как привести произвольный тип T (для которого может быть не перегружен оператор приведения) к целочисленному типу? Вроде как должен помочь reinterpret_cast, который приводит к указателю, но конструкция вида
reinterpret_cast (key);
Отказывается компилироваться, когда key имеет не-целочисленный тип.
Если же приводить указатель к указателю (как в примере на msdn)
reinterpret_cast (&key);
то теряется смысл хэш таблицы - поиск по ней не будет работать, поскольку ключ с идентичным значением будет иметь другой адрес, и результат хэш-функции будет тоже другой.
Можно ли как-то насильно интерпретировать байты произвольного объекта в памяти как целочисленный тип? Вообще, какое решение будет правильным? Как эта проблема решена в std::unordered_map или QMap?


Ответ

Классы наподобие unordered_set вычисляют хеш не сами, а используют std::hash (а также дают возможность пользователю указать свою реализацию хеширования, если он недоволен стандартной, или если её не существует).
std::hash, в свою очередь, тоже не пользуется никакой особой магией, а просто имеет шаблонные специализации для примитивных типов, строк и указателей (обычных и «умных»).
Мне кажется, вам стоит не изобретать велосипед, а воспользоваться той же идеей. А ещё проще, просто используйте std::hash. Поверьте, в написании контейнера есть много сложностей помимо этой.

Таким образом, просто используйте
size_t hash_value = std::hash()(t);

Комментариев нет:

Отправить комментарий