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.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk