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

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

Peter Dimov wrote:
> For larger integer types, we probably need something along the lines of
> 
> std::size_t hash_value( val )
> {
>     size_t r = val;
> 
>     while( val >>= size_t_bits )
>     {
>         hash_combine( r, (size_t)val );
>     }
> 
>     return r;
> }
> 
> It has the property of preserving the hash_value of all _values_ that can 
> fit into a size_t, even though the underlying type is capable of holding 
> bigger integers. 

I don't think it does. It needs to be done in the reverse order, and 
needs to use a different combine function which hashes 0's to 0. For 
example, for 10, that would do:

r = 10;
hash_combine(r, 0);

Which would not give 10.

Negative numbers would be a problem, so I was thinking of inverting the 
higher parts (ie. a 64-bit -2, would convert to the 32-bit values FF, 
FE, then I'd invert the first one, to get 00, FE and combine it to make 
FE) but that'd be a little slow as it requires a comparison. So I was 
going to try to come up with something better.

Sorry if that isn't very clear. I wanted to spend a bit of time writing 
this up and I've been thinking about other possibilities as well.

Daniel