Интересная реализация stdext :: hash_value ()

Question

Я пробовал некоторые алгоритмы хеширования с stdext::hash_value() на VS2010 и понял это:

#include <iostream>
#include <xhash>
using namespace std;

int main() 
{
#ifdef _WIN64
    std::cout << "x64" << std::endl;
#else
    std::cout << "x32" << std::endl;
#endif

    std::cout << stdext::hash_value(345.34533) << std::endl;
    std::cout << stdext::hash_value(345.566) << std::endl;

    return 0;
}

// Output is:
// x64
//3735928758
//3735928758

Я пробовал некоторые другие пары двойной переменной, которые имеют такое же целое, но разную дробную часть. Как 1.234 против 1.568. Хэш-значения всегда были одинаковыми. Поэтому я взглянул на источник hash_value() и увидел

#define _HASH_SEED  (size_t)0xdeadbeef

template<class _Kty> inline
size_t hash_value(const _Kty& _Keyval)
{   // hash _Keyval to size_t value one-to-one
    return ((size_t)_Keyval ^ _HASH_SEED);
}

_KeyVal приведен к size_t, что не имеет смысла для меня. Функция просто игнорирует дробную часть double. Какова логика этой реализации? Это ошибка или особенность?

Answer 1

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

Но поскольку спецификация hash_value по умолчанию отсутствует, он использует метод convert-to-int, который игнорирует дробную часть.

Существует почти идентичная ошибка для стандартной функции std :: tr1 :: hash / std :: hash вплоть до vc10:

http://connect.microsoft.com/VisualStudio/feedback/details/361851/std-tr1-hash-float-or-hash-double-is-poorly-implemented

в vc10 std :: hash получает двойную специализацию, которая хэширует биты. Я полагаю, что stdext считается устаревшим, поэтому исправления для него нет даже в vc10.

Answer 2

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

template<>
size_t hash_value<double>(const double& key) {
    return // Some awesome double hashing algorithm 
}

Если поставить это определение над вашим методом main, вызовет привязку к этому определению stdext::hash_value(354.566), а нестандартный

Answer 3

VC10 содержит стандартные механизмы хеширования C ++ 0x, поэтому больше нет необходимости использовать механизмы stdext, а std::hash содержит механизм для double, который выполняет побитовое преобразование и затем хеширование.Тот код, который у вас есть для stdext, является всего лишь резервным механизмом, и он на самом деле не предназначен для использования с типами с плавающей точкой.Я думаю, это упущение дизайна.

template<>
class hash<double>
    : public unary_function<double, size_t>
{   // hash functor
public:
typedef double _Kty;
typedef _ULonglong _Inttype;    // use first 2*32 bits

size_t operator()(const _Kty& _Keyval) const
    {   // hash _Keyval to size_t value by pseudorandomizing transform
    _Inttype _Bits = *(_Inttype *)&_Keyval;
    return (hash<_Inttype>()(
        (_Bits & (_ULLONG_MAX >> 1)) == 0 ? 0 : _Bits));
    }
};

Answer 4

Это, по-видимому, попытка предоставить универсальную хеш-функцию для целых чисел (хотя я не вижу, что добавляет xor).Совершенно ясно, что не будет работать для большинства других типов.Включая число с плавающей запятой.

Обеспечение хорошей хэш-функции для значения с плавающей запятой затруднительно;если бы я пытался создать общий хеш, я бы, вероятно, начал с проверки на 0, NaN и Inf и возврата предопределенных хешей для них (или полного отклонения NaN, поскольку оно не является допустимым хеш-значением), а затем просто с помощьюстандартный хэш строки в нижележащих байтах.Это по крайней мере сделает хеширование совместимым с оператором ==.Но проблемы точности означают, что == само по себе может не быть тем, что нужно.Ни <, в случае std :: map, поскольку std :: map использует <для определения отношения равенства, и в зависимости от источника чисел с плавающей запятой или удваивается, такое отношение равенства может не подходить для хеш-таблицы. </p>

В любом случае, не ожидайте найти стандартную хеш-функцию для типов с плавающей запятой.

Answer 5

Это старый код - выглядит не очень хорошо.

Возможно, вам следует вместо этого попробовать std :: hash.