Re: [boost] [review] hash functions

From: Dave Harris (brangdon_at_[hidden])
Date: 2005-03-10 10:49:13

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.

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;
    }

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

> 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.

-- Dave Harris, Nottingham, UK