Re: [boost] [review] hash functions

From: Peter Dimov (pdimov_at_[hidden])
Date: 2005-03-13 14:04:53

Topher Cooper wrote:
> On Mar 13, 2005, at 11:13 AM, Peter Dimov wrote:
>> implementation to which you port your program. Your original tests
>> are still valid.
>>
>> The other side of predictability - that the hash function is not
>> affected by types or the particular representation of a sequence of
>> values - means that you don't necessarily have to re-run the
>> performance benchmark of your unordered_maps when you refactor the
>> key to use int[3] instead of struct { short, short, short }, or a
>> wstring instead of a string.
>>
>
> Fundamentally, what makes for a good hash function is that things that
> are equal (however you are defining equality) always hash to the same
> value, while any small difference between two things should cause them
> to hash to completely different values.  In an arbitrary program would
> I expect an int[3] to be equal to a struct { short, short, short }
> when the values happened to be equal?  No.  What if [...]

The intent of the proposal is to provide a reasonable default when 
tr1::unordered_map is used (and to provide the tools to build such a 
reasonable default for user-defined compound types). It is not an attempt to 
build the ultimate hash function (a hopeless task).

Since the keys in an unordered_map are of the same type, it is usually not 
possible for one of them to contain int[3] and for another to hold struct 
{ short, short, short }.

A discriminated union type (boost::variant) that is able to hold either type 
can easily hash_combine the index of the currently active type to avoid 
these accidental collisions. Similarly, a boost::any-alike can hash_combine 
the address of a structure that uniquely identifies the type, or 
typeid().name(). This mirrors their implementation of operator==.

I agree that the current design may not be well suited for a general purpose 
hash function that needs to be able to sort objects of arbitrary types into 
buckets. I'm not sure how often this occurs in practice. Do you have 
examples?