Re: [boost] Re: [review] hash functions

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

In-Reply-To: <d0pe8q$tdi$1_at_[hidden]>
daniel_at_[hidden] (Daniel James) wrote (abridged):
> But it will be easy to make mistakes for more complicated (possibly 
> recursive) types. Especially since hash_combine is not associative or 
> transitive. I could see that leading to mistakes.

I can see that it's possible to call the function with the wrong 
arguments, but that kind of problem can be addressed with documentation 
and/or by careful naming. I don't think that's worth distorting the 
interface and introducing side effects and spurious variables and 
inefficiency to fix it.

> And it would be quite easy to forget to call hash_value (because
> many types are implicitly convertible to std::size_t)

Since that conversion is all hash_value does, why does it matter?

That said, I agree the second argument should not be hash value. If we 
care about the first argument, perhaps the problem could be identified 
with an overload or specialisation.

    template < typename T, typename S>
    size_t hash_combine( S seed, const T &v ) {
        BOOST_STATIC_ASSERT( false );
    }

    template <typename T, typename S>
    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));
    }

(I'm not so hot on templates so the above may be wrong, but I hope it 
conveys the idea.)

> size_t my_hash_function(int x[4]) {
>      using namespace boost;
> 
>      return hash_combine(
>          hash_combine(hash_value(x[0]), hash_value(x[1])),
>          hash_combine(hash_value(x[2]), hash_value(x[3])));
> }

I agree this is wrong. I think:

      return hash_combine( hash_combine( hash_combine(
            hash_value( x[0] ), x[1] ), x[2] ), x[3] );

is reasonable and ideally would be supported.

> An alternative would be to implement hash_combine as an object. 
> Something like:
> 
> struct hash_seed {
>      hash_seed();
>      template <class T> void combine(T const&);
>      std::size_t value() const;
> };
> 
> Then it could initialise itself to whatever it wants.

Do you mean the seed should be an object? I can see advantages to that, 
although it seems like overkill. Adding an optional seed argument to 
hash_range and/or hash_combine sounds like a good idea, though.

-- Dave Harris, Nottingham, UK