Interesting stdext::hash_value() implementation

Question

I was trying some hashing algorithms with stdext::hash_value() on VS2010 and realized this:

#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

I tried some other couples of double variable that has the same integer but different fractional part. Like 1.234 vs 1.568. Hash values were always the same. So I took a look at source of hash_value() and saw

#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 is cast to size_t which does not make sense to me. The function simply ignores the fractional part of double. What is the logic behind this implementation? Is it a bug or feature?

Answer 1

stdext::hash_value isn't a hash function. It's the input to a hash function, you specialize it for your type so that it can be used as a key for the stdext hash classes. There doesn't seem to be any documentation for it however. The actual hash function is stdext::hash_compare.

But because there is no default specialization of hash_value it uses the convert-to-int method which ignores the fractional part.

There is an almost-identical bug for the standard std::tr1::hash/std::hash function up until vc10:

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

in vc10 std::hash gets a double specialization that hashes the bits. I guess stdext is considered obsolete now so there's no fix for it even in vc10.

Answer 2

The function is written to work with any type of data. It makes no assumption about the size and hence is inefficient for certain types. You can override this behavior for doubles to make it more efficient via a template specialization

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

Putting this definition above your main method will cause the calls to stdext::hash_value(354.566) to bind to this definition as opposed to the standard one