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
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk