From: Daniel James (daniel_at_[hidden])
Date: 2005-03-19 08:23:28
Peter Dimov wrote:
> As for table sizes being a power of two being a source of speedup, this
> is obviously only true when hv % 2^n doesn't produce collisions. If the
> key set doesn't already have this property, the cost of fixing it (in
> the general case, where it is not known which bits vary, something like
> x ^ (x % p1 + x * p2) needs to be used) may cancel the speedup obtained
> by using a 2^n table size.
I agree. This wasn't clear in my last mail, but when I wrote:
> A better approach to using a power of 2 might be to apply a further
> transformation to the hash value, which might take into account the
> current hash table size.
I meant that a power of 2 hash table should do this, and might be able
to do it better since it knows how many bits are required.
> On the other hand, it doesn't seem to cost us anything to apply x + (x
> >> 3) to our pointer hash function, so we might as well do it.
Okay, I'll do that.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk