[boost] Re: [review] hash functions

From: Daniel James (daniel_at_[hidden])
Date: 2005-03-22 04:07:40

Dave Harris wrote:
> In-Reply-To: <003501c52a54$a28c4b90$6601a8c0_at_pdimov>
> pdimov_at_[hidden] (Peter Dimov) wrote (abridged):
>>This reflects their intended use. The two argument overload is used 
>>when one has a whole range and wants its hash value, as in the 
>>hash_value overload for std::vector, for example.
> 
> I actually think this is going to be fairly rare. This is mainly because 
> there will usually be a constant thrown in to represent the type of the 
> object. (I appreciate you won't do that for std containers, but I maintain 
> its a good idea for user-defined types.)

I disagree (I won't go into the reasons, as they've already been stated 
enough times). But, I'll add a note that this can be done to the 
tutorial and explain why you might want to do it.

> The 2-argument version is strictly redundant as it must be defined in 
> terms of the 3-argument version. It's just a convenience function, used 
> mainly by the std containers.
> 
> Admittedly hash_combine is also (nearly) redundant, being definable as:
> 
>     void hash_combine( size_t &hash, const T &t ) {
>         hash_range( hash, &t, &t+1 );
>     }
> 
> if T does not overload address-of. 

Since nested vectors give different hash values to their flattened form, 
I don't think a single element vector should have the same hash values 
as it's element. We don't want [[1], 2] (using square brackets as a 
representation of a sequence, not in the normal C++ sense) to be 
considered equivalent to [1, 2], so [1] is not equivalent to 1.

Now, I suppose the response to that is, if membership of a sequence 
affects the hash value, why doesn't type? I think the hash function 
should consider its values in the same manner as the STL does. 
std::equal_to considers 1u == (char) 1, but not [1]. Does that make 
sense? If it does, I'll write it in a more verbose form in the 
documentation.

> Incidently, do you agree we will sometimes want to pass a hash value as 
> the second argument to hash_combine? Like:
> 
>     hash_combine( hash, hash_range( first, last ) );
>     hash_combine( hash, obj.get_hash( some_arg ) );
> 
> If not, then maybe we should have a hash_combine that just combines 
> hashes. At the moment the combining is mixed in with the getting; it's not 
> a very orthogonal API.

No, the way to do this is to overload hash_value for the type of the 
object being hashed.

Once I've added support for Boost.Range (or vice-versa), 
boost::iterator_range could be used for value type of a range (for the 
first example). For the second one, you'll have to overload hash_value 
yourself.

So they become:

     hash_combine(seed, boost::make_iterator_range(first, last));
     hash_combine(seed, obj);

Daniel