Re: [boost] [functional] boost::hash with 64-bit types

From: Daniel James (daniel_james_at_[hidden])
Date: 2006-03-20 17:59:22

Daniel James wrote:

> Actually, it does for positive number. Sorry I misread it. What you were 
> doing clicked a couple of seconds after I clicked on 'send'. But I'm not 
> sure it works for negative numbers.

Okay, probably not perfect, but here's a mostly working version:

template <class T>
size_t integer_hash_value(T val)
{
     const int size_t_bits = std::numeric_limits<size_t>::digits;

     size_t seed = val;

     // Two's complement for negative numbers but only after using
     // the initial value so that: hash_value(-2) != hash_value(1)
     val = val < 0 ? -1 - val : val;

     while( val >>= size_t_bits )
     {
         hash_combine(seed, (size_t) val);
     }

     return seed;
}

My idea was something roughly like this:

template <class T>
size_t hash_value2(T val)
{
     const int size_t_bits = std::numeric_limits<size_t>::digits;
     // ceiling(std::numeric_limits<T>::digits / size_t_bits) - 1
     const int length = (std::numeric_limits<T>::digits - 1)
         / size_t_bits;

     size_t seed = 0;
     T positive = val < 0 ? -1 - val : val;

     // Hopefully, this loop can be unrolled.
     for(unsigned int i = length * size_t_bits; i > 0; i -= size_t_bits)
     {
         seed ^= (size_t) (positive >> i) + (seed<<6) + (seed>>2);
     }
     seed ^= (size_t) val + (seed<<6) + (seed>>2);

     return seed;
}

Which looks more complicated, but if the compiler optimizes it well (or 
I optimize the code), it could be faster (as there are less 
comparisons). Although, maybe this is a premature optimization, since 
long long is unlikely to have more than twice the number of bits than 
std::size_t.

I'm not suggesting the specification should spell out an algorithm, but 
could describe requirements that both those algorithms would meet. This 
would give library authors some latitude to deal with the strengths of 
the processor they're targeting and their own imagination.

Daniel