Re: [boost] [hash] regular behaviour of hash function for double values

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