Re: [boost] [review] hash functions

From: Peter Dimov (pdimov_at_[hidden])
Date: 2005-03-10 07:08:45

Dave Harris wrote:
> In-Reply-To: <00cd01c524e3$bf3cb4d0$6501a8c0_at_pdimov2>
> pdimov_at_[hidden] (Peter Dimov) wrote (abridged):
>> A pure function would entice you to define hash_value for (x, y)
>> as hash_combine(x, y).
>
> And that would be bad because...?

That would be bad because the hash value of the pair (x, y) would no longer 
match the hash value of the sequence (x, y).

>> We can fix this by initializing the seed in hash_range with something
>> other than zero. It isn't a problem for strings, where \0 is rare,
>> but may be a problem for arbitrary sequences.
>
> That would help.
>
> How about fixing it in hash_combine instead?

This would mean N fixes for a sequence of length N, when one simple fix is 
enough. The initial value of the seed is arbitrary so we can vary it at 
will. hash_combine, on the other hand, is based on research and has 
apparently been selected as one of the best amongst the shift+xor family. 
This doesn't mean that it's sacred, just that if we change it we'll no 
longer be able to just point at a PDF as a rationale but will need to do our 
own research (which might be a good idea anyway, though.)

Do you have a different hash_combine in mind that doesn't suffer from this 
problem and is better than the proposed implementation? ;-) (Keeping in mind 
that even the current hash_combine is perceived as slower than necessary, of 
course.)