Boost logo

Boost :

Subject: Re: [boost] [hash] regular behaviour of hash function for double values
From: Topher Cooper (topher_at_[hidden])
Date: 2012-02-01 14:08:17

On 2/1/2012 3:59 AM, Daniel James wrote:
> On 1 February 2012 00:44, Topher Cooper<topher_at_[hidden]> wrote:
>> >
>> > values that differ by the table size end
>> > up in the same bin
> Is that likely though? And any more likely than other causes of collisions?
It is immensely more likely than any of the causes of /systematic/
collisions in a reasonable implementations that avoids destroying
expected performance (O(1)) and replacing it with worst case performance
(O(N)) for simple regularities in the input data. The expected
performance takes into account the occurrence of non-systematic
collisions. No algorithm can guarantee that there cannot be systematic
collisions (since it must be deterministic) but it is easy to make sure
that regularities in the input data would have to be incredibly
arbitrary to cause them.

Topher Cooper

Boost list run by bdawes at, gregod at, cpdaniel at, john at