Boost logo

Boost :

Subject: Re: [boost] [hash] regular behaviour of hash function for double values
From: Daniel James (dnljms_at_[hidden])
Date: 2012-02-01 11:02:35


On 1 February 2012 15:11, Dave Abrahams <dave_at_[hidden]> wrote:
>
> on Tue Jan 31 2012, Daniel James <dnljms-AT-gmail.com> wrote:
>
>> On 31 January 2012 17:57, Andrey Semashev <andrey.semashev_at_[hidden]> wrote:
>>>
>>> The standard doesn't favor or preclude either approach, so either way the
>>> implementation would be conforming. So, you might say it's my understanding of
>>> both the standard and the "best" solution. I realize that my opponent had a
>>> different opinion on this and I didn't convince him.
>>
>> The requirements for the hash function are:
>>
>> For two different values
>> t1 and t2, the probability that h(t1) and h(t2) compare
>> equal should be very small, approaching 1.0 / numeric_-
>> limits<size_t>::max().
>>
>> There's no requirement about how h(t1) and h(t2) are distributed so it
>> must be the container's responsibility, since the container must work
>> well with any hash function that meets these requirements. How else
>> can you interpret it?
>
> You can interpret it as a QOI issue, and we should aim to provide the
> highest QOI.

I think you might have misunderstood my point, the question here is
whether the containers should work well with hash functions (i.e.
other than std::hash and boost::hash) that meet the standard's
requirements but don't have a good distribution, even though that
makes the container a bit slower (this came up on the other thread
because the hit from doing a modulus is much higher on 64-bit
machines). Andrey thinks they shouldn't, I think they should.


Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk