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-02 19:04:46

On 2/2/2012 5:28 PM, Daniel James wrote:
>> >  Ah, I did miss that, but it just means that the underlying table include
>> >  indirection as open chaining generally does intrinsically (I say generally,
>> >  because it is possible to implement open chaining if that were not a
>> >  requirement with the first entry contained in the table).
>>      
> Wouldn't that defeat the purpose? If you have to follow an indirection
> for every key comparison, then you've lost the main advantage of using
> coalesced hashing.
>    
I'd have to look at the figures in detail, but I don't think so.  You do 
straight-forward coalesced hashing either with the key kept in the 
table, or perhaps its size_t sized hash-values as proxies, and pointers 
to separately allocated vector for the values pointed at.  You still get 
all the goodness -- essentially better paging, less space, and compared 
to external chaining with as many entries as bins, about equal failure 
search probes and slightly better success search probes.

In any case, the issue is whether it conforms to the standard and is a 
reasonably reasonable choice.  I'm not recommending it -- and certainly 
not as the primary implementation.  Its possible that a library might 
provide it as an alternative, chosen either manually or via policies.

Topher Cooper