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