Re: [boost] [review] hash functions

From: Peter Dimov (pdimov_at_[hidden])
Date: 2005-03-10 12:36:25

Dave Harris wrote:
> In-Reply-To: <018901c52569$ea842610$6601a8c0_at_pdimov>
> pdimov_at_[hidden] (Peter Dimov) wrote (abridged):
>> 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).
>
> Why is it necessary for pairs and sequences to have the same hash
> value?
> They are different things.

pair<int, int>, int[2], struct { int a; int b; } are different 
representations of the same thing; it is not strictly necessary for them to 
use the same algorithm, but it's desirable and will eliminate a source of 
confusion and mistakes.

> If it is necessary, we can avoid the problem by fixing hash_range:
>
>    template <typename It>
>    size_t hash_range( It first, It last ) {
>        if (first == last)
>            return 0x87654321; // Or some other value;
>        size_t seed = hash_value(*first);
>        for (++first; first != last; ++first)
>            seed = hash_combine( seed, *first );
>        return seed;
>    }

The simpler "initialize seed, modify seed with each element" approach is 
much cleaner. It can also be expressed in terms of

    void hash_range( size_t & seed, It first, It last );

should this function be added. You are welcome to spell the above as

    size_t hash_range( size_t seed, It first, It last );

and I understand your reasons for doing so, I just don't see side effects as 
so evil. Anyway, the good thing in this formulation is that you can hash a 
range in stages, if you only have access to a subrange at a time. The 
non-uniform treatment of empty sequences and the first element of the 
sequence would force you to keep state. State is even more evil than side 
effects. ;-)

> This also gives hash_range( &a, &a+1 ) the same result as
> hash_value(a), which your approach does not.

Yes, you are right, starting with a nonzero seed makes sequences of one 
element produce a different hash value than the element itself.

>> 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.)
>
> I had in mind something like:
>
>    template <typename T>
>    size_t hash_combine( size_t seed, const T &v ) {
>        const size_t c = 0x12345678; // Or some other value.
>        return seed ^ (hash_value(v) + c + (seed<<6) + (seed>>2));
>    }
>
> This costs one extra addition, which can probably be scheduled in
> parallel with other operations anyway.

This may be good enough.